Motivations pour un nouvel algorithme de planification de tâches

Télécharger le fichier pdf d’un mémoire de fin d’études

Etat de l’art

La planification de mouvement a été largement étudiée ces deux dernières décennies, y compris dans des cadres plus généraux ou différents de ceux qui intéressaient mon équipe. Le problème général de validation continue de non-collision le long d’un chemin entre deux configurations est très bien résolu et a fait l’objet de nombreuses publications, notamment par le LAAS lui-même [1]. Il est connu depuis longtemps que la planification de mouvements de systèmes à haute dimension tels que les robots humanoïdes est complexe et nécessite le recours à des échantillonnages aléatoires de configurations. De nombreux algorithmes d’exploration basée sur des échantillonnages aléatoires existent, du plus simple et général, le RRT [2], à des plus compliqués mais plus efficaces comme le RMR* [3], et même des algorithmes spécialisés pour le cas de la planification de manipulation [4]. Les cas de manipulation non préhensile d’objets qui pourraient être lancés [5] ou poussés [6] ont été également décrits. Enfin, la manipulation préhensile est depuis longtemps le sujet d’étude d’une équipe dédiée du LAAS, qui a produit en particulier le logiciel Humanoid Path Planner (HPP) pour le résoudre [7].

Définitions

Configurations

La position exacte d’un robot humanoïde (ou plusieurs) et des objets avec lesquels il peut interagir à un instant donné est appelée configuration. Une configuration est décrite par un ensemble de paramètres décrivant les différents degrés de liberté des articulations du (des) robot(s) ainsi que des objets avec lesquels une interaction est possible. Ces paramètres sont soit des coordonnées de translation dans R3, des quaternions décrivant une rotation dans SO(2), ou une rotation 3D décrite par un élément de SO(3). L’espace des configurations est alors le produit cartésien des espaces associés à chaque degré de liberté. Algorithmiquement, les configurations sont représentées par un vecteur de nombres réels, concaténation des vecteurs d’éléments des espaces représentant chaque degré de liberté. Cela facilite l’application de transformations comme multiplication par une matrice ad hoc.
Une configuration peut être valide si elle respecte certaines conditions. Ces conditions peuvent être l’absence de collisions, ou le fait que les transformations décrivant des articulations restent dans des bornes données, par exemple un genou qui ne doit pas tourner du mauvais sens. Ou encore le fait qu’un objet ne se trouve pas en l’air mais, soit dans une main du robot, soit collé au sol. En effet on demande au robot de ne lâcher un objet qu’une fois placé au sol. En toute généralité on parlera de gripper plutôt que de main, l’organe attrapant pouvant être plus original.
L’évolution continue des configurations du robot en fonction du temps suit un chemin. Un chemin sera valide si on peut vérifier de manière continue que toutes les configurations intermédiaires de ce chemin du début à la fin sont valides.

Contraintes

Pour assurer la cohérence temporelle d’un chemin, et éviter des aberrations telles que la téléportation d’objets, certaines configurations ou portions de chemin peuvent avoir à vérifier des ensembles d’équations, appelés contraintes. On leur donne en général un nom intelligible.
Les contraintes s’expriment comme une équation de type f(q) = b où q est le vecteur de configuration, b est appelé le second membre, et f est une fonction différentiable, pas forcément linéaire. Par exemple, pour une balle de rayon r repérée par un vecteur de configuration de longueur 7, soit un vecteur 3D de translation (t1, t2, t3) et un quaternion de rotation (q0, q1, q2, q3), le placement peut s’écrire tout simplement t3=r, ou (t3, q0, q1, q2, q3) = (r, 1, 0, 0, 0) si l’on veut imposer une orientation au sol.
On distinguera des contraintes d’état, dites non paramétrables, qui doivent être respectées à un instant t et qui possèdent un second membre nul, et des contraintes de chemin, dites complémentaires ou paramétrables, qui ne fournissent pas un second membre à atteindre mais demandent de conserver le même second membre le long du chemin.
Des exemples de contraintes non paramétrables sont :
– placement : pour un objet, il s’agit d’être à une position et dans une orientation donnée. Cette contrainte devrait être vérifiée pour tout objet dès lors qu’il n’est pas dans le gripper d’un robot.
– grasp : pour un couple objet-gripper, cela requiert que l’objet se trouve exactement dans le gripper du robot s’il est supposé le tenir actuellement. Grasp est en quelque sorte l’opposé de placement.
– pregrasp : avant de saisir un objet au sol (ou après l’avoir posé), on peut demander au robot d’aligner son gripper verticalement à une petite distance donnée au-dessus de l’objet pour faciliter sa préhension.
– preplacement : avant de poser un objet (resp. après l’avoir saisi), on peut demander au robot d’aligner son gripper, et donc l’objet tenu, verticalement à une petite distance donnée au-dessus du sol. Cela peut servir lorsqu’on doit poser ou sortir l’objet d’une boîte pour éviter de heurter les murs de la boîte avec le gripper.
Voici quelques exemples de contraintes paramétrables :
– placement/complement : pour un objet, il s’agit de rester à une même position et orientation. Peu importe lesquelles.
– grasp/complement : pour un objet, il s’agit de suivre en temps réel les mouvements du gripper qui le tient actuellement.
– vertical : pour un objet en déplacement, donc qui suit déjà une contrainte grasp/complement, il s’agit de spécifier que la trajectoire de l’objet doit en plus être verticale par rapport au sol.

