Narrow Passage Problem

Auch genannt: narrow passages
Kategorie: Planning & manipulation › Motion planning
Schlagwörter: motion-planning, sampling-based-planning, configuration-space, planner-failure-modes

Die Schwierigkeit samplingbasierter Planer mit dünnen Korridoren im freien Raum: Zufällige Samples landen selten darin, sodass die Planung langsamer wird oder sich auf einen langen Umweg festlegt.

Definition

Das Problem enger Passagen (narrow passage problem) ist die bekannteste Schwäche samplingbasierter Bewegungsplaner wie Probabilistic Roadmaps und Rapidly-exploring Random Trees. Diese Planer erkunden den Konfigurationsraum, indem sie zufällige Samples ziehen und sie durch kurze kollisionsfreie Bewegungen verbinden. Führt die einzige Route oder die kürzeste durch einen Bereich des freien Raums, der in einer oder mehreren Richtungen dünn ist, so ist die Wahrscheinlichkeit, dass ein gleichverteiltes Sample darin landet, proportional zu seinem Volumen, und das ist winzig. Selbst ein Sample, das darin landet, lässt sich womöglich nicht mit Nachbarn auf beiden Seiten verbinden. Der Planer braucht dann sehr viele Samples, um die Passage zu finden, oder er findet zuerst eine längere Route.

Der Effekt wächst mit der Dimension. Eine Lücke, die auf einer 2D-Karte etwas breiter als der Roboter ist, lässt sich leicht sampeln. Bei einem Arm mit 7 Gelenken, der in ein Regal greift, einen Stift in ein Loch steckt oder ein Teil durch eine Vorrichtung bewegt, können die gültigen Konfigurationen dagegen einen dünnen Splitter in einem Raum mit vielen Dimensionen bilden, und ihr Volumenanteil wird extrem klein. Theoretische Analysen samplingbasierter Planer, etwa die Expansivität (expansiveness) und die ε-Güte (ε-goodness) des freien Raums, machen diese Abhängigkeit explizit: Die Konvergenzgarantien gelten weiterhin, aber die Zahl der benötigten Samples steigt stark an, wenn die Passagen enger werden.

Viele Abhilfen lenken das Sampling auf die Ränder und Lücken des freien Raums. Gauß-Sampling behält Samples nahe an Hindernisoberflächen, der Brückentest behält die Mittelpunkte kurzer Strecken, deren beide Enden in Kollision sind, hindernisbasierte und Mittelachsen-Sampler (medial axis) schieben Samples zum Rand oder zur Mitte von Korridoren, und gelernte Sampler sagen voraus, wo nützliche Konfigurationen liegen. Andere Methoden erweitern den freien Raum vorübergehend, indem sie Hindernisse schrumpfen lassen oder Nebenbedingungen lockern, planen im leichteren Problem und reparieren dann den Pfad. In der Ingenieurpraxis funktioniert es oft gut, gut platzierte Zwischenwegpunkte oder Zielbereiche zu wählen.

Warum es wichtig ist

Viele reale Aufgaben sind Probleme enger Passagen: Einfügen, Greifen in vollgestellte Regale und Behälter sowie das Durchfahren von Türen oder engen Vorrichtungen. Wer das Problem erkennt, kann Zeitüberschreitungen und Umwege des Planers erklären und findet Lösungen im Sampler, statt einfach das Zeitlimit zu erhöhen.

Wichtige Anwendungen

Peg-in-Hole-Einfügen und Montage in Vorrichtungen
Armbewegungen in Regale, Schränke und Behälter
Mobile Roboter und Fahrzeuge, die durch Türen und enge Korridore fahren
Demontage- und Wartbarkeitsanalyse mechanischer Teile
Benchmarking und Entwurf von Sampling-Strategien für Bewegungsplaner

In der Praxis

Ein Arm muss ein Teil mit wenigen Millimetern Spiel auf jeder Seite in eine Vorrichtung setzen. Mit einem gleichverteilten Sampler läuft der Planer oft in eine Zeitüberschreitung oder liefert Pfade, die weit um die Vorrichtung herumschwingen. Das Team bestätigt die Ursache, indem es die Kollisionsnetze leicht verkleinert und sieht, dass die Planung dann schnell wird. Anschließend fügt es eine Pose vor dem Einfügen über der Vorrichtung als Zwischenziel hinzu, stellt die letzte Annäherung auf eine auf Kollisionen geprüfte geradlinige kartesische Bewegung um und ergänzt für die übrige freie Bewegung einen Sampler, der Samples nahe an Hindernisoberflächen konzentriert. Die Planungszeit sinkt, und die Umwege verschwinden.

Häufige Missverständnisse

Eine enge Passage ist eine physisch schmale Lücke — sie ist eng im Konfigurationsraum; auch eine breite Tür kann für einen langen Gegenstand, der genau gedreht werden muss, eine enge Passage sein
Mehr Zeit löst das Problem immer — die benötigte Zahl an Samples kann mit Dimension und Enge stark wachsen, daher helfen besseres Sampling oder eine Zerlegung meist mehr
Probabilistische Vollständigkeit bedeutet, dass der Planer die Passage schnell findet — Vollständigkeit verspricht nur, dass er irgendwann Erfolg hat
Nur samplingbasierte Planer sind davon betroffen — auch Rastersuche und Optimierung haben mit dünnen Bereichen freien Raums Probleme, durch Auflösungsgrenzen oder schlechte Anfangsschätzungen

Wer das wissen sollte

Ingenieure für Bewegungsplanung, die OMPL, MoveIt oder ähnliche Bibliotheken nutzen
Manipulationsingenieure, die an Einfüge- und Montageaufgaben arbeiten
Forscher, die Sampling-Strategien für Planer entwickeln
Studierende, die samplingbasierte Planung studieren

Open Source Robotics