Worldlex Wiki 
SO (2) (où SO (2) est le Espace libre
L'ensemble des configurations qui évitent les collisions avec les obstacles est appelé l'espace libre C <sub>libre</sub> . Le complémentaire de C <sub>libre</sub> dans C est appelé la région d'obstacles ou région interdite.
Il est souvent extrêmement difficile de calculer explicitement la forme de C<sub> libre</sub> . Cependant, vérifier si une configuration donnée appartient à C<sub> libre</sub> est une méthode efficace. Premièrement, la cinématique directe détermine la position de la géométrie du robot, et la détection de collision vérifie si cette géométrie entre en collision avec celle de l'environnement.
Espace cible
L'espace cible est un sous-espace de l'espace libre qui indique la direction à suivre pour le robot. En planification de mouvement globale, cet espace est observable par les capteurs du robot. Cependant, en planification de mouvement locale, le robot ne peut pas l'observer dans certains états. Pour pallier ce problème, il parcourt plusieurs espaces cibles virtuels, chacun situé dans sa zone observable (autour du robot). Un espace cible virtuel est appelé un sous-objectif.
Espace d'obstacles
L'espace d'obstacles est un espace inaccessible au robot. L'espace d'obstacles n'est pas l'opposé de 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 à l'espace de configuration, ou des algorithmes géométriques qui calculent la forme et la connectivité de C libre .
La planification exacte du mouvement pour les systèmes de grande dimension soumis à des contraintes complexes est un problème de calcul complexe . Les algorithmes de champ de potentiel sont efficaces, mais sensibles aux minima locaux (à l'exception des champs de potentiel harmoniques). Les algorithmes d'échantillonnage évitent ce problème et résolvent rapidement de nombreux problèmes. Ils ne peuvent pas déterminer l'absence de chemin, mais leur probabilité d'échec tend vers zéro avec le temps.
Les algorithmes basés sur l'échantillonnage sont actuellement considérés comme la référence en matière de planification de mouvement dans des espaces de grande dimension et ont été appliqués à des problèmes comportant des dizaines, voire des centaines de dimensions (manipulateurs robotiques, molécules biologiques, personnages numériques animés et robots à pattes ).
Recherche par grille
Les approches basées sur une grille superposent une grille à l'espace de configuration et supposent que chaque configuration est associée à un point de la grille. À chaque point, le robot peut se déplacer vers les points adjacents tant que la ligne les séparant est entièrement contenue dans l' espace libre C (vérifié par détection de collisions). Ceci discrétise l'ensemble des actions, et des algorithmes de recherche (comme A* ) sont utilisés pour trouver un chemin du point de départ à l'objectif.
Ces approches nécessitent la définition d'une résolution de grille. La recherche est plus rapide avec des grilles plus grossières, mais l'algorithme ne parviendra pas à trouver de chemins à travers les portions étroites de C<sub> libre</sub> . De plus, le nombre de points sur la grille croît exponentiellement avec la dimension de l'espace de configuration, ce qui les rend inadaptées aux problèmes de grande dimension.
Les méthodes traditionnelles basées sur une grille produisent des trajectoires dont les changements de cap sont limités à des multiples d'un angle de base donné, ce qui conduit souvent à des trajectoires sous-optimales. Les méthodes de planification de trajectoires à angle quelconque trouvent des trajectoires plus courtes en propageant l'information le long des bords de la grille (pour une recherche rapide) sans contraindre les trajectoires aux bords de la grille (pour trouver des trajectoires plus courtes).
Les approches basées sur une grille nécessitent souvent des recherches répétées, par exemple lorsque la connaissance de l'espace de configuration par le robot évolue ou lorsque l'espace de configuration lui-même change pendant le suivi de trajectoire. Les algorithmes de recherche heuristique incrémentale replanifient rapidement en exploitant l'expérience acquise avec des problèmes de planification de trajectoire similaires précédents afin d'accélérer leur recherche pour le problème actuel.
Recherche par intervalles
Ces approches sont similaires aux méthodes de recherche par grille, à la différence qu'elles génèrent un pavage couvrant intégralement l'espace de configuration au lieu d'une grille. Ce pavage est décomposé en deux sous-pavages X − , X + constitués de boîtes telles que X − ⊂ C libre ⊂ X + . La caractérisation de C libre revient à résoudre un problème d'inversion d'ensemble . L'analyse d'intervalles peut ainsi être utilisée lorsque C libre ne peut être décrit par des inégalités linéaires, afin de garantir son confinement.
Le robot peut ainsi se déplacer librement dans X− et ne peut sortir de X + . Un graphe de voisinage est construit pour chaque sous-revêtement, et des chemins peuvent être trouvés à l'aide d'algorithmes tels que Dijkstra ou A* . Si un chemin est réalisable dans X− , il l'est également dans C<sub> libre </sub>. S'il n'existe aucun chemin dans X + reliant une configuration initiale à l'objectif, nous avons la garantie qu'aucun chemin réalisable n'existe dans C<sub> libre</sub> . Concernant l'approche par grille, l'approche par intervalles est inadaptée aux problèmes de grande dimension, car le nombre de boîtes à générer croît exponentiellement avec la dimension de l'espace de configuration.
Les trois figures de droite en donnent une illustration : un crochet à deux degrés de liberté doit se déplacer de gauche à droite en évitant deux petits segments horizontaux.
Des robots ponctuels parmi des obstacles polygonaux
Déplacer des objets parmi les obstacles
Trouver la sortie d'un bâtiment
- trace de rayon la plus éloignée
Étant donné un faisceau de rayons autour de la position actuelle, dont la longueur correspond à celle du rayon atteignant un mur, le robot se déplace dans la direction du rayon le plus long, sauf s'il détecte une porte. Un tel algorithme a été utilisé pour modéliser l'évacuation d'urgence des bâtiments.
champs de potentiel artificiels
Une approche consiste à considérer la configuration du robot comme un point dans un champ de potentiel combinant l'attraction vers l'objectif et la répulsion des obstacles. La trajectoire résultante est alors affichée. Cette approche présente l'avantage de générer la trajectoire avec un faible coût de calcul. Cependant, le robot peut se retrouver piégé dans des minima locaux du champ de potentiel et ne pas trouver de chemin, ou emprunter un chemin non optimal. Les champs de potentiel artificiels peuvent être traités comme des équations continues similaires aux champs de potentiel électrostatiques (en considérant le robot comme une charge ponctuelle), ou le mouvement dans 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 exemples de fonctions de potentiel artificiel qui ont la particularité de ne présenter aucun minimum, hormis le point cible.
Algorithmes basés sur l'échantillonnage
Les algorithmes d'échantillonnage représentent l'espace de configuration par une feuille de route des configurations échantillonnées. Un algorithme de base échantillonne N configurations dans C et conserve celles qui sont libres dans C pour les utiliser comme points de repère . Une feuille de route est ensuite construite, reliant deux points de repère P et Q si le segment PQ est entièrement libre dans C. La détection de collisions est utilisée pour vérifier l'appartenance à C. Pour trouver un chemin reliant S et G, ces derniers sont ajoutés à la feuille de route. Si un chemin de la feuille de route relie S et G, le planificateur réussit et renvoie ce chemin. Sinon, la raison n'est pas certaine : soit il n'existe aucun chemin libre dans C , soit le planificateur n'a pas échantillonné suffisamment de points de repère.
Ces algorithmes sont performants pour les espaces de configuration de grande dimension, car, contrairement aux algorithmes combinatoires, leur temps d'exécution ne dépend pas (explicitement) exponentiellement de la dimension de C. Ils sont également (généralement) beaucoup plus faciles à implémenter. Ils sont probabilistiquement complets, ce qui signifie que la probabilité qu'ils produisent une solution tend vers 1 lorsque le temps d'exécution augmente. Cependant, ils ne permettent pas de déterminer l'absence de solution.
Étant donné des conditions de visibilité de base sur C libre , il a été démontré que lorsque le nombre de configurations N augmente, la probabilité que l'algorithme ci-dessus trouve une solution tend exponentiellement vers 1 . La visibilité ne dépend pas explicitement de la dimension de C ; un espace de grande dimension peut présenter une « bonne » visibilité, tout comme un espace de faible dimension peut présenter une « mauvaise » visibilité. Le succès expérimental des méthodes basées sur l'échantillonnage suggère que la plupart des espaces fréquemment rencontrés présentent 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 situés entre des paires de jalons proches, plutôt que toutes les paires.
- Les distributions d'échantillonnage non uniformes tentent de placer davantage d'étapes clés dans des 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 affirment que l'effet de la source d'aléatoire est minime comparé à l'effet de la distribution d'échantillonnage.
- Utilise un échantillonnage local en effectuant une marche aléatoire directionnelle de Monte Carlo par chaîne de Markov avec une distribution de proposition locale.
- Il est possible de réduire considérablement le nombre d’étapes nécessaires pour résoudre un problème donné en autorisant des visions courbes (par exemple en rampant sur les obstacles qui bloquent le chemin entre deux étapes ).
- Si une ou quelques requêtes de planification seulement sont nécessaires, il n'est pas toujours indispensable de construire une feuille de route couvrant l'ensemble de l'espace. Les variantes arborescentes sont généralement plus rapides dans ce cas (planification par requête unique). Les feuilles de route restent utiles si de nombreuses requêtes doivent être effectuées sur le même espace (planification par requêtes multiples).
Liste d'algorithmes notables
Concepts de planification des mouvements
Exhaustivité et performance
Un planificateur de mouvement est dit complet s'il trouve une solution en un temps fini ou s'il signale correctement son inexistence. 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é algorithmique . Lors de la démonstration mathématique de cette propriété, il est impératif de s'assurer que la démonstration a lieu en temps fini et non seulement à la limite asymptotique. Ceci est particulièrement problématique si des séquences infinies (convergeant uniquement à la limite) apparaissent lors d'une démonstration 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 convergentes, alors qu'elles ne le sont qu'à la limite infinie. Autrement dit, la solution existe, mais le planificateur ne la signalera jamais. Cette propriété est donc liée à la complétude de Turing et sert, dans la plupart des cas, de fondement théorique. Les planificateurs basés sur une approche par force brute sont toujours complets, mais ne sont réalisables que pour des configurations finies et discrètes.
En pratique, la terminaison de l'algorithme peut toujours être garantie par un compteur qui limite le nombre d'itérations et s'arrête systématiquement, qu'une solution soit trouvée ou non. Pour les systèmes temps réel, on utilise généralement un chien de garde qui interrompt le processus. Ce chien de garde doit être indépendant de tous les processus (ce qui est généralement réalisé par des routines d'interruption de bas niveau). Cependant, le cas asymptotique décrit précédemment ne sera pas atteint de cette manière. L'algorithme indiquera la meilleure solution trouvée jusqu'à présent (ce qui est mieux que rien) ou aucune solution, mais ne pourra pas indiquer correctement qu'il n'y en a aucune. Toutes les implémentations incluant un chien de garde sont toujours incomplètes (sauf si tous les cas peuvent être évalués en temps fini).
La complétude ne peut être garantie que par une preuve mathématique rigoureuse de sa correction (souvent à l'aide d'outils et de méthodes basées sur les graphes) et ne devrait être effectuée que par des experts spécialisés si l'application inclut des données de sécurité. En revanche, réfuter la complétude est aisé : il suffit de trouver une boucle infinie ou un résultat erroné. La vérification formelle des algorithmes constitue un domaine de recherche à part entière. La mise en place correcte de ces cas de test est une tâche très complexe.
La complétude de la résolution garantit que le planificateur trouvera un chemin si la résolution de la grille sous-jacente est suffisamment fine. La plupart des planificateurs à résolution complète sont basés sur une grille ou sur des intervalles. Leur complexité de calcul dépend du nombre de points de la grille sous-jacente et est de l'ordre de O(1/h d ), où h est la résolution (la longueur d'un côté d'une cellule de la grille) et d la dimension de l'espace de configuration.
La complétude probabiliste est la propriété selon laquelle, à mesure que le « travail » effectué augmente, la probabilité que le planificateur ne trouve pas de chemin, s'il en existe un, tend asymptotiquement vers zéro. Plusieurs méthodes basées sur l'échantillonnage sont probabilistement complètes. La performance d'un planificateur probabilistement complet est mesurée par sa vitesse de convergence. En pratique, on utilise généralement cette propriété, car elle permet de paramétrer le délai d'expiration du mécanisme de surveillance en fonction d'un temps de convergence moyen.
Les planificateurs incomplets ne produisent pas toujours un chemin réalisable lorsqu'il en existe un (voir premier paragraphe). Dans certains cas, ils fonctionnent bien, car ils s'arrêtent toujours après un délai garanti et laissent la place à d'autres routines.
variantes du problème
De nombreux algorithmes ont été développés pour traiter des variantes de ce problème fondamental.
Contraintes différentielles
- Bras manipulateurs (avec dynamique)
- Drones
- Voitures
- Monocycles
- Avions
- Systèmes à accélération limitée
- Obstacles mobiles (le temps ne peut pas remonter le temps)
- Aiguille orientable à pointe biseautée
- Robots à entraînement différentiel
contraintes d'optimalité
Systèmes hybrides
Les systèmes hybrides sont ceux qui combinent comportement discret et comportement continu. Voici quelques exemples de tels systèmes :
Incertitude
- Incertitude liée au mouvement
- Informations manquantes
- Détection active
- Planification sans capteurs
- Systèmes de contrôle en réseau
contraintes environnementales
- Cartes de dynamique