Niedrigdimensionale Probleme können mit gitterbasierten Algorithmen gelöst werden, die ein Gitter über dem Konfigurationsraum überlagern, oder mit geometrischen Algorithmen, die die Form und Konnektivität von Cfree berechnen.
Eine exakte Bewegungsplanung für hochdimensionale Systeme unter komplexen Randbedingungen ist rechnerisch nicht möglich. Potentialfeldalgorithmen sind effizient, fallen aber lokalen Minima zum Opfer (eine Ausnahme bilden die harmonischen Potentialfelder). Stichprobenbasierte Algorithmen vermeiden das Problem lokaler Minima und lösen viele Probleme recht schnell.Sie können nicht feststellen, dass kein Pfad vorhanden ist, haben jedoch eine Ausfallwahrscheinlichkeit, die mit zunehmendem Zeitaufwand auf Null sinkt.
Sampling-basierte Algorithmen gelten derzeit als State-of-the-Art für die Bewegungsplanung in hochdimensionalen Räumen und wurden auf Probleme angewendet, die Dutzende oder sogar Hunderte von Dimensionen haben (Robotermanipulatoren, biologische Moleküle, animierte digitale Zeichen und Roboter mit Beinen).
Es gibt den Motion Planning Parallel Algorithmus (A1-A2) zur Objektmanipulation (zum Fangen des Flugobjekts).
Grid-based searchEdit
Grid-basierte Ansätze überlagern ein Raster im Konfigurationsraum und gehen davon aus, dass jede Konfiguration mit einem Gitterpunkt identifiziert wird. An jedem Gitterpunkt darf sich der Roboter zu benachbarten Gitterpunkten bewegen, solange die Linie zwischen ihnen vollständig in Cfree enthalten ist (dies wird mit Kollisionserkennung getestet). Dies diskretisiert die Menge der Aktionen, und Suchalgorithmen (wie A *) werden verwendet, um einen Pfad vom Start zum Ziel zu finden.
Diese Ansätze erfordern die Einstellung einer Rasterauflösung. Die Suche ist mit gröberen Gittern schneller, aber der Algorithmus findet keine Pfade durch enge Teile von Cfree. Darüber hinaus wächst die Anzahl der Punkte auf dem Gitter exponentiell in der Konfigurationsraumdimension, was sie für hochdimensionale Probleme ungeeignet macht.
Herkömmliche gitterbasierte Ansätze erzeugen Pfade, deren Kursänderungen auf ein Vielfaches eines bestimmten Basiswinkels beschränkt sind, was häufig zu suboptimalen Pfaden führt. Beliebige Winkelpfadplanungsansätze finden kürzere Pfade, indem Informationen entlang von Gitterkanten propagiert werden (um schnell zu suchen), ohne ihre Pfade auf Gitterkanten zu beschränken (um kurze Pfade zu finden).
Gitterbasierte Ansätze müssen häufig wiederholt suchen, wenn sich beispielsweise das Wissen des Roboters über den Konfigurationsraum ändert oder sich der Konfigurationsraum selbst während der Pfadverfolgung ändert. Inkrementelle heuristische Suchalgorithmen planen schnell neu, indem sie Erfahrungen mit den vorherigen ähnlichen Pfadplanungsproblemen verwenden, um die Suche nach dem aktuellen zu beschleunigen.
Intervallbasierte Sucheedit
Diese Ansätze ähneln rasterbasierten Suchansätzen, mit der Ausnahme, dass sie anstelle eines Rasters ein Raster erzeugen, das den gesamten Konfigurationsraum abdeckt. Die Pflasterung wird in zwei Unterspäne X zerlegt-,X+ mit Boxen gemacht, so dass X- ⊂ Cfree ⊂ X+. Charakterisierung von Cfree-Mengen zur Lösung eines Mengeninversionsproblems. Die Intervallanalyse könnte somit verwendet werden, wenn Cfree nicht durch lineare Ungleichungen beschrieben werden kann, um ein garantiertes Ergebnis zu erzielen.
Der Roboter darf sich somit frei in X- bewegen und kann nicht außerhalb von X+ gehen. Zu beiden Unterpunkten wird ein Nachbargraph erstellt und Pfade können mit Algorithmen wie Dijkstra oder A * gefunden werden. Wenn ein Pfad in X- machbar ist, ist er auch in Cfree machbar. Wenn in X + kein Pfad von einer Anfangskonfiguration zum Ziel vorhanden ist, haben wir die Garantie, dass in Cfree kein realisierbarer Pfad vorhanden ist. Was den rasterbasierten Ansatz betrifft, so ist der Intervallansatz für hochdimensionale Probleme ungeeignet, da die Anzahl der zu generierenden Boxen exponentiell in Bezug auf die Dimension des Konfigurationsraums wächst.
Veranschaulicht wird dies durch die drei Figuren rechts, wo sich ein Haken mit zwei Freiheitsgraden von links nach rechts bewegen muss, wobei zwei horizontale kleine Segmente vermieden werden.
Bewegung von der Anfangskonfiguration (blau) bis zur endgültigen Konfiguration des Hakens unter Vermeidung der beiden Hindernisse (rote Segmente). Die linke untere Ecke des Hakens muss auf der horizontalen Linie bleiben, wodurch der Haken zwei Freiheitsgrade hat.
Zerlegung mit Boxen, die den Konfigurationsraum abdecken: Das Unterfenster X- ist die Vereinigung aller roten Kästchen und das Unterfenster X + ist die Vereinigung der roten und grünen Kästchen. Der Pfad entspricht der oben dargestellten Bewegung.
Diese Zahl entspricht dem gleichen Pfad wie oben, wird jedoch mit viel weniger Feldern erhalten.Der Algorithmus vermeidet das Halbieren von Feldern in Teilen des Konfigurationsraums, die das Endergebnis nicht beeinflussen.
Die Zerlegung mit Subpavings unter Verwendung der Intervallanalyse ermöglicht es auch, die Topologie von Cfree zu charakterisieren, z. B. die Anzahl der verbundenen Komponenten zu zählen.
Geometrische Algorithmenbearbeiten
Punktroboter unter polygonalen Hindernissen
- Sichtbarkeitsgraph
- Zellzerlegung
Objekte zwischen Hindernissen übersetzen
- Minkowski-Summe
Den Weg aus einem Gebäude finden
- Am weitesten entfernte Strahlenspur
Bei einem Strahlenbündel um die aktuelle Position, dessen Länge auf eine Wand trifft, bewegt sich der Roboter in Richtung des längsten Strahls, es sei denn, es wird eine Tür identifiziert. Ein solcher Algorithmus wurde zur Modellierung des Notausgangs aus Gebäuden verwendet.
Künstliche Potentialfeldebearbeiten
Ein Ansatz besteht darin, die Konfiguration des Roboters als einen Punkt in einem Potentialfeld zu behandeln, der die Anziehung zum Ziel und die Abstoßung von Hindernissen kombiniert. Die resultierende Trajektorie wird als Pfad ausgegeben. Dieser Ansatz hat den Vorteil, dass die Trajektorie mit wenig Rechenaufwand erzeugt wird. Sie können jedoch in lokalen Minima des Potentialfeldes gefangen werden und keinen Pfad finden oder einen nicht optimalen Pfad finden. Die künstlichen Potentialfelder können als Kontinuumsgleichungen ähnlich wie elektrostatische Potentialfelder behandelt werden (wobei der Roboter wie eine Punktladung behandelt wird), oder die Bewegung durch das Feld kann mithilfe einer Reihe sprachlicher Regeln diskretisiert werden.Eine Navigationsfunktion oder eine probabilistische Navigationsfunktion sind Arten von künstlichen Potentialfunktionen, die die Qualität haben, keine Minimalpunkte außer dem Zielpunkt zu haben.
Sampling-basierte Algorithmenbearbeiten
Sampling-basierte Algorithmen repräsentieren den Konfigurationsraum mit einer Roadmap von abgetasteten Konfigurationen.Ein grundlegender Algorithmus abtastet N Konfigurationen in C und behält die in Cfree als Meilensteine zu verwenden. Anschließend wird eine Roadmap erstellt, die zwei Meilensteine P und Q verbindet, wenn das Liniensegment PQ vollständig in Cfree ist. Auch hier wird die Kollisionserkennung verwendet, um die Aufnahme in Cfree zu testen. Um einen Pfad zu finden, der S und G verbindet, werden sie der Roadmap hinzugefügt. Wenn ein Pfad in der Roadmap S und G verknüpft, ist der Planer erfolgreich und gibt diesen Pfad zurück. Wenn nicht, ist der Grund nicht eindeutig: Entweder gibt es keinen Pfad in Cfree oder der Planer hat nicht genügend Meilensteine erstellt.
Diese Algorithmen eignen sich gut für hochdimensionale Konfigurationsräume, da ihre Laufzeit im Gegensatz zu kombinatorischen Algorithmen nicht (explizit) exponentiell von der Dimension von C abhängt. Sie sind probabilistisch vollständig, dh die Wahrscheinlichkeit, dass sie eine Lösung ergeben, nähert sich 1, wenn mehr Zeit aufgewendet wird. Sie können jedoch nicht feststellen, ob keine Lösung existiert.
Bei grundlegenden Sichtbarkeitsbedingungen auf Cfree wurde nachgewiesen, dass mit zunehmender Anzahl von Konfigurationen N die Wahrscheinlichkeit, dass der obige Algorithmus eine Lösung findet, exponentiell gegen 1 geht. Es ist möglich, einen hochdimensionalen Raum mit „guter“ Sichtbarkeit oder einen niedrigdimensionalen Raum mit „schlechter“ Sichtbarkeit zu haben. Der experimentelle Erfolg von stichprobenbasierten Methoden legt nahe, dass die am häufigsten gesehenen Räume eine gute Sichtbarkeit aufweisen.
Es gibt viele Varianten dieses Grundschemas:
- Es ist normalerweise viel schneller, nur Segmente zwischen nahe gelegenen Meilensteinpaaren zu testen, als alle Paare.
- Ungleichmäßige Stichprobenverteilungen versuchen, weitere Meilensteine in Bereichen zu platzieren, die die Konnektivität der Roadmap verbessern.
- Quasizufällige Stichproben erzeugen typischerweise eine bessere Abdeckung des Konfigurationsraums als pseudozufällige, obwohl einige neuere Arbeiten argumentieren, dass der Effekt der Zufallsquelle im Vergleich zum Effekt der Stichprobenverteilung minimal ist.
- Verwendet lokale Stichproben, indem ein direktionaler Markov Chain Monte Carlo Random Walk mit einer lokalen Vorschlagsverteilung durchgeführt wird.
- Es ist möglich, die Anzahl der Meilensteine, die zur Lösung eines bestimmten Problems erforderlich sind, erheblich zu reduzieren, indem gekrümmte Augenblicke zugelassen werden (z. B. durch Kriechen auf den Hindernissen, die den Weg zwischen zwei Meilensteinen versperren).
- Wenn nur eine oder wenige Planungsabfragen benötigt werden, ist es nicht immer notwendig, eine Roadmap des gesamten Raums zu erstellen. Baum wachsende Varianten sind in der Regel schneller für diesen Fall (Single-Query-Planung). Roadmaps sind immer noch nützlich, wenn viele Abfragen auf demselben Space durchgeführt werden sollen (Multi-Query-Planung)
- A *
- D*
- Zufallsbaum schnell erkunden
- Probabilistische Roadmap