Homotopy Class

• Detto anche: homotopy class of paths
• Categoria: Planning & manipulation › Motion planning
• Tag: motion-planning, topology, trajectory-optimization, mobile-navigation

Un insieme di percorsi con la stessa partenza e lo stesso obiettivo che possono essere deformati con continuità l'uno nell'altro senza attraversare un ostacolo, come tutti i percorsi che passano a sinistra di un dato pilastro.

Definizione

Due percorsi con gli stessi punti di partenza e di arrivo sono omotopi (homotopic) se uno può essere deformato con continuità nell'altro mentre gli estremi restano fissi e ogni percorso intermedio resta nello spazio libero. Questa relazione divide tutti i percorsi possibili in classi di equivalenza, chiamate classi di omotopia (homotopy classes). In un piano con un ostacolo tra partenza e obiettivo, i percorsi che passano alla sua sinistra formano una classe e quelli che passano alla sua destra ne formano un'altra; i percorsi che girano attorno all'ostacolo una o più volte prima di raggiungere l'obiettivo formano ulteriori classi, per cui anche un solo ostacolo produce infinite classi, distinte dal loro numero di avvolgimento. Ogni ostacolo in più moltiplica le possibilità.

Il concetto conta perché la maggior parte degli ottimizzatori di percorso lavora localmente. Gli ottimizzatori di traiettoria basati sul gradiente e le bande elastiche deformano un percorso per renderlo più corto o più regolare, ma non possono spingerlo attraverso un ostacolo, quindi trovano solo il percorso migliore all'interno della classe in cui sono partiti. I pianificatori globali decidono quale classe usare, spesso implicitamente. Un pianificatore basato sul campionamento come RRT può trovare prima un percorso attraverso un varco e scoprire in seguito un percorso più breve attraverso un altro, il che si manifesta come un calo improvviso del costo del percorso invece che come un miglioramento graduale. I pianificatori che tengono conto dell'omotopia rendono esplicito tutto questo seguendo diverse classi in parallelo e ottimizzando il percorso migliore in ciascuna.

In pratica, i pianificatori usano spesso un invariante calcolabile al posto dell'omotopia stessa. Per problemi planari, una H-signature o un conteggio dell'angolo di avvolgimento attorno a ciascun ostacolo indica da quale lato di ciascun ostacolo passa un percorso, il che a rigore identifica la classe di omologia, correlata ma più grossolana. Nello spazio delle configurazioni a più dimensioni di un braccio, le classi esistono ancora ma sono difficili da enumerare, per cui se ne parla soprattutto per robot mobili, veicoli e problemi planari.

Perché è importante

Sapere a quale classe di omotopia appartiene un percorso spiega perché un ottimizzatore locale resta bloccato su una lunga deviazione, perché il costo di un pianificatore salta all'improvviso e perché un robot può oscillare tra il passare un ostacolo a sinistra e a destra. I pianificatori che ragionano sulle classi evitano questi errori e possono offrire opzioni di percorso davvero diverse.

Applicazioni principali

• Pianificatori locali per robot mobili che mantengono percorsi alternativi attorno agli ostacoli
• Spiegare i cambi a gradino nel costo della soluzione nei pianificatori anytime e asintoticamente ottimi
• Scegliere le stime iniziali per l'ottimizzazione della traiettoria
• Navigazione multi-robot e tra la folla, dove il lato di passaggio deve essere concordato
• Robot vincolati da un cavo, dove la classe del cavo attorno agli ostacoli limita i percorsi raggiungibili

In pratica

Un robot di magazzino usa un pianificatore locale che mantiene diverse traiettorie candidate, ciascuna in una diversa classe di omotopia attorno a pallet e persone vicini. A ogni ciclo ottimizza ogni candidata per tempo e distanza dagli ostacoli, poi sceglie la più economica. Senza accortezze, due opzioni quasi equivalenti fanno cambiare lato al robot da un ciclo all'altro e lo fanno oscillare sul posto, quindi il team aggiunge un'isteresi: una nuova classe deve battere quella attuale di un certo margine prima che il robot cambi idea. Limitano anche il numero di classi esplorate perché il pianificatore resti entro il suo tempo di ciclo.

Idee sbagliate comuni

• I percorsi omotopi hanno lunghezze simili — l'omotopia è una proprietà topologica; due percorsi nella stessa classe possono differire molto in lunghezza
• Ci sono solo tante classi quanti sono i modi di aggirare gli ostacoli — girare ripetutamente attorno a un ostacolo crea infinite classi
• Un ottimizzatore locale troverà il percorso globalmente più breve con abbastanza iterazioni — resta nella classe del suo percorso iniziale
• Le classi di omotopia e di omologia sono la stessa cosa — l'omologia è più grossolana, e le firme pratiche come la H-signature identificano classi di omologia

Chi dovrebbe saperlo

• Ricercatori di pianificazione del movimento che lavorano sulla pianificazione ottima e multimodale
• Ingegneri della navigazione di robot mobili che regolano i pianificatori locali
• Professionisti dell'ottimizzazione della traiettoria che scelgono le inizializzazioni
• Studenti che studiano la topologia dello spazio delle configurazioni

Tecnologie correlate

• H-signature
• Pianificatore Timed Elastic Band (TEB)
• Numero di avvolgimento (winding number)
• Diagramma di Voronoi
• Grafo di visibilità (visibility graph)
• CHOMP e TrajOpt

Termini correlati

• Configuration Space
• Elastic band
• RRT*
• Anytime Motion Planning
• Narrow Passage Problem
• Motion Planning

Progetti correlati

• 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