Planification des mouvements

Les problèmes de faible dimension peuvent être résolus avec des algorithmes basés sur une grille qui superposent une grille au-dessus de l’espace de configuration, ou des algorithmes géométriques qui calculent la forme et la connectivité de Cfree.

La planification exacte des mouvements pour des systèmes de grande dimension soumis à des contraintes complexes est impossible à calculer. Les algorithmes de champ de potentiel sont efficaces, mais sont la proie de minima locaux (une exception est les champs de potentiel harmonique). Les algorithmes basés sur l’échantillonnage évitent le problème des minima locaux et résolvent de nombreux problèmes assez rapidement.Ils sont incapables de déterminer qu’aucun chemin n’existe, mais ils ont une probabilité d’échec qui diminue à zéro à mesure que plus de temps est passé.

Les algorithmes basés sur l’échantillonnage sont actuellement considérés comme des algorithmes de pointe pour la planification de mouvements dans des espaces de grande dimension, et ont été appliqués à des problèmes qui ont des dizaines, voire des centaines de dimensions (manipulateurs robotiques, molécules biologiques, personnages numériques animés et robots à pattes).

Il existe l’algorithme parallèle de planification de mouvement (A1-A2) pour la manipulation d’objets (pour attraper l’objet volant).

Recherche basée sur une grille

Les approches basées sur une grille superposent une grille sur l’espace de configuration et supposent que chaque configuration est identifiée par un point de grille. À chaque point de grille, le robot est autorisé à se déplacer vers des points de grille adjacents tant que la ligne entre eux est complètement contenue dans Cfree (ceci est testé avec la détection de collision). Cela discrédite l’ensemble des actions et des algorithmes de recherche (comme un *) sont utilisés pour trouver un chemin du début à l’objectif.

Ces approches nécessitent de définir une résolution de grille. La recherche est plus rapide avec des grilles plus grossières, mais l’algorithme ne parviendra pas à trouver des chemins à travers des portions étroites de Cfree. De plus, le nombre de points sur la grille augmente de façon exponentielle dans la dimension de l’espace de configuration, ce qui les rend inappropriés pour des problèmes de grande dimension.

Les approches traditionnelles basées sur une grille produisent des chemins dont les changements de cap sont limités à des multiples d’un angle de base donné, ce qui entraîne souvent des chemins sous-optimaux. Les approches de planification de chemin à n’importe quel angle trouvent des chemins plus courts en propageant des informations le long des bords de la grille (pour rechercher rapidement) sans contraindre leurs chemins aux bords de la grille (pour trouver des chemins courts).

Les approches basées sur une grille doivent souvent effectuer des recherches répétées, par exemple lorsque la connaissance du robot sur l’espace de configuration change ou que l’espace de configuration lui-même change lors du suivi du chemin. Les algorithmes de recherche heuristique incrémentielle se replanent rapidement en utilisant l’expérience des problèmes de planification de chemin similaires précédents pour accélérer leur recherche du problème actuel.

Recherche par intervalles

Ces approches sont similaires aux approches de recherche par grille, sauf qu’elles génèrent un pavage couvrant entièrement l’espace de configuration au lieu d’une grille. Le pavage est décomposé en deux sous-couches X-, X+ faites avec des boîtes telles que X− ⊂ Cfree ⊂ X+. Caractériser Cfree revient à résoudre un problème d’inversion défini. L’analyse d’intervalle pourrait ainsi être utilisée lorsque Cfree ne peut pas être décrit par des inégalités linéaires afin d’avoir une enceinte garantie.

Le robot est ainsi autorisé à se déplacer librement dans X-, et ne peut pas sortir de X+. Pour les deux sous-sauts, un graphe voisin est construit et des chemins peuvent être trouvés à l’aide d’algorithmes tels que Dijkstra ou A *. Lorsqu’un chemin est réalisable dans X-, il l’est également dans Cfree. Lorsqu’aucun chemin n’existe dans X+ d’une configuration initiale à l’objectif, nous avons la garantie qu’aucun chemin réalisable n’existe dans Cfree. Comme pour l’approche basée sur la grille, l’approche par intervalles est inappropriée pour les problèmes de grande dimension, en raison du fait que le nombre de boîtes à générer augmente de manière exponentielle par rapport à la dimension de l’espace de configuration.

Une illustration est fournie par les trois figures de droite où un crochet à deux degrés de liberté doit se déplacer de gauche à droite, en évitant deux petits segments horizontaux.

La décomposition avec des sous-portées à l’aide de l’analyse d’intervalles permet également de caractériser la topologie de Cfree telle que le comptage de son nombre de composantes connectées.

Algorithmes géométriques

Robots ponctuels parmi les obstacles polygonaux

• Graphique de visibilité
• Décomposition de cellules

Traduction d’objets parmi les obstacles