Etats

En synthétisant une configuration par seulement le caractère tenu ou non de chaque objet, et si tenu, par quel gripper, on groupe les configurations en états. Certains états sont irréalisables. Par exemple, on ne peut pas demander à un gripper de tenir plusieurs objets à la fois. On appelle notamment free l’état le plus simple dans lequel aucun gripper ne tient d’objet. Dans le cas d’un robot à 2 grippers et 2 objets, il y a donc 7 types d’états : le free, 4 états où un objet est tenu, 2 états où les deux objets sont tenus. Un état est donc défini par un ensemble de contraintes non-paramétrables.
Le long d’un chemin, les configurations d’un robot évoluent dans un état, et parfois changent d’état.
Evoluer dans un état signifie qu’il existe un chemin reliant deux configurations pendant lequel toutes les configurations intermédiaires sont dans le même état. Deux configurations du même état ne sont pas forcément reliables par un chemin restant dans le même état. Par exemple pour qu’un objet au sol se déplace, on ne peut pas rester dans l’état free, il faudra passer par un état où l’objet est tenu, le temps de le déplacer.
Changer d’état nécessite de passer par une configuration à l’intersection de deux états. Par exemple, pour saisir un objet, on veut passer d’un état free à un état où le gripper tient l’objet. A la frontière se trouve une configuration où le gripper tient l’objet qui est encore posé au sol : cette configuration est à l’intersection des deux états. Deux états ne possèdent pas forcément une intersection et peuvent nécessiter de passer par plusieurs états intermédiaires. Cela permet de définir un graphe d’états, dans lequel on relie des états qui ont une intersection, c’est-à-dire qui autorisent un passage direct de l’un à l’autre. De plus, on ajoute dans un graphe d’état des arêtes de boucle autour de chaque état pour représenter la possibilité de demeurer dans un même état. Les arêtes de boucle ne sont pas uniquement visuelles. On peut les interpréter en leur faisant porter des contraintes propres, comme les états. En faisant l’amalgame entre un chemin de configurations et un chemin dans le graphe suivant ses arêtes, on dira que l’arête Transit de la figure 1 porte la contrainte placement/complement, non contenue dans l’état Placement défini uniquement par la contrainte placement. Ainsi l’arête Transit illustre le fait qu’un chemin qui ne quitte pas l’état Placement est contraint par placement/complement, qui empêche un objet posé de se déplacer tout seul.
L’ensemble des configurations accessibles depuis une configuration initiale tout en suivant une arête de boucle donnée peut ainsi être visualisé comme une sous-variété au sein de l’espace des configurations, en tant qu’espace des solutions des équations des contraintes contenues dans l’arête. Par abus de langage on peut aussi parler de configurations accessibles en restant dans un même état pour signifier qu’on suit l’arête qui boucle sur cet état (par exemple Transit et Transfer  dans la figure 1).

Feuilles

