Einführung in die Regelungstechnik: Pfadplanung – A*, Dijkstra, RRT, RRT* und PRM

Contents — find the section you need

Die Bewegung eines Roboters vom Start zum Ziel bedeutet selten, eine gerade Linie zu zeichnen. Ein praktikabler Plan muss Wände, Durchgangsbreite, Roboter-Aufstandsfläche, Wendegrenzen, Lokalisierungsunsicherheiten, veraltete Karten, sich bewegende Personen und den Bremsweg berücksichtigen. Die Pfadplanung legt das Ziel fest; Trajektoriengenerierung und -steuerung bestimmen, wie dieser Weg unter dynamischen Bedingungen befolgt wird. Ein sicherer Stack trennt diese Verantwortlichkeiten, teilt aber gleichzeitig ihre Grenzen.

Diese Einführung vergleicht Grid-Dijkstra und A mit kontinuierlichen RRT-, RRT- und PRM-Verfahren. Sie erklärt Hindernisaufblähung, Heuristiken, Sampling, Komplexität, SLAM/Nav2-Integration, Implementierungsprüfungen und unabhängiges Sicherheitsverhalten. Weiterführende Informationen finden Sie in Visual SLAM Primer, ROS 2 Primer und Sensor Fusion Primer.

Praktische Schlussfolgerung

Dijkstra garantiert einen kürzesten Pfad auf einem nichtnegativen gewichteten Graphen, expandiert aber in Richtungen, die nicht mit dem Ziel zusammenhängen. A* steuert die Expansion mit einer zulässigen Heuristik und behält dabei die gleiche Optimalität bei.
RRT findet in hochdimensionalen kontinuierlichen Räumen tendenziell schnell einen zulässigen Pfad. RRT* nähert sich mit zunehmender Anzahl an Stichproben einem optimalen Pfad an, wobei zusätzliche Kosten für Nachbarn und Umverdrahtung anfallen. PRM amortisiert die Roadmap-Erstellung über viele Anfragen in einem ausreichend statischen Raum.
Ein kürzester Pfad durch eine nicht aufgeblähte Karte ist ein Kollisionspfad für einen Roboter mit Radius, Lokalisierungsfehler und Stoppdistanz.
Eine zurückgegebene Route ist kein Beweis für Sicherheit. Kartenaktualität, lokale Erfassung, Trackingfehler, dynamische Hindernisse, Neuplanungslatenz und Not-Aus müssen separat behandelt werden.

Definition des freien Raums vor der Algorithmusauswahl

Der Zustandsraum sei $\mathcal X$ , der Hindernisraum $\mathcal X_{obs}$ und der freie Raum $\mathcal X_{free}=\mathcal X\setminus\mathcal X_{obs}$ . Ein Pfad $\sigma:[0,1]\to\mathcal X_{free}$ verbindet $x_s$ mit $x_g$ , wobei $\sigma(0)=x_s,\sigma(1)=x_g$ verwendet wird. Ein Punktroboter in 2D verwendet $x=(x,y)$ ; ein Fahrzeug fügt Richtung $\theta$ , Geschwindigkeit und Lenkung hinzu; ein Manipulator berücksichtigt alle Gelenkwinkel. Die Vereinfachung des Zustands reduziert die Suchkosten, kann aber Kurven erzeugen, die das nachfolgende Fahrzeug nicht bewältigen kann.

Die Hindernisaufblähung wandelt einen endlichen Roboter in eine Punktsuche um, indem sie Hindernisse erweitert. Hierbei sollte $r_{loc}$ ein angegebener Unsicherheitsterm sein, z. B. ein Radius, der für ein definiertes Konfidenzniveau gewählt wird, und nicht ein nicht spezifizierter durchschnittlicher Fehler. Ein konzeptionelles Minimum ist

r_{inflate}=r_{robot}+r_{loc}+r_{safe}

wobei $r_{robot}$ der Körperradius ist, die Lokalisierungsunsicherheit durch den vorherigen Term dargestellt wird und $r_{safe}$ die Nachführ-/Stoppmarge ist. Tatsächlich variiert der Sicherheitsabstand mit der Kartenauflösung, den toten Winkeln der Sensoren, der Geschwindigkeit sich nähernder Objekte und der Bremsleistung. Zu geringer Sicherheitsabstand führt zu Kollisionen; zu großer macht eigentlich mögliche Durchfahrten unmöglich.

