Pfadplanung mit Potential Fields

Abstract

Diese Seite ist im Rahmen des Kurses Data Visualization an der Freien Universität Berlin entstanden. Aufgabe war es einen Algorithmus zu erklären und zu visualisieren, wobei Informatikstudenten im ersten Semester für das Studium motiviert werden sollten.

Die Pfadplanung mit Potentialfeldern ist ein Algorithmus aus der Robotik. Der Algorithmus plant einem Roboter einen Weg zu einem Ziel. Dabei wird die Kollision mit Hindernissen vermieden.

Problembeschreibung

Stell dir vor ein Roboter (hier R2D2) soll von seinem Startpunkt aus ein Ziel erreichen. Auf dem Weg des Roboters liegen jedoch Hindernisse. Gefährliche Kampfdruiden und gemeine Bösewichte wollen den Roboter aufhalten. Daher muss der Roboter einen Weg zum Ziel finden, ohne an eines der Hindernisse zu geraten.

Damit der Roboter so wenig Energie wie möglich verbraucht, muss er einen möglichst kurzen Weg finden. Hier für wird die Pfadplanung, hier mit der Potential Fields Methode eingesetzt.

Bei dieser Methode werden einfache physikalische Kräfte verwendet.

Diese berechneten Kräfte bzw. Potentiale weisen den Roboter in eine Richtung. Das Ziel zieht den Roboter an und die Hindernisse stoßen ihn ab. Dadurch sollen Begegnungen mit den Hindernissen vermieden werden.

Der Algorithmus

Der Algorithmus Potential Fields nutzt einfache physikalische Elemente zur Wegfindung zum Ziel und Vermeidung von Kollision mit einem Hindernis. Das Ziel hat anziehende Kräfte, daher wird der Roboter dorthin gezogen. Die Hindernisse umgeht der Roboter, da diese abstoßende Kräfte haben.

Auf der rechten Seite siehst du eine Simulation des Algorithmus. Klicke hier, um die Simulation zu starten. (Du kannst auch den Button unter der Simulation verwenden). Der blaumarkierte Roboter findet einen Weg zum orange markierten Ziel. Du kannst alle Objekte verschieben und an beliebiger Stelle pausieren und fortsetzen. Nutze die Gelegenheit um erste Erfahrungen mit dem Algorithmus zu sammeln. Du kannst dir ein eigenes Szenario mit dem Roboter, den Hindernissen und dem Ziel zusammenbauen.

Parametererklärung

Anstatt des Szenarios siehst du auf der rechten Seite nun ein vereinfachtes Beispiel mit einem Hindernis.

Wie findet der Roboter den Weg zum Ziel ohne mit Hindernissen zu kollidieren? Der Roboter wird durch eine Kraft $F$ beeinflusst. Im Bild rechts sieht man einen zweidimensionalen Raum mit allen anfahrbaren Positionen des Roboters. Die Position des Roboters $q_r$ , bestehend aus einer x- und einer y- Koordinate, berechnet sich durch folgende Gleichung:

q_r=\sigma * \frac{F(q_r)}{||F(q_r)||}

Dabei bezeichnet $\sigma$ die Schrittlänge des Roboters. Also kann mit diesem Paramter Einfluss auf die Entfernung, die der Roboter in einem Planungszyklus durchläuft, genommen werden. Nach jedem Planungsschritt wird die Position des Roboters neu berechnet.

Schauen wir uns nun an wie die Kraft bestimmt wird:

F(q_r)=F_{\text{anziehend}}(q_r,q_z)+F_{\text{abstoßend}}(q_r,q_h)

$F(q_r)$ besteht aus zwei Komponenten. Zum einen ist $F_{\text{anziehend}(q_r, q_z)}$ die anziehende Kraft des Roboters in die Richtung des Ziels. Das Ziel hat dabei die Position $q_z$ . Zum Anderen beschreibt $F_{\text{abstoßend}(q_r, q_h)}$ die abstoßende Kraft des nächsten Hindernisses. Das Hindernis hat dabei die Position $q_h$ . Es wird immer nur das Hindernis mit dem kleinsten Abstand zum Roboter betrachtet.

Die anziehende Kraft wird wieder durch zwei Terme berechnet:

F_{\text{anziehend}}(q_r, q_z)= -U_{\text{anziehend}}(q_r, q_g) * (q_r - q_z)

$(q_r - q_z)$ ist dabei der Richtungsvektor vom Roboter zum Ziel.

Dieser Richtungsvektor wird mit dem Potential $U_{\text{anziehend}}(q_r, q_z)$ skaliert:

U_{\text{anziehend}}(q_r, q_z)= \epsilon * \frac{1}{||q_r-q_z||}

Du sieht, dass das Ergebnis nur vom Abstand des Roboters und des Ziels, sowie dem Skalierungsparameter $\epsilon$ abhängt. Das Potential sagt also aus, wie stark der Roboter vom Ziel angezogen wird. Je größer der Abstand, desto kleiner das Potential. Der Parameter $\epsilon$ verstärkt die anziehende Kraft oder schwächt sie ab.