Si deux configurations du même état n’ont pas tous leurs seconds membres égaux selon chaque contrainte paramétrable contenue dans l’arête de boucle associée à l’état, elles ne sont pas reliables dans le même état. En effet, par définition, changer un second membre violerait sa contrainte et donc induirait un changement d’état. En conservant les mêmes contraintes mais en changeant leur second membre, on obtient une nouvelle sous-variété « parallèle » à la première. On parlera de feuilles pour illustrer ces sous-variétés. Chacune constitue une proportion de l’espace des configurations. Cette proportion peut être nulle mais l’union des feuilles donne obligatoirement un état entier. Les seconds membres ne sont pas le seul problème à l’accessibilité mutuelle de deux configurations : un obstacle physique et les collisions qui en découlent peuvent par exemple séparer une sous variété de configurations possibles en plusieurs.
Le problème de planification de tâches de manipulation consiste donc à explorer un espace de configurations qui s’arrange en union d’états, états qui sont eux-mêmes une union disjointe de feuilles définies par des contraintes et leurs seconds membres. La suite d’état à suivre pour trouver une solution est a priori inconnue et n’est pas unique. Au sein d’une feuille même, une résolution « en ligne droite » n’est pas toujours possible. Des détours peuvent être nécessaires pour contourner un obstacle afin d‘éviter des collisions.

Motivations pour un nouvel algorithme de planification de tâches

Lors de mon stage, ma mission est d’enrichir le logiciel HPP. Le logiciel a déjà atteint un stade avancé et le LAAS cherche en ce moment à l’optimiser.
Plus précisément, en réduisant à ce qui m’aura été utile, HPP est déjà capable de laisser un utilisateur définir un problème, définir des contraintes, définir des états, spécifier les transitions d’états autorisées, choisir des configurations initiales et finales, et appliquer un des algorithmes existants pour trouver des chemins entre deux configurations. Ces algorithmes utilisent les différents modules de HPP, par exemple échantillonner une configuration, vérifier ou appliquer des contraintes sur un chemin, tester les collisions ponctuellement pour une configuration et de manière continue pour un chemin. Toutes ces fonctionnalités bas niveau sont déjà au point et il s’agit de trouver de meilleurs algorithmes. On cherche une balance entre les choix aléatoires, lorsqu’il y a trop de possibilités, et les choix déterministes, lorsqu’il y a un avantage clair à guider la résolution.
Tous les algorithmes de planification de manipulation actuellement disponibles dans HPP sont basés sur un arbre d’exploration aléatoire de l’espace des configurations, mais aucun ne guide cette exploration par un plan précis quant aux états par lesquels passer. L’exploration aléatoire basée sur une variante d’un RRT fait explorer des configurations proches de configurations déjà explorées, et les changements d’états y sont décidés de manière aléatoire. Chaque étape consiste à ajouter une nouvelle branche à l’arbre. Pour cela, on part d’une configuration q0 dans l’arbre et on cherche une nouvelle configuration accessible par un chemin direct depuis q0. Si on décide de changer d’état vers un état voisin, on projette une configuration aléatoire qrand vers une configuration qproj dans cet état voisin, et on tente de créer une configuration qinter à l’intersection des deux états qui servirait de point de passage entre q0 et qproj. Mais ceci n’est pas toujours réalisable.
Une idée nouvelle, pour accélérer la recherche de chemin solution et limiter les explorations inutiles de branches infructueuses, est de décomposer le problème en définissant à l’avance une suite d’états intermédiaires par lesquels le chemin solution doit passer. Mais comme on ne connaît pas a priori de telle suite solution, on testera de nombreuses candidates.
Le premier avantage de cette idée suppose qu’on arrive à donner un sens aux arêtes de transition du graphe d’état, de la même façon qu’on a su attacher des contraintes aux arêtes de boucle. Si cela est fait, alors une suite imposée d’états décomposera naturellement un éventuel chemin solution en portions dont les contraintes sont connues, en tant que contraintes de l’arête du graphe d’état reliant deux états adjacents. Une analyse de ces contraintes permettra d’éliminer plus ou moins tôt des candidats. Ce sera autant de temps gagné par rapport à un algorithme classique qui ne connait que les timeout ou dépassements de seuils arbitraires similaires pour annoncer un échec.
Le second avantage est qu’on divise ainsi la résolution du problème en deux sous-problèmes plus simples, ce qui est très souvent une bonne chose en algorithmique :
1. chercher une suite de configurations suivant les étapes de la suite d’états
2. à partir de la suite de configurations ainsi générée, relier les paires de configurations consécutives par un chemin continu.
Calculer une suite de configurations ne demande aucunement de calculer des interpolations continues entre deux configurations, et requiert une quantité minimale de tests de collisions par opposition à une validation continue de chemin, plus coûteuse en temps de calcul. L’intérêt de relier ensuite les paires de configurations consécutives de cette suite est que deux configurations consécutives sont sur une même feuille et on peut donc espérer les relier sans changer d’état, réduisant considérablement la dimension de l’espace de configurations à explorer pour les algorithmes d’exploration aléatoire appelés pour relier ces paires de configurations.
D’où l’intérêt de rechercher un algorithme suivant ce plan général où le choix de la suite d’état précède toute résolution de configuration ou chemin. Pour cela on propose un algorithme qui itère par ordre de longueur sur toutes les suites d’états possibles pour aller de l’état initial à l’état final, puis qui cherche pour chaque suite générée à résoudre un chemin qui suive cette suite. Cet ordre maximisera les chances de trouver en premier une solution plus courte. Ceci contraste avec les algorithmes classiques qui agrandissent l’arbre d’exploration pas à pas à partir de la configuration initiale en usant de différentes heuristiques pour faire croître les chances que des branches de l’arbre atteignent la configuration finale.

