Hybrid A*
- Auch genannt: Hybrid A-star, hybrid-state A*
- Kategorie: Planning & manipulation › Motion planning
- Schlagwörter: path-planning, graph-search, autonomous-driving, nonholonomic, parking
Eine Variante der A*-Suche für autoähnliche Roboter, die Knoten durch Simulation fahrbarer Lenkbewegungen im kontinuierlichen Zustand expandiert und dabei mit einem groben (x, y, Fahrtrichtung)-Raster beschneidet.
Definition
Hybrid A ist ein suchbasierter Pfadplaner für Fahrzeuge mit nichtholonomen Zwangsbedingungen, den Dolgov, Thrun, Montemerlo und Diebel für Stanfords Beitrag zur DARPA Urban Challenge 2007 einführten, wo er Parkplätze und andere unstrukturierte Bereiche übernahm. Wie das Standard-A führt er eine offene Liste, die nach Kosten plus Heuristik geordnet ist. Der Unterschied liegt in der Darstellung der Zustände. Der Suchraum wird in Zellen über Position und Fahrtrichtung unterteilt, aber jeder Knoten behält eine exakte kontinuierliche Pose. Ein Knoten wird expandiert, indem das Fahrzeug, meist mit einem kinematischen Fahrradmodell**, über einen kurzen Bogen bei einigen Lenkwinkeln simuliert wird, etwa voll links, geradeaus und voll rechts, vorwärts und, falls erlaubt, rückwärts. Eine neue Pose wird nur behalten, wenn ihre Zelle nicht bereits mit geringeren Kosten erreicht wurde.
Da jede Kante eine simulierte Bewegung ist, ist der resultierende Pfad konstruktionsbedingt fahrbar, was ein einfaches Raster-A auf Zellmittelpunkten nicht leisten kann. Der Preis ist, dass das Beschneiden nach Zellen Zustände verwirft, die zu einer Lösung hätten führen können; der Planer ist daher im strengen Sinne weder vollständig noch optimal. Grobe Zellen machen ihn schnell, können aber dazu führen, dass er enge Manöver verpasst. Die ursprüngliche Methode verwendete zwei zulässige Heuristiken und nahm die größere: die Länge des kürzesten Pfades eines Autos ohne Hindernisse, etwa eines Reeds–Shepp- oder Dubins-Fahrzeug**-Pfades, und den kürzesten hindernisbewussten Pfad eines Roboters, der auf der Stelle drehen kann, aus einer 2D-Suche auf dem Raster. Außerdem versuchte sie periodisch, den aktuellen Knoten mit einer Reeds–Shepp-Kurve direkt mit dem Ziel zu verbinden, was analytische Expansion (analytic expansion) heißt und der Suche hilft, eine exakte Zielpose zu erreichen.
Der Rohpfad folgt den diskreten Lenkentscheidungen und verläuft daher leicht im Zickzack. Das ursprüngliche System glättete ihn mit einem gradientenbasierten Optimierer, der Abstand, Krümmung und Glätte gegeneinander abwog, und interpolierte ihn dann für den Folgeregler. Hybrid A unterscheidet sich von der Zustandsgitter-Planung (state lattice), die feste Gitterpunkte mit vorberechneten Bewegungsprimitiven** verbindet, und von Planern im Frenet-Koordinatensystem, die eine Referenzspur voraussetzen.
Warum es wichtig ist
Hybrid A* gehört zu den am häufigsten eingesetzten Planern für autoähnliche Roboter auf Parkplätzen, Betriebshöfen und anderen Flächen ohne Fahrspuren. Er zeigt einen praktischen Weg, die Geschwindigkeit der Rastersuche mit Pfaden zu verbinden, die die Wendegrenzen eines Fahrzeugs einhalten, und seine Struktur findet sich in vielen quelloffenen Fahr-Stacks.
Wichtige Anwendungen
- Automatisches Parken und Valet-Manöver
- Rangieren von Lkw, Schleppern und Anhängern auf Betriebshöfen und in Depots
- Autoähnliche Roboter in Lagern, auf Höfen und Baustellen
- Planung in unstrukturierten Bereichen von Stacks für autonomes Fahren
- Pfadplanung für Gelände- und Bergbaufahrzeuge
In der Praxis
Ein autonomer Schlepper muss rückwärts in eine Ladebucht fahren. Der Planer diskretisiert den Hof in Positionszellen und Fahrtrichtungsintervalle, expandiert Knoten mit einigen Lenkwinkeln vorwärts und rückwärts anhand des Fahrradmodells und prüft an jeder simulierten Pose die vollständige Fahrzeugkontur (footprint) auf Kollisionen. Alle paar Expansionen versucht er eine direkte Reeds–Shepp-Verbindung zur Pose der Bucht. Sobald ein Pfad gefunden ist, wird er auf Krümmung und Abstand geglättet, erneut auf Kollisionen geprüft und mit einem Geschwindigkeitsprofil versehen, bevor ein Bahnfolgeregler ihn abfährt. Wenn der Planer an engen Stellen scheitert, verkleinert das Team zuerst die Zellgröße oder fügt weitere Lenkwinkel hinzu, bevor es irgendetwas anderes ändert.
Häufige Missverständnisse
- Hybrid A ist gewöhnliches A auf einem Raster — Knoten speichern kontinuierliche Posen, die durch simulierte Lenkbewegungen erreicht werden, und das Raster beschneidet nur Duplikate
- Seine Pfade können wegen des Rasters kinematisch unzulässig sein — Kanten sind simulierte Fahrzeugbewegungen, daher bleibt die Zulässigkeit erhalten; was das Raster kostet, sind Vollständigkeit und Optimalität
- Hybrid A* liefert den kürzesten Pfad — Zellbeschneidung und begrenzte Lenkoptionen machen das Ergebnis zu einer Näherung, auf die meist eine Glättung folgt
- Er plant die vollständige Trajektorie mit Geschwindigkeiten — er plant einen geometrischen Pfad; Geschwindigkeitsprofile und Dynamik werden danach behandelt
Wer das wissen sollte
- Ingenieure für autonomes Fahren, die an Parken und unstrukturierten Bereichen arbeiten
- Entwickler mobiler Roboter mit autoähnlichen oder Ackermann-Plattformen
- Studierende der Bewegungsplanung, die suchbasierte Planung lernen
- Ingenieure der Feldrobotik in Landwirtschaft, Bergbau und Logistik
Verwandte Technologien
- A*-Suche
- Reeds–Shepp-Kurven
- Zustandsgitter-Planer (State Lattice Planner)
- Voronoi-Feld (Voronoi field)
- Pfadglättung
- Pure-Pursuit- und Stanley-Regler
Verwandte Begriffe
- Nonholonomic Constraint
- Dubins Car
- Bicycle model
- Motion Primitive
- Configuration Space
- Frenet Frame Planning
Verwandte Projekte
- 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