Probabilistic Roadmap

Auch genannt: PRM, probabilistic roadmap method
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

Ein samplingbasierter Bewegungsplaner, der einen wiederverwendbaren Graphen aus zufälligen kollisionsfreien Konfigurationen und den machbaren Pfaden zwischen ihnen aufbaut und Planungsanfragen dann per Graphsuche beantwortet.

Definition

Probabilistic Roadmap (PRM) ist ein samplingbasiertes Verfahren der Bewegungsplanung, das 1996 von Kavraki, Švestka, Latombe und Overmars vorgestellt wurde. Statt den Konfigurationsraum für jede Anfrage neu zu durchsuchen, baut PRM zuerst einen Graphen auf, die Roadmap, der die Zusammenhänge des freien Raums des Roboters erfasst, und beantwortet dann mit diesem Graphen beliebig viele Start-Ziel-Anfragen.

Die Planung hat zwei Phasen. In der Konstruktionsphase sampelt der Planer zufällige Konfigurationen des Roboters, behält die kollisionsfreien als Knoten und versucht, jeden Knoten mit einem einfachen lokalen Planer mit nahegelegenen Knoten zu verbinden, meist einer Geraden im Konfigurationsraum, die in feinen Abständen auf Kollisionen geprüft wird. Erfolgreiche Verbindungen werden zu Kanten. In der Anfragephase werden Start- und Zielkonfiguration mit der Roadmap verbunden, und eine Graphsuche wie der Dijkstra-Algorithmus oder A* findet einen Pfad durch sie.

PRM eignet sich für Mehrfachanfrage-Probleme, bei denen die Umgebung statisch ist und der Roboter viele Bewegungen im selben Raum planen muss, weil die aufwendige Konstruktion der Roadmap nur einmal erfolgt. Es ist probabilistisch vollständig: Wenn ein Pfad existiert, strebt die Wahrscheinlichkeit, dass die Roadmap einen enthält, mit wachsender Zahl der Samples gegen 1.

Seine Hauptschwäche sind enge Durchgänge. Gleichverteilte Zufallssamples landen selten in schmalen Bereichen des freien Raums, sodass die Roadmap Gebiete, die tatsächlich verbunden sind, womöglich nicht verbindet. Um dem zu begegnen, wurden verzerrte Sampling-Strategien entwickelt, etwa das Sampeln nahe an Hindernisgrenzen. PRM* ist eine Variante, die die Verbindungsradien so wählt, dass die Roadmap asymptotisch optimal wird.

Warum es wichtig ist

PRM zeigte, dass Zufallssampling die Bewegungsplanung für Roboter mit vielen Freiheitsgraden praktikabel machen kann, bei denen exakte Verfahren nicht handhabbar sind. Seine Roadmap-Idee bleibt nützlich, wann immer ein Roboter wiederholt in derselben Umgebung arbeitet, etwa in einer festen Industriezelle.

Wichtige Anwendungen

Bewegungsplanung mit Mehrfachanfragen für Roboterarme in festen Arbeitszellen
Pfadplanung für mobile Roboter in statischen Karten
Planung für Systeme mit vielen Freiheitsgraden wie Humanoide und zweiarmige Roboter
Lehre und Benchmarking samplingbasierter Planung

In der Praxis

Teams nutzen PRM typischerweise über OMPL, für die Armplanung oft über MoveIt, wo PRM und PRM* neben baumbasierten Planern wie RRT-Connect stehen. Da sich eine Roadmap speichern und wiederverwenden lässt, passt PRM zu festen Arbeitszellen, in denen sich ein Arm zwischen vielen Posen um dieselben Vorrichtungen bewegt: Die Roadmap wird offline aufgebaut und zur Laufzeit abgefragt, wobei Kollisionsprüfungen nur dort wiederholt werden, wo sich Objekte bewegt haben könnten. Ingenieure passen die Zahl der Samples und den Verbindungsradius an und achten auf nicht verbundene Komponenten in der Roadmap, die meist auf einen engen Durchgang hinweisen, der mehr oder gezielter platzierte Samples braucht.

Häufige Missverständnisse

PRM findet immer einen Pfad, wenn einer existiert — es ist probabilistisch vollständig, daher gilt die Garantie nur im Grenzfall unendlich vieler Samples
PRM ist hauptsächlich für 2D-Karten — sein Haupteinsatz liegt in hochdimensionalen Konfigurationsräumen wie dem Gelenkraum eines Arms
Eine Roadmap bleibt für immer gültig — bewegen sich Hindernisse, müssen betroffene Kanten erneut geprüft oder die Roadmap neu aufgebaut werden

Wer das wissen sollte

Ingenieure für Bewegungsplanung
Integratoren von Industrieroboterzellen
Forschende in der Manipulation
Robotikstudierende, die samplingbasierte Planung lernen

Videos

Modern Robotics, Chapter 10.5: Sampling Methods for Motion Planning (Part 1 of 2): Northwestern Robotics

Open Source Robotics