Introduction à l'ingénierie du contrôle : planification de trajectoires — A*, Dijkstra, RRT, RRT* et PRM

Déplacer un robot d'un point de départ à un point d'arrivée implique rarement de tracer une ligne droite. Un plan utilisable doit tenir compte des murs, de la largeur du passage, de l'encombrement du robot, des limites de virage, de l'incertitude de localisation, des cartes obsolètes, des personnes en mouvement et de la distance d'arrêt. La planification de trajectoire détermine le chemin à suivre ; la génération et le contrôle de la trajectoire déterminent comment suivre cet itinéraire en tenant compte de la dynamique. Une architecture sécurisée permet de séparer ces responsabilités tout en partageant leurs limites.

Ce guide compare les algorithmes Dijkstra et A sur grille avec les algorithmes RRT, RRT et PRM en espace continu. Il explique l'inflation des obstacles, les heuristiques, l'échantillonnage, la complexité, l'intégration SLAM/Nav2, les vérifications d'implémentation et le comportement de sécurité indépendant. Voir Visual SLAM Primer, ROS 2 Primer et Sensor Fusion Primer pour des informations complémentaires.

Conclusion pratique

• L'algorithme de Dijkstra garantit un chemin le plus court sur un graphe pondéré non négatif, mais son expansion se fait dans des directions non liées à l'objectif. L'algorithme A* oriente cette expansion grâce à une heuristique admissible tout en conservant la même optimalité.

• L'algorithme RRT tend à trouver rapidement un chemin réalisable dans les espaces continus de grande dimension. L'algorithme RRT* converge vers un chemin optimal à mesure que le nombre d'échantillons augmente, moyennant des coûts supplémentaires liés aux voisins et au recâblage. L'algorithme PRM amortit la construction de la carte sur de nombreuses requêtes dans un espace suffisamment statique.

• Un chemin le plus court sur une carte non gonflée correspond à un chemin de collision pour un robot, avec un rayon, une erreur de localisation et une distance d'arrêt.

• Un itinéraire retourné ne garantit pas la sécurité. La fraîcheur de la carte, la perception locale, l'erreur de suivi, les obstacles dynamiques, la latence de replanification et l'arrêt d'urgence nécessitent un traitement indépendant.

Définir l'espace libre avant de choisir un algorithme

Soit \mathcal X l'espace d'états, \mathcal X_{obs} l'espace d'obstacles et \mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs} l'espace libre. Un chemin \sigma:[0,1]\to\mathcal X_{free} relie x_s à x_g, avec \sigma(0)=x_s,\sigma(1)=x_g. Un robot ponctuel en 2D utilise x=(x,y) ; un véhicule ajoute le cap \theta, la vitesse et la direction ; un manipulateur inclut tous les angles articulaires. La simplification de l'état réduit le coût de recherche, mais peut générer des courbes que le véhicule en aval ne peut pas réaliser.

L'inflation d'obstacles transforme un robot fini en une recherche ponctuelle en étendant les obstacles. Ici, r_{loc} doit être un terme d'incertitude spécifié, tel qu'un rayon choisi pour un niveau de confiance défini, plutôt qu'une erreur moyenne non spécifiée. Un minimum conceptuel est :

où r_{robot} est le rayon du corps, l'incertitude de localisation est représentée par le terme précédent et r_{safe} est la marge de suivi/d'arrêt. En réalité, la marge varie en fonction de la résolution de la carte, des angles morts des capteurs, de la vitesse de l'objet qui s'approche et de la capacité de freinage. Une marge trop faible entraîne une collision ; une marge trop importante rend les passages possibles impossibles.

Schéma : Duskcoil, conceptuel et non mesuré. La taille des cellules et le gonflement doivent être calculés à partir de l'empreinte réelle du robot, de l'incertitude et de la zone de fonctionnement.

Recherche sur grille : Dijkstra et A*

Pour le graphe G=(V,E) avec un coût d'arête non négatif c(u,v)\ge0, l'algorithme de Dijkstra stabilise de manière itérative le nœud non stabilisé ayant le coût initial connu le plus faible g(n) et relâche la contrainte. voisins. Une fois stabilisé, sa valeur g est minimale. Avec un tas binaire, une complexité représentative est O((|V|+|E|)\log|V|). Elle garantit la distance minimale dans le graphe, mais, sans connaissance de l'objectif, tend à s'étendre largement.

A* ordonne les nœuds par

où h(n) est une borne inférieure du coût restant. Une heuristique admissible ne surestime jamais le coût restant réel ; alors A* reste optimal. La distance de Manhattan convient aux grilles 4-connexes, tandis que la distance euclidienne ou de Tchebychev peut convenir aux déplacements 8-connexes. Une heuristique cohérente satisfait également h(n)\le c(n,n')+h(n') et réduit la ré-expansion.

A* pondéré pondère l'heuristique par w>1 pour rechercher plus rapidement un chemin faisable au détriment de l'optimalité. Cela peut être un compromis opérationnel judicieux s'il est explicite. Le coût des arêtes peut encoder non seulement la longueur, mais Risque lié aux obstacles, dégagement, virages, énergie ou terrain (calculés en fonction de l'inflation). Le résultat est alors le coût minimal défini, et non nécessairement la longueur géométrique minimale.

