WikiDer > Bewegungsplanung

Ein Roboterarm schreibt Text auf Papier – die Bewegungen werden mit mehreren Algorithmen berechnet.

Im Robotik ist Bewegungsplanung (Englisch: Bewegungsplanung) es planen von a Bewegung indem man es in kleinere Bewegungen aufteilt. Beispiele bewegen sich a Roboterarm, Objekte manipulieren oder einen Weg von A nach B finden. Im Bereich der Bewegungsplanung gibt es viele Algorithmen die die Informationen berechnen, die für ein gegebenes Problem benötigt werden, um eine Bewegung auszuführen, zum Beispiel welcher Weg zu folgen ist. Diese Informationen können dann verwendet werden, um Motoren des Roboter leiten.

Bewegungsplanung hat Anwendungen in der Robotik, Photogrammetrie, das Automatisierung und Roboter entwerfen mit CAD-Software aber auch andere Bereiche, wie z animieren von Zeichen in virtuelle Welten (wie Computerspiele), Roboterchirurgie, designen die Architektur und studieren Moleküle in dem Bioinformatik.

Überblick

Die Bewegungsplanung umfasst folgende Themen:

• Einen Weg von A nach B finden (Englisch: Wegfindung) ohne auf Gegenstände zu treffen (Englisch: Kollisionserkennung)
• Einen Roboterarm bewegen
• Gegenstände aufheben
• Immobilisieren von Objekten (so dass sie sich nicht mehr bewegen können, oft für Herstellungsprozesse)
• Manipulieren von Objekten (zum Beispiel so, dass sie alle in der gleichen Ausrichtung auf a . sind) Fließband)

Zu den genannten Problemen gibt es auch alle möglichen Varianten, die zusätzliche Einschränkungen erfordern, etwa ein Roboter, der nur vorwärts fahren kann oder Objekte in der Umgebung bewegen. Darüber hinaus muss man sich möglicherweise mit Unsicherheiten wie fehlenden Informationen auseinandersetzen.

Technik

Beispiel für einen Arbeitsbereich.

Konfigurationsraum für einen Punktroboter, der sich bewegen kann. weiß = Ckostenlos, grau = Cobs

Konfigurationsraum für einen rechteckigen Roboter, der sich bewegen kann (der rote Bereich). weiß = Ckostenlos, grau = Cobs (dunkelgrau = die Objekte, hellgrau = Konfigurationen, bei denen der Roboter auf ein Objekt trifft oder den Arbeitsbereich verlässt).

Einen Weg von A nach B zu finden, ohne auf Objekte in der Umgebung zu treffen, ist ein häufiges Problem bei der Bewegungsplanung. Dieses Problem hat alle Arten von Instanzen, wie z. B. ein physischer oder virtueller Roboter, der sich bewegen muss, aber auch die Bewegungen von Atome in einem Molekül.

Konfigurationsraum

sehen Konfigurationsraum für den Hauptartikel zu diesem Thema.

Die Umgebung eines Roboters wird zum Arbeitsplatz (Englisch: Arbeitsplatz), beispielsweise eine zweidimensionale Ebene oder ein dreidimensionaler Raum. Um einen Pfad zu finden, a Konfigurationsraum gebraucht, a Platz in dem alle möglichen Orte und Orientierungen des Roboters (bzw. des zu bewegenden Objekts) dargestellt werden. Ein möglicher Zustand (ein Ort oder eine Orientierung) wird zu einem Aufbau erwähnt.

Zum Beispiel hat ein Roboter, der sich über eine zweidimensionale Ebene bewegen kann, eine Konfiguration, die aus zwei Variablen besteht: (x,y). Wenn der Roboter auch rotieren kann, dann besteht die Konfiguration aus drei Variablen (x, y, ). Die entsprechenden Konfigurationsräume bestehen daher aus allen erlaubten Werten für diese Variablen. Die Anzahl der Maße der Konfigurationsraum hängt somit von den Eigenschaften des Arbeitsraums und des Roboters ab.

Die Objekte in der Umgebung des Roboters bedeuten, dass nicht alle Konfigurationen im Konfigurationsraum gültig sind: Bei bestimmten Konfigurationen kommt der Roboter mit einem Objekt im Arbeitsbereich in Kontakt. Der Konfigurationsraum lässt sich daher in zwei Teile unterteilen: einen zugänglichen Teil, den der Roboter erreichen kann, und einen unzugänglichen Teil, den der Roboter nicht erreichen kann. Diese Teile sind gekennzeichnet mit C_kostenlos und C_obs (von Hindernisse).

Einen Pfad im Arbeitsbereich finden W besteht nun darin, eine Startkonfiguration zu finden so zu einer Zielkonfiguration G im C_kostenlos, der freie Teil des Konfigurationsraums C.

Algorithmen

Es gibt alle Arten von Algorithmen, um einen Pfad im zugänglichen Teil des Konfigurationsraums zu finden.

mit Probenahme

Beispiel für einen Streckenplan (schwarz = Streckenplan, rot = Weg über Streckenplan).

Diese Gruppe von Algorithmen verwendet Proben: Konfigurationen werden ausgewählt (zufällig oder nach bestimmten Kriterien), die als Knoten zu a . hinzugefügt werden Anzahl. In diesem Graphen sind zwei Knoten verbunden, wenn zwischen den zugehörigen Konfigurationen ein (einfacher) Pfad besteht. Indem immer Konfigurationen ausgewählt und wenn möglich mit anderen Konfigurationen verbunden werden, wird ein Diagramm erstellt, das Verbindungen zwischen den Konfigurationen zeigt. Dieser Graph wird auch der Straßenkarte (Englisch: Straßenkarte) erwähnt.