Diese anziehende Kraft kannst du dir auch wie einen Abhang vorstellen. Das Tal ist das Ziel und das Gefälle die Anziehungskraft. Je stärker die Anziehungskraft desto stärker ist das Gefälle. In der nachfolgenden Ansicht siehst du das Potential der Anziehung.

Mit Verschiebung des Regelers Anziehungskraft ändert sich der Parameter $\epsilon$ die Anziehungskraft des Ziels zum Roboter. Beobachte wie sich das Gefälle und das Verhalten des Roboters verändert.

Anziehungskraft $\epsilon$ 20.00

Damit der Roboter zum Ziel kommt, aber nicht mit möglichen Hindernissen kollidiert, geht von den Hindernissen die Kraft $F_{\text{abstoßend}}$ ab. Auch die abstoßende Kraft ist auch in zwei Terme unterteilt:

$F_{\text{abstoßend}}(q_r, q_h)= U_{\text{abstoßend}} * (q_r-q_h)$ .

$(q_r-q_h)$ ist der Richtungsvektor vom Hindernis zum Roboter, der mit dem Potential $U_{\text{abstoßend}}(q_r, q_h)$ skaliert wird:

U_{\text{abstoßend}}(q_r, q_h)=\theta * U_{\text{Erkennung}}*U_{\text{Entfernung}} *\frac{1}{||q_r-q_h||}

Hier stellt θ den Skalierungsparamter dar.

$U_{\text{Entfernung}}=\frac{1}{|q_r - q_h|^2}$ .

$U_{\text{Entfernung}}$ repräsentiert den Abstand zwischen Roboter und Hindernis:

U_{\text{Erkennung}}=(\frac{1}{q_r}-\frac{1}{\phi})

$U_{\text{Erkennung}}$ regelt den Einfluss eines Hindernisses auf den Roboter. Erst wenn der Abstand zwischen Roboter und Hinderniss kleiner als phi ist, wird $U_{\text{abstoßend}}$ berechnet. Ist der Abstand kleiner als $\phi$ , wird $U_{\text{Erkennung}}$ größer, je kleiner der Abstand zwischen Roboter und Hindernis ist. In der Simulation wird ein Hindernis rot markiert, wenn $\phi$ kleiner als der Abstand ist.

Ein Hindernis hat neben der abstoßenden Kraft auch einen Einflussbereich, der beeinflusst wann der Roboter durch die abstoßende Kraft beeinflusst wird.

Ähnlich wie mit unserem Abhang für die anziehende Kraft, kannst du dir ein Hindernis als Berg auf einer Ebene vorstellen. Dabei ist die abstoßende Kraft die Steigung und der Einflussbereich die Breite des Berges.

Verschiebe die Regler Abstoßungskraft und Hindernisseinflussbereich. Beobachte wie sich die Steigung und die Breite des Berges ändern und wie sich der Roboter zu den Hindernissen verhält.

Abstoßungskraft $\theta$ 20.00

Hindernisseinflussbereich $\phi$ 100.00

Die Addition der anziehenden Kraft (Abhang) mit der abstoßenden Kraft (Berg) ergibt das Potentialfeld:

Parameteranwendung

Hier kannst du noch einmal die Parametern verändern. Beobachte die Veränderung des Potentialfeldes (oben) und wie sich der Roboter in der Simulation verhält:

Wenn du den Regler Schrittgröße $\sigma$ verschiebst, kannst du die Schrittgröße beeinflussen. Fällt dir ein Problem auf, wenn du den Wert sehr hoch setzt?

Schrittgröße $\sigma$ 10.00

Wie du vielleicht bemerkt hast, springt der Roboter durch Hindernisse und überspringt gegegenfalls das Ziel. Das liegt daran, dass der Roboter während eines Schrittes immer in die gleiche Richtung geht.

Mit der Anziehungskraft kannst du sehen, wie stark der Roboter vom Ziel angezogen wird. Wenn du den Regler erhöhst, wird der Roboter knapper am Hindernis vorbeigehen um schneller ans Ziel zu gelangen.

Anziehungskraft $\epsilon$ 20.00

Das Gegenteil erreichst du mit der Abstoßungskraft:

Abstoßungskraft $\theta$ 20.00

Mit dem Hinderniseinflussbereich kannst du verändern, wann der Roboter ein Hindernis bemerkt. Das erkennst du daran, dass das Hindernis rot aufleuchtet.

Hinderniseinflussbereich $\phi$ 100.00

Abschließende Worte

Der gezeigte Algorithmus ist auch heute noch relevant. Aber fällt dir etwas auf? Reagiert der Roboter nicht wie du gedacht hast? Falls dein Interesse geweckt ist, gibt es hier noch etwas mehr Informationen. Dort wird noch auf die Probleme des Algorithmus und Erweiterungen eingegangen, wobei du die Probleme vielleicht schon während deinen Experimenten bemerkt hast. Eine Anwendung findest du zum Beispiel im Computerspiel StarCraft.