Espaces continus et de grande dimension : RRT, RRT*, PRM

Les grilles fines explosent dans un espace de configuration de bras à six articulations ou dans un espace de pose de véhicule. RRT échantillonne x_{rand} dans l'espace libre, trouve le nœud d'arbre le plus proche x_{near}, se dirige sur une distance limitée vers celui-ci, vérifie les collisions et ajoute x_{new}. Il est probabilistiquement complet : avec suffisamment d'échantillons, la probabilité de trouver un itinéraire réalisable tend vers un lorsqu'il existe. Il ne garantit pas un premier itinéraire court.

RRT* choisit le parent le moins coûteux parmi les sommets proches et recâble les voisins via un nouveau sommet lorsque cela est moins cher. Il est asymptotiquement optimal, mais pas optimal en temps fini ; la recherche de voisins, les tests de collision et le recâblage consomment des ressources de calcul. Il est préférable d'évaluer la qualité à l'échéance opérationnelle plutôt que de promettre l'« optimalité ».

PRM échantillonne des configurations libres et connecte les paires voisines sans collision pour former une feuille de route réutilisable. Cette méthode est particulièrement intéressante dans un environnement statique ou lors de requêtes répétées sur les bras, car le prétraitement peut être amorti. Les obstacles dynamiques invalident les arêtes. Les passages étroits rendent l'échantillonnage uniforme difficile ; des échantillons prenant en compte les limites des obstacles, les trajectoires ou les tâches peuvent donc s'avérer nécessaires.

Schéma : Duskcoil, simplifié. L’échantillonnage, la vérification des collisions et la connectivité ne constituent pas une mesure de performance ni une voie de production finale.

SLAM, Nav2 et planification locale

Le SLAM fournit une carte et une estimation de pose, mais un planificateur a besoin de transformations alignées sur l'horodatage et d'une signification claire de l'occupation et du coût. La fermeture de boucle ou la relocalisation peuvent modifier la pose dans le repère de la carte ; continuer à suivre un ancien itinéraire peut s'avérer dangereux. Intégrez l'incertitude, la réinitialisation de la localisation et les événements de mise à jour de la carte dans les règles de replanification ; voir Introduction au SLAM visuel.

Dans une architecture ROS 2 de type Nav2, une carte de coûts globale et un planificateur choisissent un itinéraire à grande échelle, tandis qu'une carte de coûts locale et un contrôleur gèrent les obstacles et la vitesse à proximité. Un algorithme A* global peut sélectionner un corridor ; la couche locale doit céder le passage, s'arrêter ou contourner une personne. Une couche purement locale peut se retrouver bloquée dans une impasse. Définissez explicitement le planificateur, le contrôleur, la récupération, les taux de mise à jour de la carte, les échéances et les priorités. Le transport ROS 2 décrit dans ROS 2 Primer ne garantit ni le temps réel ni la sécurité.

Avant le déploiement, mesurez l'encombrement, incluant la charge utile, le champ de vision des capteurs, la vitesse/décélération maximale, l'erreur de localisation et la résolution de la carte. Testez le dégagement réel dans les passages étroits. Vérifiez l'absence de collisions entre les trajectoires planifiées et le mouvement continu, ainsi que la cinématique : un itinéraire sur grille peut effectuer des virages entre les cellules, contrairement à un système à entraînement différentiel, une voiture ou un bras robotisé.

Pour les obstacles dynamiques, mesurez la fraîcheur de la détection, la vitesse relative, la distance de freinage et le temps de replanification ; ne poursuivez jamais votre mouvement en raison d'un retard du planificateur. Considérez les personnes inconnues, les trous, les obstacles transparents et les pannes de capteurs comme des cas de sécurité, et non comme des cellules automatiquement libérées. Ralentissez, arrêtez ou transférez le contrôle en l'absence d'itinéraire, si la trajectoire locale est dangereuse, si la covariance est trop importante, si la carte est obsolète ou si l'erreur de suivi dépasse sa limite. L'arrêt d'urgence doit être indépendant de la sortie du planificateur.

Liste de vérification de l'implémentation et de la sécurité

1. Définir l'espace d'états, l'empreinte, les repères, la résolution de la carte et la signification des cellules inconnues.

2. Faire en sorte que l'inflation prenne en compte l'erreur de localisation, la vitesse et la distance d'arrêt ; tester dans des passages étroits réels.

3. Vérifier l'admissibilité heuristique ou documenter la garantie délibérément assouplie.

4. Consigner la résolution de la vérification des collisions, la graine aléatoire, la date limite et le comportement en cas d'absence de solution pour les planificateurs d'échantillonnage.

5. Injecter la relocalisation, les modifications de la carte, la perte de capteurs, les obstacles dynamiques et le délai de communication.

6. Vérifier un arrêt sûr et un journal de trajectoire diagnostiquable pour les événements d'absence de route, de carte obsolète et de déviation de suivi.

Références

• Hart, Nilsson, Raphael, 1968 : A Formal Basis for A*

• LaValle : Rapidly-Exploring Random Trees

• Karaman et Frazzoli, 2011 : RRT*

• Documentation Nav2