Diese Straßenkarte dient als Autobahnnetz in einem Land, in dem man überall hinkommen kann, indem man zuerst auf die Autobahn fährt, dann auf der Autobahn zu einem Ort in der Nähe des Ziels und dann ein letztes Stück zum Ziel fährt. Mit diesen Arten von Abtastalgorithmen kann man von einer Ausgangskonfiguration zu einer Zielkonfiguration gelangen, indem man zuerst einen Pfad zur Roadmap findet, dann den Roadmap-Konfigurationen folgt und dann einen Pfad zur Zielkonfiguration durchläuft. Um einen Weg in der Straßenkarte zu finden, kann man Algorithmen wie den A*-Algorithmus wenn es Kurzweg-Algorithmus benutzen.

Diese Algorithmen funktionieren gut für hochdimensionale Konfigurationsräume, da die Laufzeit des Algorithmus hängt nicht (explizit) von der Anzahl der Dimensionen des Konfigurationsraums ab.

Je mehr Konfigurationen gewählt werden, desto größer wird der Graph und desto größer ist der Anteil von C_kostenlos die man über die Straßenkarte (und einfache Wege zu und von dieser Straßenkarte) erreichen kann. Die Wahrscheinlichkeit, einen Pfad zu finden, nähert sich 1, wenn mehr Stichproben gewählt werden. Diese Algorithmen können nicht garantieren, dass ein Pfad gefunden wird, wenn er existiert: Wenn kein Pfad gefunden wird, existiert er möglicherweise nicht, aber es kann auch sein, dass nicht genügend Samples ausgewählt wurden.

Im Computerspiele Es verwendet auch eine Straßenkarte zum Bewegen der Fahrzeuge oder Charaktere. In diesem Fall werden die Proben nicht ausgewählt, sondern in der angegeben Niveau bis zum Level-Designer in dem Level-Editor. In diesem Zusammenhang wird kein Konfigurationsraum verwendet, sondern nur ein Graph mit Knoten, die bestimmte Punkte in der Ebene repräsentieren. Diese Punkte sind auch Wegpunkte erwähnt. Ein Grabalgorithmus wird jetzt verwendet, um einen Weg von einem Ort zu einem anderen im Level zu finden. Um zu verhindern, dass Fahrzeuge oder Charaktere ineinander geraten, , Kollisionserkennung benutzt.

Geometrische Algorithmen

Beispiel für einen gültigen Pfad durch einen Konfigurationsraum.

Beispiel für einen ungültigen Pfad durch einen Konfigurationsraum (Cobs wird mehrfach eingegeben).

Diese Gruppe von Algorithmen verwendet geometrische Techniken, um einen Pfad zu finden, wie z Minkowski-Summe und der zersetzen von C_kostenlos in Zellen.

Die Idee hinter der Zellzerlegung ist, dass man leicht einen Pfad zwischen benachbarten Zellen und zwischen Konfigurationen innerhalb einer Zelle finden kann. Oft wird ein zentraler Punkt innerhalb einer Zelle bestimmt, um die Anzahl der Konfigurationen zu begrenzen. Auf diese Weise kann man einen Weg von einer Start- zu einer Zielkonfiguration konstruieren, indem man sich zuerst von der Startkonfiguration zum Mittelpunkt der Zelle bewegt, dann einem Pfad von Zelle zu Zelle zur Zelle der Zielkonfiguration folgt und dann von der zentraler Punkt in der Zelle von der Zielkonfiguration zur Zielkonfiguration.

Es gibt alle Arten von Techniken zum Zellaufschluss: Man kann C_kostenlos dividiere nach einem bestimmten Datenstruktur (so wie ein Zeitplan, Octree oder ein kd-baum) oder durch Verwendung von Objektmerkmalen (z. B. durch Beginnen einer Zelle an jeder Ecke eines Objekts). Beispiele dafür sind vertikale Zellzerlegung und Zylindrische Zellzersetzung.

Beim Teilen C_kostenlos mit einem Gitter (Punkte über den Konfigurationsraum verteilt) versucht man einen Weg zu finden, indem man einen Weg von Punkt zu Punkt findet. Die Anzahl der Punkte wächst exponentiell wenn die Anzahl der Dimensionen des Konfigurationsraums zunimmt. Somit ist dieser Ansatz für hochdimensionale Konfigurationsräume nicht geeignet.

Virtuelles Kraftfeld

sehen Algorithmus für virtuelle Kraftfelder für den Hauptartikel zu diesem Thema.

Der virtuelle Kraftfeldalgorithmus erzeugt ein Kraftfeld, in dem die Zielkonfiguration den Roboter „anzieht“ und die Objekte eine abstoßende Kraft auf den Roboter ausüben. Auf diese Weise wird der Roboter nach Möglichkeit auf die Zielkonfiguration gelenkt.

Eigenschaften eines Algorithmus

Ein Bewegungsplanungsalgorithmus ist Komplett wenn es immer einen Pfad findet, wenn er existiert. Die meisten vollständigen Bewegungsplanungsalgorithmen verwenden geometrische Techniken. Ein Algorithmus ist unvollständig wenn es nicht immer einen Pfad findet, wenn er existiert.

Ein Algorithmus ist wahrscheinlich vollständig wenn die Wahrscheinlichkeit, einen bestehenden Pfad nicht zu finden, mit längerer Laufzeit des Algorithmus auf 0 sinkt. Mit anderen Worten, die Wahrscheinlichkeit, einen vorhandenen Pfad zu finden, nähert sich 1, je länger der Algorithmus läuft.

Externe Links

• (und) Planungsalgorithmen, Steven M. LaValle

Siehe die Kategorie Bewegungsplanung von Wikimedia Commons für Mediendateien zu diesem Thema.