Hybrid A*
- Detto anche: Hybrid A-star, hybrid-state A*
- Categoria: Planning & manipulation › Motion planning
- Tag: path-planning, graph-search, autonomous-driving, nonholonomic, parking
Una variante della ricerca A* per robot di tipo automobilistico che espande i nodi simulando movimenti di sterzata ammissibili in uno stato continuo, mentre pota con una griglia grossolana di (x, y, orientamento).
Definizione
Hybrid A è un pianificatore di percorso basato sulla ricerca per veicoli con vincoli anolonomi, presentato da Dolgov, Thrun, Montemerlo e Diebel per la partecipazione di Stanford alla DARPA Urban Challenge del 2007, dove gestiva parcheggi e altre aree non strutturate. Come l'A standard, mantiene una lista aperta ordinata per costo più euristica. La differenza sta nel modo in cui sono rappresentati gli stati. Lo spazio di ricerca è diviso in celle su posizione e orientamento, ma ogni nodo conserva una posa continua esatta. Un nodo viene espanso simulando il veicolo, di solito con un modello a bicicletta** cinematico, lungo un breve arco con pochi angoli di sterzata, come tutto a sinistra, dritto e tutto a destra, in marcia avanti e, se consentito, in retromarcia. Una nuova posa viene mantenuta solo se la sua cella non è già stata raggiunta con un costo inferiore.
Poiché ogni arco è un movimento simulato, il percorso risultante è percorribile per costruzione, cosa che un semplice A su griglia sui centri delle celle non può garantire. Il prezzo è che la potatura per celle scarta stati che avrebbero potuto portare a una soluzione, per cui il pianificatore non è né completo né ottimo in senso stretto; celle grossolane lo rendono veloce ma possono fargli perdere manovre strette. Il metodo originale usava due euristiche ammissibili e prendeva la maggiore: la lunghezza del percorso più breve per un'auto senza ostacoli, come un percorso di Reeds–Shepp o dell'auto di Dubins**, e il percorso più breve che tiene conto degli ostacoli per un robot in grado di ruotare sul posto, ottenuto da una ricerca 2D sulla griglia. Inoltre tentava periodicamente di collegare il nodo corrente direttamente all'obiettivo con una curva di Reeds–Shepp, la cosiddetta espansione analitica, che aiuta la ricerca a raggiungere una posa obiettivo esatta.
Il percorso grezzo segue le scelte di sterzata discrete, quindi procede leggermente a zig-zag. Il sistema originale lo levigava con un ottimizzatore basato sul gradiente che bilanciava distanza dagli ostacoli, curvatura e regolarità, e poi lo interpolava per il controllore di inseguimento. Hybrid A si distingue dalla pianificazione a reticolo di stati, che collega punti fissi del reticolo con primitive di movimento** precalcolate, e dai pianificatori nel riferimento di Frenet, che presuppongono una corsia di riferimento.
Perché è importante
Hybrid A* è uno dei pianificatori più usati per robot di tipo automobilistico in parcheggi, piazzali e altri spazi senza corsie. Mostra un modo pratico per unire la velocità della ricerca su griglia a percorsi che rispettano i limiti di sterzata di un veicolo, e la sua struttura compare in molti stack di guida open source.
Applicazioni principali
- Parcheggio automatizzato e manovre di valet parking
- Manovre di camion, trattori di traino e rimorchi in piazzali e depositi
- Robot di tipo automobilistico in magazzini, aziende agricole e cantieri
- Pianificazione nelle aree non strutturate degli stack di guida autonoma
- Pianificazione del percorso per veicoli fuoristrada e minerari
In pratica
Un trattore di traino autonomo deve entrare in retromarcia in una baia di carico. Il pianificatore discretizza il piazzale in celle di posizione e intervalli di orientamento, espande i nodi con pochi angoli di sterzata in avanti e all'indietro usando il modello a bicicletta e controlla le collisioni dell'intero ingombro del veicolo in ogni posa simulata. Ogni poche espansioni tenta un collegamento diretto di Reeds–Shepp alla posa della baia. Una volta trovato un percorso, questo viene levigato per curvatura e distanza dagli ostacoli, ricontrollato per le collisioni e dotato di un profilo di velocità prima che un controllore di inseguimento del percorso lo esegua. Quando il pianificatore fallisce nei punti stretti, il team per prima cosa riduce la dimensione delle celle o aggiunge altri angoli di sterzata, prima di cambiare qualsiasi altra cosa.
Idee sbagliate comuni
- Hybrid A è un normale A su una griglia — i nodi memorizzano pose continue raggiunte con movimenti di sterzata simulati, e la griglia serve solo a potare i duplicati
- I suoi percorsi possono essere cinematicamente non ammissibili a causa della griglia — gli archi sono movimenti simulati del veicolo, quindi l'ammissibilità è garantita; ciò che la griglia costa è la completezza e l'ottimalità
- Hybrid A* fornisce il percorso più breve — la potatura per celle e le poche scelte di sterzata rendono il risultato approssimato, di solito seguito da una levigatura
- Pianifica la traiettoria completa con le velocità — pianifica un percorso geometrico; profili di velocità e dinamica vengono gestiti dopo
Chi dovrebbe saperlo
- Ingegneri della guida autonoma che lavorano su parcheggio e aree non strutturate
- Sviluppatori di robot mobili con piattaforme di tipo automobilistico o Ackermann
- Studenti di pianificazione del movimento che studiano la pianificazione basata sulla ricerca
- Ingegneri di field robotics in agricoltura, attività minerarie e logistica
Tecnologie correlate
- Ricerca A (A search)
- Curve di Reeds–Shepp
- Pianificatore a reticolo di stati (state lattice planner)
- Campo di Voronoi (Voronoi field)
- Levigatura del percorso (path smoothing)
- Controllori Pure Pursuit e Stanley
Termini correlati
- Nonholonomic Constraint
- Dubins Car
- Bicycle model
- Motion Primitive
- Configuration Space
- Frenet Frame Planning
Progetti correlati
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
- Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots
- Fields2Cover: Coverage path planning library for autonomous agricultural vehicles
- Vision Pilot: Autoware Foundation's open-source L2 ADAS stack from a single camera