• Somme de Minkowski

Trouver le moyen de sortir d’un bâtiment

• trace de rayon la plus éloignée

Étant donné qu’un faisceau de rayons autour de la position actuelle est attribué à leur longueur frappant un mur, le robot se déplace dans la direction du rayon le plus long à moins qu’une porte ne soit identifiée. Un tel algorithme a été utilisé pour modéliser les sorties d’urgence des bâtiments.

Champ de potentiel artificielmodifier

Une approche consiste à traiter la configuration du robot comme un point dans un champ de potentiel qui combine attraction vers le but et répulsion des obstacles. La trajectoire résultante est sortie en tant que chemin. Cette approche présente des avantages en ce que la trajectoire est produite avec peu de calcul. Cependant, ils peuvent être piégés dans des minima locaux du champ potentiel et ne pas trouver de chemin, ou peuvent trouver un chemin non optimal. Les champs de potentiel artificiels peuvent être traités comme des équations de continuum similaires aux champs de potentiel électrostatiques (traitant le robot comme une charge ponctuelle), ou le mouvement à travers le champ peut être discrétisé à l’aide d’un ensemble de règles linguistiques.Une fonction de navigation ou une fonction de navigation probabiliste sont des sortes de fonctions potentielles artificielles qui ont la qualité de ne pas avoir de points minimaux à l’exception du point cible.

Algorithmes basés sur l’échantillonmodifier

Les algorithmes basés sur l’échantillonnage représentent l’espace de configuration avec une feuille de route des configurations échantillonnées.Un algorithme de base échantillonne N configurations en C et conserve celles de Cfree pour les utiliser comme jalons. Une feuille de route est ensuite construite qui relie deux jalons P et Q si le segment de ligne PQ est complètement dans Cfree. Encore une fois, la détection de collision est utilisée pour tester l’inclusion dans Cfree. Pour trouver un chemin qui relie S et G, ils sont ajoutés à la feuille de route. Si un chemin dans la feuille de route relie S et G, le planificateur réussit et renvoie ce chemin. Sinon, la raison n’est pas définitive: soit il n’y a pas de chemin dans Cfree, soit le planificateur n’a pas échantillonné suffisamment de jalons.

Ces algorithmes fonctionnent bien pour les espaces de configuration à haute dimension, car contrairement aux algorithmes combinatoires, leur temps d’exécution ne dépend pas (explicitement) de manière exponentielle de la dimension de C. Ils sont également (généralement) considérablement plus faciles à implémenter. Ils sont probabilistes complets, ce qui signifie que la probabilité qu’ils produisent une solution approche 1 à mesure que plus de temps est consacré. Cependant, ils ne peuvent pas déterminer si aucune solution n’existe.

Compte tenu des conditions de visibilité de base sur Cfree, il a été prouvé qu’à mesure que le nombre de configurations N augmente, la probabilité que l’algorithme ci-dessus trouve une solution se rapproche de 1 de manière exponentielle. La visibilité ne dépend pas explicitement de la dimension de C; il est possible d’avoir un espace de grande dimension avec une « bonne » visibilité ou un espace de faible dimension avec une « mauvaise » visibilité. Le succès expérimental des méthodes basées sur des échantillons suggère que les espaces les plus couramment vus ont une bonne visibilité.

Il existe de nombreuses variantes de ce schéma de base:

• Il est généralement beaucoup plus rapide de tester uniquement des segments entre des paires de jalons proches, plutôt que toutes les paires.
• Les distributions d’échantillonnage non uniformes tentent de placer plus de jalons dans des domaines qui améliorent la connectivité de la feuille de route.
• Les échantillons quasi-aléatoires produisent généralement une meilleure couverture de l’espace de configuration que les échantillons pseudo-aléatoires, bien que certains travaux récents soutiennent que l’effet de la source du caractère aléatoire est minime par rapport à l’effet de la distribution d’échantillonnage.
• Utilise l’échantillonnage local en effectuant une marche aléatoire Monte Carlo à chaîne de Markov directionnelle avec une distribution de proposition locale.
• Il est possible de réduire considérablement le nombre de jalons nécessaires pour résoudre un problème donné en permettant des vues oculaires incurvées (par exemple en rampant sur les obstacles qui bloquent le chemin entre deux jalons).
• Si seulement une ou quelques requêtes de planification sont nécessaires, il n’est pas toujours nécessaire de construire une feuille de route de l’ensemble de l’espace. Les variantes arborescentes sont généralement plus rapides dans ce cas (planification à requête unique). Les feuilles de route sont toujours utiles si de nombreuses requêtes doivent être effectuées sur le même espace (planification multi-requêtes)

Liste des algorithmes notablesmodifier

• A*
• D*
• Arbre aléatoire à exploration rapide
• Feuille de route probabiliste