Planification de mouvement - Motion planning

La planification de mouvement , également la planification de chemin (également connue sous le nom de problème de navigation ou problème du moteur de piano ) est un problème de calcul pour trouver une séquence de configurations valides qui déplace l'objet de la source à la destination. Le terme est utilisé dans la géométrie computationnelle , l' animation informatique , la robotique et les jeux informatiques .

Par exemple, envisagez de diriger un robot mobile à l' intérieur d'un bâtiment jusqu'à un point de cheminement éloigné. Il doit exécuter cette tâche en évitant les murs et en ne tombant pas dans les escaliers. Un algorithme de planification de mouvement prendrait en entrée une description de ces tâches et produirait les commandes de vitesse et de rotation envoyées aux roues du robot. Les algorithmes de planification de mouvement peuvent traiter des robots avec un plus grand nombre d'articulations (par exemple, des manipulateurs industriels), des tâches plus complexes (par exemple la manipulation d'objets), des contraintes différentes (par exemple, une voiture qui ne peut qu'avancer) et l'incertitude (par exemple des modèles imparfaits de l'environnement ou le robot).

La planification de mouvement a plusieurs applications robotiques, telles que l' autonomie , l' automatisation et la conception de robots dans les logiciels de CAO , ainsi que des applications dans d'autres domaines, tels que l'animation de personnages numériques , le jeu vidéo , la conception architecturale , la chirurgie robotique et l'étude des molécules biologiques .

notions

Exemple d'espace de travail.
Espace de configuration d'un robot de taille ponctuelle. Blanc = C libre , gris = C obs .
Espace de configuration pour un robot de traduction rectangulaire (en rouge). Blanc = C libre , gris = C obs , où gris foncé = les objets, gris clair = configurations où le robot toucherait un objet ou quitterait l'espace de travail.
Exemple de chemin valide.
Exemple de chemin invalide.
Exemple de feuille de route.

Un problème de planification de mouvement de base est de calculer un chemin continu qui relie une configuration de départ S et une configuration d'objectif G, tout en évitant la collision avec des obstacles connus. La géométrie du robot et de l'obstacle est décrite dans un espace de travail 2D ou 3D , tandis que le mouvement est représenté comme un chemin dans l' espace de configuration (éventuellement de dimension supérieure) .

Espace de configuration