Mise en œuvre

Prérequis

On suppose que le graphe d’états est connu à l’avance : les états possibles (EPC compris), ainsi que les arêtes les reliant et donc les contraintes associées à chaque arête et chaque état. C’est à l’utilisateur de définir les mouvements possibles pour son robot et de définir les interactions que son robot peut avoir avec les objets de son environnement.
On peut donc naturellement parler par la suite d’une liste d’états, ordonnée arbitrairement, ainsi que de la liste de contraintes du graphe, union de l’ensemble des contraintes contenues dans chaque arête et état du graphe.

Génération des suites d’états par ordre de longueur

Cette partie étant loin d’être la plus coûteuse en ressources et en temps, plusieurs solutions peuvent être implémentées : c’est un exercice de parcours de graphe relativement classique. La version implémentée dans HPP a été optimisée et saurait difficilement être décrite en détail mais utilise le principe suivant basé sur la structure de queue. On part d’une queue contenant une seule suite d’états, la suite d’états de longueur 1 contenant seulement s0 l’état de la configuration initiale. On parcourt la queue et pour chaque chemin s0-s1-s2-…-sn rencontré, on crée des nouveaux chemins de la forme s0-s1- …-sn-s* pour tous les états voisins s* de sn, et on ajoute ces nouveaux chemins au bout de la queue. Lorsque sn est l’état de la configuration finale, on envoie le chemin obtenu à la prochaine étape de l’algorithme. Ce parcours de queue s’arrête dans deux cas :
– Lorsque la suite de l’algorithme réussit à trouver une solution valide à partir d’un chemin s0-s1-…-sn rencontré.
– Quand n dépasse un certain seuil fixé à l’avance, dans ce cas on considère que l’algorithme a échoué à trouver une solution suffisamment « courte », au sens du nombre de changements d’états à effectuer.
Par la suite, pour alléger les écritures, on notera q0 la configuration initiale, qn la configuration finale, et pour k entre 1 et n-1, qk désignera une configuration, a priori inconnue mais que l’on cherchera à calculer, point de passage de la solution dans l’état sk. Trouver une telle suite (qi)i est un objectif intermédiaire de cet algorithme.

Analyse préliminaire des contraintes