Diagramm: Duskcoil, konzeptionell, nicht gemessen. Zellengröße und Aufblähung müssen aus der realen Roboterfläche, Unsicherheit und dem Arbeitsbereich abgeleitet werden.

Gittersuche: Dijkstra und A*

Für den Graphen $G=(V,E)$ mit nichtnegativen Kantenkosten $c(u,v)\ge0$ platziert Dijkstra wiederholt den unbesetzten Knoten mit den niedrigsten bekannten Startkosten. $g(n)$ und entspannt Nachbarn. Nach der Stabilisierung ist sein $g$ -Wert der kürzeste. Bei einem binären Heap ist eine repräsentative Komplexität $O((|V|+|E|)\log|V|)$ . Sie garantiert die kürzeste Graphdistanz, neigt aber ohne Zielkenntnis zu einer breiten Expansion.

A* ordnet Knoten nach:

f(n)=g(n)+h(n)

wobei $h(n)$ eine untere Schranke für die verbleibenden Kosten ist. Eine zulässige Heuristik überschätzt niemals die tatsächlichen verbleibenden Kosten; dann bleibt A* optimal. Die Manhattan-Distanz eignet sich für 4-verbundene Gitter, während die euklidische oder Tschebyscheff-Distanz für 8-verbundene Bewegungen geeignet sein kann. Eine konsistente Heuristik erfüllt zusätzlich $h(n)\le c(n,n')+h(n')$ und reduziert die Re-Expansion.

Gewichtetes A* skaliert die Heuristik um $w>1$ , um schneller eine zulässige Route zu finden, allerdings auf Kosten der Optimalität. Dies kann ein sinnvoller Kompromiss im Betrieb sein. Wenn es explizit angegeben ist. Kantenkosten können neben der Länge auch erhöhtes Hindernisrisiko, Freiraum, Kurvenfahrten, Energieaufwand oder Geländebeschaffenheit kodieren. Das Ergebnis sind dann die minimalen definierten Kosten, nicht unbedingt die minimale geometrische Länge.

Kontinuierliche und hochdimensionale Räume: RRT, RRT*, PRM

Feine Gitter dehnen sich in einem Konfigurationsraum für einen sechsgelenkigen Arm oder einem Fahrzeugpositionsraum aus. RRT zieht Stichproben aus dem freien Raum, findet den nächstgelegenen Baumknoten, steuert eine begrenzte Distanz darauf zu, führt Kollisionsprüfungen durch und fügt einen Knoten hinzu. Es ist probabilistisch vollständig: Mit genügend Stichproben nähert sich die Wahrscheinlichkeit, eine zulässige Route zu finden, eins, wenn eine solche existiert. Es garantiert keine kurze erste Route.

RRT* wählt den kostengünstigsten Elternknoten unter den benachbarten Knoten und verbindet Nachbarn über einen neuen Knoten, wenn dies günstiger ist. Es ist asymptotisch optimal, nicht in endlicher Zeit optimal; Nachbarsuche, Kollisionsprüfungen und das Umverbinden benötigen Rechenzeit. Qualitätsmessung. PRM konzentriert sich auf den operativen Stichtag, anstatt „optimale“ Ergebnisse zu versprechen.

PRM ermittelt freie Konfigurationen und verbindet benachbarte kollisionsfreie Paare zu einer wiederverwendbaren Roadmap. Es ist attraktiv in statischen Fabriken oder Umgebungen mit wiederholten Armabfragen, da die Vorverarbeitung amortisiert werden kann. Dynamische Hindernisse machen Kanten ungültig. Enge Passagen sind für gleichmäßiges Sampling schwierig, daher können hindernis-, pfad- oder aufgabenbasierte Sampling erforderlich sein.

Diagramm: Duskcoil, vereinfacht. Abtastung, Kollisionsprüfung und Konnektivität sind keine Leistungsmessung oder ein endgültiger Produktionsweg.

--- | --- | --- | --- | --- |

SLAM, Nav2 und lokale Planung

