Homotopy Class

Aussi appelé: homotopy class of paths
Catégorie: Planning & manipulation › Motion planning
Mots-clés: motion-planning, topology, trajectory-optimization, mobile-navigation

Ensemble de chemins ayant le même départ et le même but, qui peuvent être déformés continûment les uns en les autres sans traverser d'obstacle, par exemple tous les chemins qui passent à gauche d'un pilier donné.

Définition

Deux chemins ayant les mêmes points de départ et d'arrivée sont homotopes (homotopic) si l'on peut déformer continûment l'un en l'autre en gardant les extrémités fixes et en maintenant chaque chemin intermédiaire dans l'espace libre. Cette relation partitionne l'ensemble des chemins possibles en classes d'équivalence, appelées classes d'homotopie (homotopy classes). Dans un plan comportant un obstacle entre le départ et le but, les chemins qui passent à sa gauche forment une classe et ceux qui passent à sa droite en forment une autre ; les chemins qui font une ou plusieurs fois le tour de l'obstacle avant d'atteindre le but forment d'autres classes, si bien qu'un seul obstacle produit déjà une infinité de classes, distinguées par leur indice d'enroulement. Chaque obstacle supplémentaire multiplie les possibilités.

Le concept est important parce que la plupart des optimiseurs de chemin travaillent localement. Les optimiseurs de trajectoire à base de gradient et les bandes élastiques déforment un chemin pour le rendre plus court ou plus lisse, mais ils ne peuvent pas le pousser à travers un obstacle ; ils ne trouvent donc que le meilleur chemin au sein de la classe dans laquelle ils ont démarré. Ce sont les planificateurs globaux qui décident de la classe à utiliser, souvent implicitement. Un planificateur par échantillonnage tel que RRT peut d'abord trouver un chemin passant par un interstice, puis découvrir plus tard un chemin plus court passant par un autre, ce qui se traduit par une chute soudaine du coût du chemin plutôt que par une amélioration progressive. Les planificateurs qui tiennent compte de l'homotopie rendent cela explicite en suivant plusieurs classes en parallèle et en optimisant le meilleur chemin de chacune.

En pratique, les planificateurs utilisent souvent un invariant calculable plutôt que l'homotopie elle-même. Pour les problèmes plans, une H-signature ou un décompte de l'angle d'enroulement autour de chaque obstacle indique de quel côté de chaque obstacle passe un chemin, ce qui identifie au sens strict la classe d'homologie, apparentée mais plus grossière. Dans l'espace de configuration de dimension plus élevée d'un bras, les classes existent toujours mais sont difficiles à énumérer ; on en parle donc surtout pour les robots mobiles, les véhicules et les problèmes plans.

Pourquoi c'est important

Savoir à quelle classe d'homotopie appartient un chemin explique pourquoi un optimiseur local reste bloqué sur un long détour, pourquoi le coût d'un planificateur saute brusquement et pourquoi un robot peut osciller entre passer un obstacle par la gauche et par la droite. Les planificateurs qui raisonnent sur les classes évitent ces échecs et peuvent proposer des options d'itinéraire réellement différentes.

Applications principales

Planificateurs locaux pour robots mobiles qui conservent des itinéraires alternatifs autour des obstacles
Explication des sauts du coût de la solution dans les planificateurs anytime et asymptotiquement optimaux
Choix des estimations initiales pour l'optimisation de trajectoire
Navigation multirobot et en foule, où le côté de passage doit être convenu
Robots attachés par câble, où la classe du câble autour des obstacles limite les chemins atteignables

En pratique

Un robot d'entrepôt utilise un planificateur local qui conserve plusieurs trajectoires candidates, chacune dans une classe d'homotopie différente autour des palettes et des personnes proches. À chaque cycle, il optimise chaque candidate en temps et en dégagement, puis choisit la moins coûteuse. Sans précaution, deux options presque équivalentes amènent le robot à changer de côté d'un cycle à l'autre et à osciller sur place ; l'équipe ajoute donc une hystérésis : une nouvelle classe doit battre la classe actuelle d'une certaine marge avant que le robot ne change d'avis. Elle plafonne aussi le nombre de classes explorées pour que le planificateur respecte son temps de cycle.

Idées reçues

Des chemins homotopes ont des longueurs similaires — l'homotopie est une propriété topologique ; deux chemins de la même classe peuvent avoir des longueurs très différentes
Il y a autant de classes que de façons de contourner les obstacles — faire le tour d'un obstacle à plusieurs reprises crée une infinité de classes
Un optimiseur local trouvera le chemin globalement le plus court avec assez d'itérations — il reste dans la classe de son chemin initial
Les classes d'homotopie et d'homologie sont identiques — l'homologie est plus grossière, et les signatures pratiques comme la H-signature identifient des classes d'homologie

Qui devrait le savoir

Chercheurs en planification de mouvement travaillant sur la planification optimale et multimodale
Ingénieurs en navigation de robots mobiles qui règlent des planificateurs locaux
Praticiens de l'optimisation de trajectoire qui choisissent des initialisations
Étudiants qui étudient la topologie de l'espace de configuration

Technologies associées

H-signature
Planificateur Timed Elastic Band (TEB)
Indice d'enroulement (winding number)
Diagramme de Voronoï
Graphe de visibilité (visibility graph)
CHOMP et TrajOpt

Termes associés

Projets associés

OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines
NeuPAN: Real-time end-to-end planner that maps raw lidar points directly to robot actions