Après avoir reçu une suite d’états à suivre de la part de l’étape précédente de l’algorithme, on peut repérer les contraintes qui doivent être conservées depuis la configuration q0, ou à partir d’une certaine étape jusqu’à la configuration qn, ou juste le long d’un tronçon de la solution.
Ainsi, si une même contrainte c se retrouve dans les k premières arêtes, on possède déjà une équation pour contraindre la configuration qk. Si une contrainte c n’est pas valable dès la première arête mais est valable sur les k dernières arêtes, on a une équation sur la configuration qn-k. Si une contrainte est vérifiée de l’arête k1 à l’arête k2-1, on sait que la configuration qk1 suffit à contraindre les configurations intermédiaires jusqu’à qk2. Enfin, si une contrainte c est dans toutes les arêtes, on obtient une équation reliant q0 à qn. Si cette dernière crée un conflit, on en déduit immédiatement que la suite d’état ne peut fournir de solution et on retourne à l’étape précédente de l’algorithme pour chercher le prochain candidat de suite d’états.
Toutes ces informations sont enregistrées dans un tableau T bidimensionnel qui, pour chaque contrainte de la liste de contraintes du graphe, et chaque point de passage indexé par k entre 1 et n-1, donne l’une des 4 possibilités suivantes :
– ABSENT pour une contrainte ne restreignant pas cette étape.
– EQUAL_TO_INIT pour une contrainte présente depuis la première arête.
– EQUAL_TO_GOAL pour une contrainte présente jusqu’à la fin.
– EQUAL_TO_PREVIOUS pour les autres cas.
On retient alors les contraintes pertinentes à la résolution de qk pour chaque k, à savoir les contraintes de l’arête k repérées par un statut EQUAL_TO_INIT ou EQUAL_TO_PREVIOUS dans le tableau T, et les contraintes de l’arête k+1 repérées par un statut EQUAL_TO_GOAL.

Résolution d’une suite de configurations

Cette partie, le cœur de l’algorithme, consiste à obtenir pour chaque état intermédiaire sk pour k allant de 1 à n-1, une configuration qk telle que :
– elle soit dans sk, c’est-à-dire que qk doit respecter les contraintes de l’état sk,
– les seconds membres de qk pour chaque contrainte d’arête de l’arête liant sk-1 à sk soient égaux aux seconds membres pour ces contraintes de qk-1.
En effet, pour effectivement bénéficier de la possibilité de relier des paires (qk-1,qk) par un chemin continu restant dans une même arête à la prochaine étape, il faut s’assurer que qk-1 et qk soient dans la même feuille de cette arête (cf Figure 3 : ici ce n’est pas le cas et il faut changer d’état). Partant de q0 déjà connu, on essaye de déterminer des qi pour tout i de 1 à n-1, un par un récursivement, avec possibilité de backtrack si un échec est rencontré pour un certain k, afin d’éviter de tout recommencer alors que le début de la liste de qi pourrait être conservé. On entretiendra un compteur d’échecs à chaque étape pour déterminer à quel moment reprendre à la même étape et à quels autres moments revenir en arrière et de combien.
Pour résoudre qk à partir de qk-1, on ajoute les équations associées à chaque contrainte pertinente à un solver Sk. Les solvers sont une structure de HPP destinée à mettre en forme les systèmes d’équation et à projeter des configurations sur l’espace des solutions de ces équations, que je n’ai pas eue à coder. Les seconds membres de ces équations sont ceux de q0, qk-1 ou qn, selon le statut dans T de la contrainte.
Lors d’un premier essai pour résoudre qk, on tente d’appliquer le solver Sk à qk-1 : on veut projeter qk-1 sur l’espace des solutions que qk devrait respecter. Si cela ne marche pas, ou si la configuration obtenue n’est pas valide (au sens des collisions notamment), on recommence quelques fois mais en appliquant Sk à des configurations aléatoires. L’intérêt de commencer par projeter qk-1 plutôt qu’une configuration aléatoire est qu’on peut ainsi espérer que la solution trouvée qk soit proche de qk-1. Au bout d’un certain nombre d’échecs, on remonte un cran en arrière : on tente de résoudre qk-1 en fonction de qk-2 après avoir incrémenté d’1 le compteur d’échecs de résolution de qk-1 et remis à zéro celui de qk.
Cette étape de l’algorithme termine à un de ces deux moments :
– Lorsque qn-1 est résolu. Dans ce premier cas c’est une réussite et on passe la suite de configurations ainsi résolue à l’étape suivante de l’algorithme.
– Lorsque le compteur d’échecs de résolution de q1 dépasse une limite fixée. On retourne à la première étape calculer le prochain candidat de suite d’état.
Dans certains problèmes, on peut rencontrer un cas où, quel que soit le début de la résolution, toutes les tentatives de résoudre qk échoueront au même k proche de n, entrainant un nombre exponentiel en k de calculs de résolution des configurations avant l’étape k jusqu’à épuiser tous les compteurs d’échecs. Pour se prémunir de trop longs calculs dans ce cas, on met à jour à chaque échec un compteur global d’échecs. Quand ce compteur global dépasse un certain seuil dépendant de n, on réinitialise l’intégralité de la liste et on incrémente directement le compteur d’échecs de q1.
Avec cet autre critère d’échec et après de nombreux tests il m’a été possible de déterminer des seuils où fixer le maximum des compteurs d’échecs de façon à conduire à des faibles taux de rejets de faux négatifs (des candidats de suites d’états pour lesquelles il aurait été possible de trouver une suite de configuration suivant la suite d’état mais où trop d’erreurs de projection ont fait échouer le candidat) tout en gardant un temps d’exécution satisfaisant : négligeable devant d’autres parties de l’algorithme.