SLAM liefert eine Karte und eine Lagebestimmung, aber ein Planer benötigt zeitstempelkorrigierte Transformationen und eine eindeutige Belegungs-/Kostenbedeutung. Schleifenschließung oder Relokalisierung können die Lage im Kartenrahmen verändern; das Weiterverfolgen einer alten Route kann gefährlich sein. Unsicherheiten, Lokalisierungs-Resets und Kartenaktualisierungen müssen in die Neuplanungsregeln einfließen; siehe Visual SLAM Primer.

In einer Nav2-ähnlichen ROS-2-Architektur wählen eine globale Kostenkarte und ein Planer eine großräumige Route, während eine lokale Kostenkarte und ein Controller nahe Hindernisse und die Geschwindigkeit berücksichtigen. Ein globaler A*-Algorithmus kann einen Korridor auswählen; die lokale Ebene muss einer Person ausweichen, anhalten oder einen Umweg fahren. Eine rein lokale Ebene kann in einer Sackgasse gefangen sein. Planer, Controller, Wiederherstellung, Kartenaktualisierungsraten, Fristen und Prioritäten müssen explizit definiert werden. Der in ROS 2 Primer beschriebene ROS 2-Transport bietet keine Echtzeit- oder Sicherheitsgarantie.

Vor dem Einsatz müssen die benötigte Fläche einschließlich Nutzlast, Sichtfeld der Sensoren, Höchstgeschwindigkeit/-verzögerung, Lokalisierungsfehler und Kartenauflösung gemessen werden. Die tatsächliche Durchfahrtshöhe in engen Passagen ist zu prüfen. Geplante Pfade sind auf Kollisionen mit kontinuierlicher Bewegung und Kinematik zu überprüfen: Eine Rasterroute kann zwischen Zellen Kurven fahren, die mit einem Differenzialantrieb, einem Fahrzeug oder einem Roboterarm nicht möglich sind.

Bei dynamischen Hindernissen sind die Aktualität der Erkennung, die relative Geschwindigkeit, der Bremsweg und die Neuplanungszeit zu messen. Die Bewegung darf niemals fortgesetzt werden, nur weil der Planer zu spät reagiert. Unbekannte Personen, Löcher, transparente Hindernisse und Sensorausfälle sind als Sicherheitsfälle zu behandeln und führen nicht automatisch zu freigegebenen Zellen. Bei fehlender Route, unsicherem lokalen Pfad, zu großer Kovarianz, veralteter Karte oder einem Trackingfehler, der den zulässigen Bereich überschreitet, ist die Geschwindigkeit zu reduzieren, der Stopp durchzuführen oder die Kontrolle zu übergeben. Der Not-Aus muss unabhängig von der Planerausgabe funktionieren.

Checkliste für die Implementierung und Sicherheit

Zustandsraum, Footprint, Frames, Kartenauflösung und Bedeutung unbekannter Zellen definieren.
Die Inflation sollte Lokalisierungsfehler, Geschwindigkeit und Bremsweg berücksichtigen; reale Engstellen testen.
Heuristische Zulässigkeit überprüfen oder die bewusst gelockerte Garantie dokumentieren.
Kollisionsprüfung, Zufallsgenerator, Deadline und Nicht-Lösungsverhalten für Sampling-Planer protokollieren.
Neulokalisierung, Kartenänderungen, Sensorausfall, dynamische Hindernisse und Kommunikationsverzögerung einbauen.
Sicheren Stopp und diagnostizierbaren Protokollpfad für No-Route-, Slater-Map- und Tracking-Deviation-Ereignisse überprüfen.

Referenzen

Überprüfen Sie Ihr Verständnis

Kann ein Fahrzeug jeder hindernisfreien Linie folgen?

Die Fahrzeugfläche und die Kurvenbeschränkungen sind wichtig. Ein Pfad zu einem Punkt ist für das Fahrzeug nicht unbedingt realisierbar.

Try it in the browser

Lab Change the conditions in a browser experimentNav2 hat einen Pfad, bewegt sich aber nicht: ein Diagnose-Workflow

Einführung in die Regelungstechnik: Pfadplanung – A, Dijkstra, RRT, RRT und PRM