Une configuration décrit la pose du robot, et l' espace de configuration C est l'ensemble de toutes les configurations possibles. Par exemple:

  • Si le robot est un seul point (taille zéro) se traduisant dans un plan à 2 dimensions (l'espace de travail), C est un plan et une configuration peut être représentée à l'aide de deux paramètres (x, y).
  • Si le robot est une forme 2D qui peut se déplacer et pivoter, l'espace de travail est toujours en 2 dimensions. Cependant, C est le groupe euclidien spécial SE (2) = R 2 SO (2) (où SO (2) est le groupe orthogonal spécial des rotations 2D), et une configuration peut être représentée à l'aide de 3 paramètres (x, y, θ ).
  • Si le robot est une forme 3D solide qui peut se déplacer et pivoter, l'espace de travail est en 3 dimensions, mais C est le groupe euclidien spécial SE(3) = R 3 SO (3), et une configuration nécessite 6 paramètres : (x, y, z) pour la translation, et les angles d'Euler (α, β, γ).
  • Si le robot est un manipulateur à base fixe avec N articulations tournantes (et pas de boucles fermées), C est N-dimensionnel.

Espace libre

L'ensemble des configurations qui évite la collision avec les obstacles est appelé l'espace libre C free . Le complément de C libre dans C est appelé l'obstacle ou la région interdite.

Souvent, il est excessivement difficile de calculer explicitement la forme de C free . Cependant, tester si une configuration donnée est en C libre est efficace. Tout d'abord, la cinématique avant détermine la position de la géométrie du robot et les tests de détection de collision si la géométrie du robot entre en collision avec la géométrie de l'environnement.

Espace cible

L'espace cible est un sous-espace d'espace libre qui indique où nous voulons que le robot se déplace. Dans la planification de mouvement global, l'espace cible est observable par les capteurs du robot. Cependant, dans la planification de mouvement local, le robot ne peut pas observer l'espace cible dans certains états. Pour résoudre ce problème, le robot parcourt plusieurs espaces cibles virtuels, chacun étant situé dans la zone observable (autour du robot). Un espace cible virtuel est appelé un sous-objectif.

Espace d'obstacles

L'espace d'obstacles est un espace dans lequel le robot ne peut pas se déplacer. L'espace d'obstacles n'est pas opposé à l'espace libre.

Algorithmes

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 C free .

La planification exacte du mouvement pour les systèmes de grande dimension sous des contraintes complexes est difficilement calculable . Les algorithmes de champ potentiel sont efficaces, mais sont la proie de minima locaux (à l'exception des champs potentiels harmoniques). 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 jusqu'à zéro au fur et à mesure que le temps passe.

Algorithmes basés sur un échantillonnage sont actuellement considérés comme l' état de l'art pour la planification de mouvement dans des espaces de grande dimension, et ont été appliquées à des problèmes qui ont des dizaines ou des centaines même de dimensions (manipulateurs robotiques, des molécules biologiques, des personnages numériques animés, et les jambes robots ).

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 la grille

Les approches basées sur la 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 C libre (ceci est testé avec détection de collision). Cela discrétise l'ensemble des actions et des algorithmes de recherche (comme A* ) sont utilisés pour trouver un chemin du début au but.

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 C free . 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 les problèmes de grande dimension.

Les approches traditionnelles basées sur la grille produisent des chemins dont les changements de cap sont contraints à des multiples d'un angle de base donné, ce qui entraîne souvent des chemins sous-optimaux. Les approches de planification de chemin à tout angle trouvent des chemins plus courts en propageant les 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 la grille doivent souvent rechercher à plusieurs reprises, par exemple, lorsque les connaissances du robot sur l'espace de configuration changent ou que l'espace de configuration lui-même change pendant le suivi du chemin. Les algorithmes de recherche heuristique incrémentielle replanifient rapidement en utilisant l'expérience des précédents problèmes de planification de chemin similaires pour accélérer leur recherche du problème actuel.

Recherche par intervalle

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- pavages X ,X + réalisés avec des boîtes telles que X ⊂ C libre ⊂ X + . Caractériser C libre revient à résoudre un problème d'inversion d'ensembles . L'analyse par intervalles pourrait ainsi être utilisée lorsque C libre 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-pavages, 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 faisable en X , il est aussi faisable en C libre . Lorsqu'aucun chemin n'existe en X + d'une configuration initiale au but, nous avons la garantie qu'aucun chemin réalisable n'existe en C free . Comme pour l'approche par grille, l'approche par intervalles est inappropriée pour les problèmes de grande dimension, du fait que le nombre de boîtes à générer croît de façon 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.

Mouvement de la configuration initiale (bleu) à la configuration finale du crochet, en évitant les deux obstacles (segments rouges). Le coin inférieur gauche du crochet doit rester sur la ligne horizontale, ce qui donne au crochet deux degrés de liberté.
Décomposition avec des cases couvrant l'espace de configuration : Le sous-pavage X est l'union de toutes les cases rouges et le sous-pavage X + est l'union des cases rouges et vertes. Le chemin correspond au mouvement représenté ci-dessus.
Ce chiffre correspond au même chemin que ci-dessus mais obtenu avec beaucoup moins de cases. L'algorithme évite de diviser des boîtes dans des parties de l'espace de configuration qui n'influencent pas le résultat final.

La décomposition en sous-pavages par analyse par intervalles permet également de caractériser la topologie de C libre comme le comptage de son nombre de composantes connexes.

Algorithmes géométriques

Pointez les robots parmi les obstacles polygonaux

Traduire des objets parmi des obstacles

Trouver la sortie d'un immeuble

  • le tracé de rayon le plus éloigné

Étant donné qu'un faisceau de rayons autour de la position actuelle attribuée avec leur longueur frappe 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.

Champs de potentiel artificiel

Une approche consiste à traiter la configuration du robot comme un point dans un champ potentiel qui combine l'attraction vers le but et la 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 les 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 continues similaires aux champs de potentiel électrostatique (en 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 minimums à l'exception du point cible.

Algorithmes basés sur l'échantillonnage

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 en C libres d'utilisation comme jalons . Une feuille de route est alors construite qui relie deux jalons P et Q si le segment de ligne PQ est complètement en C libre . Encore une fois, la détection de collision est utilisée pour tester l'inclusion dans C free . 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 en C free , soit le planificateur n'a pas échantillonné suffisamment de jalons.

Ces algorithmes fonctionnent bien pour les espaces de configuration de grande 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) sensiblement plus faciles à mettre en œuvre. Ils sont probabilistes complets, ce qui signifie que la probabilité qu'ils produisent une solution approche 1 à mesure que le temps passe. Cependant, ils ne peuvent pas déterminer s'il n'existe pas de solution.

Compte tenu des conditions de visibilité de base sur C free , 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 observés 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 les segments entre les paires de jalons proches, plutôt que toutes les paires.
  • Les distributions d'échantillonnage non uniformes tentent de placer plus de jalons dans les zones 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 un échantillonnage local en effectuant une marche aléatoire de Monte Carlo directionnelle par chaîne de Markov 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 autorisant des viseurs incurvés (par exemple en rampant sur les obstacles qui bloquent le passage 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 notables

Complétude et performances

Un planificateur de mouvement est dit complet si le planificateur en temps fini produit une solution ou rapporte correctement qu'il n'y en a pas. La plupart des algorithmes complets sont basés sur la géométrie. La performance d'un planificateur complet est évaluée par sa complexité de calcul . Lors de la démonstration mathématique de cette propriété, il faut s'assurer que cela se produit en temps fini et pas seulement dans la limite asymptotique. Ceci est particulièrement problématique s'il se produit des séquences infinies (qui ne convergent que dans le cas limite) au cours d'une technique de preuve spécifique, car alors, théoriquement, l'algorithme ne s'arrêtera jamais. Les "astuces" intuitives (souvent basées sur l'induction) sont généralement considérées à tort comme convergeant, ce qu'elles ne font que pour la limite infinie. En d'autres termes, la solution existe, mais le planificateur ne la rapportera jamais. Cette propriété est donc liée à la complétude de Turing et sert dans la plupart des cas de fondement/orientation théorique. Les planificateurs basés sur une approche de force brute sont toujours complets, mais ne sont réalisables que pour des configurations finies et discrètes.

En pratique, la fin de l'algorithme peut toujours être garantie en utilisant un compteur, qui ne permet qu'un nombre maximum d'itérations et s'arrête alors toujours avec ou sans solution. Pour les systèmes en temps réel, cela est généralement réalisé en utilisant une minuterie de surveillance , qui tuera simplement le processus. Le chien de garde doit être indépendant de tous les processus (généralement réalisé par des routines d'interruption de bas niveau). Le cas asymptotique décrit au paragraphe précédent ne sera cependant pas atteint de cette manière. Il signalera le meilleur qu'il a trouvé jusqu'à présent (ce qui est mieux que rien) ou aucun, mais ne peut pas signaler correctement qu'il n'y en a pas. Toutes les réalisations incluant un chien de garde sont toujours incomplètes (sauf que tous les cas peuvent être évalués en temps fini).

L'exhaustivité ne peut être fournie que par une preuve d'exactitude mathématique très rigoureuse (souvent aidée par des outils et des méthodes basées sur des graphiques) et ne doit être effectuée par des experts spécialisés que si l'application comprend un contenu de sécurité. D'un autre côté, réfuter l'exhaustivité est facile, car il suffit de trouver une boucle infinie ou un résultat erroné renvoyé. La vérification formelle/correction des algorithmes est un domaine de recherche à part entière. La configuration correcte de ces cas de test est une tâche hautement sophistiquée.

L'exhaustivité de la résolution est la propriété selon laquelle le planificateur est assuré de trouver un chemin si la résolution d'une grille sous-jacente est suffisamment fine. La plupart des planificateurs de résolution complète sont basés sur une grille ou sur des intervalles. La complexité de calcul des planificateurs complets de résolution dépend du nombre de points dans la grille sous-jacente, qui est O(1/h d ), où h est la résolution (la longueur d'un côté d'une cellule de grille) et d est la configuration dimension de l'espace.

L'exhaustivité probabiliste est la propriété qu'au fur et à mesure que le « travail » est effectué, la probabilité que le planificateur ne réussisse pas à trouver un chemin, s'il en existe un, se rapproche asymptotiquement de zéro. Plusieurs méthodes basées sur des échantillons sont probabilistes complètes. La performance d'un planificateur probabiliste complet est mesurée par le taux de convergence. Pour des applications pratiques, on utilise généralement cette propriété, car elle permet de paramétrer le time-out du chien de garde en fonction d'un temps de convergence moyen.

Les planificateurs incomplets ne produisent pas toujours un chemin réalisable lorsqu'il existe (voir premier paragraphe). Parfois, les planificateurs incomplets fonctionnent bien dans la pratique, car ils s'arrêtent toujours après un temps garanti et permettent à d'autres routines de prendre le relais.

Variantes du problème

De nombreux algorithmes ont été développés pour gérer des variantes de ce problème de base.

Contraintes différentielles

Holonomique

  • Bras manipulateurs (avec dynamique)

Non holonome

  • Drones
  • Voitures
  • Monocycles
  • Avions
  • Systèmes bornés d'accélération
  • Obstacles mobiles (le temps ne peut pas reculer)
  • Aiguille orientable à pointe biseautée
  • Robots à entraînement différentiel

Contraintes d'optimalité

Systèmes hybrides

Les systèmes hybrides sont ceux qui mélangent comportement discret et continu. Des exemples de tels systèmes sont :

Incertitude

  • Incertitude de mouvement
  • Information manquante
  • Détection active
  • Planification sans capteur

Applications

Voir également

Les références

Lectures complémentaires

Liens externes