Analyse préliminaire des collisions

Cette étape est facultative et constitue une optimisation permettant d’éliminer rapidement des candidats de suite d’états qui échoueraient forcément à l’étape de résolution, après des calculs plus lourds. Elle survient avant l’étape décrite précédemment de résolution d’une suite de configurations, mais la seconde justifiant la première, il était nécessaire de les introduire en ordre inverse.
L’analyse préliminaire de collisions cherche s’il existe un i entre 1 et n-1 où peu importe qi-1, il y aura forcément une collision dans qi. Si un tel événement se produit, on peut éliminer le mauvais candidat en temps linéaire en n, sans avoir résolu une liste de configurations intermédiaires (qi)i, donc sans s’être engagé dans le backtracking. Pour cela, on exploite le caractère prévisible des équations de contraintes aux statuts EQUAL_TO_INIT et EQUAL_TO_GOAL, par opposition aux contraintes au statut EQUAL_TO_PREVIOUS qui ne sont utilisables que si on résout la suite de (qi)i en entier. Dans certains cas, ces équations prévisibles déterminent entièrement qi ou une partie de la configuration. S’il y a déjà une collision parmi ce qui a pu être déterminé, le candidat est éliminé.
Par exemple les équations prévisibles peuvent suffire à déterminer les positions des objets tandis que la position du robot peut rester inconnue. Si deux objets dont la position est déterminée sont en collision, alors peu importe la position du robot, il y aura toujours une collision.
Pour pouvoir réaliser des tests de collision dans une configuration partielle, HPP dispose d’une fonctionnalité pour savoir quelles parties des robots et des objets sont contraintes par rapport aux autres. On projette donc une configuration aléatoire sur l’espace des solutions des équations prévisibles et on teste si une collision est détectée entre deux parties de l’univers (objet ou articulation d’un robot…) contraintes l’une par rapport à l’autre. Dans l’exemple précédent on ignorerait une collision entre le robot et un objet si le robot n’est pas contraint avec l’objet : le robot s’est trouvé en collision avec l’objet par hasard, pas à cause d’une contrainte, et on compte sur le fait que cette collision n’est pas inévitable.
En pratique on peut observer que l’ajout de cette étape de vérification peut être d’une aide cruciale pour diviser le temps d’exécution, lorsque de telles analyses démontrent en effet des collisions prévisibles. En revanche pour d’autres problèmes où ce genre de démonstration n’aboutit jamais, faire ce test est une pure perte de temps. De plus il est nécessaire de refaire la projection plusieurs fois à chaque étape, jusqu’à ce que la projection n’échoue pas, et la projection sur un ensemble réduit d’équations semble en effet échouer assez souvent. Lorsqu’elle échoue un certain nombre de fois sans jamais avoir réussi, on passe simplement à l’étape suivante pour ne pas consacrer trop de temps à un test facultatif.

Construction d’un chemin entre deux configurations sur une même feuille

Une fois la suite (qi)i construite, le problème est réduit à n applications d’un algorithme de construction de chemin entre deux configurations d’une même feuille, où les contraintes à respecter sont connues et valable sur tout le chemin à construire. Cette tâche simple est déjà aisément résolue par les algorithmes de manipulation préexistants de HPP, basés sur de l’exploration aléatoire, il suffit de leur donner la liste de contraintes à respecter, et lorsqu’une solution existe, elle est trouvée rapidement, d’autant plus vite que les configurations à relier sont proches.
Toutefois le succès n’est pas garanti à cette étape. Des obstacles physiques peuvent toujours se trouver sur le chemin direct et demander de passer par un détour. Cela mène parfois à dépasser un seuil de timeout. Il est même possible qu’il n’existe pas de chemin ne quittant pas la feuille lorsqu’un obstacle physique est insurmontable sans changer d’état.
En cas d’échec sur une seule des n parties du chemin, la suite de configurations déterminée à la précédente étape doit être abandonnée mais pas forcément la liste d’états dans laquelle ces configurations ont été trouvées. L’aléatoire jouant toujours dans la détermination de la suite de configurations, l’algorithme revient seulement au début de l’étape de la suite de configurations. Il n’est alors pas nécessaire de refaire l’analyse préliminaire de collisions car elle ne prend en compte que des collisions déterministes, indépendantes de tout choix aléatoire.
En cas de succès, les n chemins trouvés sont concaténés et constituent la solution au problème de manipulation que renvoie l’algorithme.
Si après plusieurs échecs de cette dernière étape sur la même liste d’états, on ne trouve toujours pas de solution, on juge la liste d’états mauvais candidat et on revient
à la première étape pour le prochain candidat. En effet il peut subsister des cas où peu importe les choix faits, une collision arrivera inévitablement entre deux configurations intermédiaires. L’étape d’analyse de collisions n’analysant que ces configurations intermédiaires, on ne pouvait pas le prévoir à l’avance avec cet algorithme.

Développements futurs

Pour chaque nouvel algorithme de planification de manipulation, il est intéressant de démontrer sa complétude, c’est-à-dire se demander si, en laissant un temps infini à l’algorithme sans le limiter par un timeout ou un nombre maximal d’itérations autorisées, la probabilité que l’algorithme trouve une solution, si elle existe, tende vers 1. La complétude a surtout un intérêt théorique. En pratique on sacrifiera souvent cette qualité si cela permet d’intégrer des optimisations qui accélèrent l’algorithme. L’objectif de la complétude a été évoqué à la fin de mon stage et il a été décidé de le garder pour une autre occasion étant donné le peu de temps qui me restait.
Les tests de mon code ont permis de découvrir des comportements inattendus dans le reste du logiciel HPP en utilisant des modules et fonctions dans des cas de figure jamais explorés auparavant. Certains bugs ont été résolus par la même occasion, d’autres restent ouverts mais sont désormais connus.
Il y a d’autres façons de gérer les échecs à la dernière étape reliant les paires de configurations intermédiaires consécutives. J’ai codé la façon qui semblait la plus naturelle, et j’en ai mesuré les performances sur les différents tests dont je disposais mais je n’ai pas eu le temps d’en coder et tester d’autres. On pourrait réutiliser partiellement les configurations intermédiaires en ne résolvant à nouveau que quelques solutions autour de la portion où la dernière étape a échoué. Ou encore pouvoir réutiliser des portions de chemins continus déjà résolus lorsque des tentatives futures réutilisent les mêmes extrémités du chemin.
Enfin, le dernier axe de progression de mon algorithme, que je n’ai pas eu le temps de proprement finir, devrait être poursuivi. Il s’agit de trouver des raccourcis dans le chemin trouvé en solution, et ainsi de trouver une meilleure solution. Pour l’instant il n’est possible que de trouver des raccourcis « locaux », qui sont intégralement contenus entre deux des configurations intermédiaires qi et qi+1. Être capable de trouver des raccourcis globaux qui évitent une des configurations intermédiaires pourrait être un objectif futur.

Table des matières

Abstract
Remerciements
Sommaire
Contexte du travail
Etat de l’art
Définitions
Configurations
Contraintes
Etats
Feuilles
Motivations pour un nouvel algorithme de planification de tâches
Mise en œuvre
Prérequis
Génération des suites d’états par ordre de longueur
Analyse préliminaire des contraintes
Résolution d’une suite de configurations
Analyse préliminaire des collisions
Construction d’un chemin entre deux configurations sur une même feuille
Développements futurs
Bibliographie

Télécharger le rapport complet