Juni 2004: Studienarbeit bei Prof. Rojas

Fast Geometric Path Planning for the Smallsize Robocup League

geometrische Pfadplanung für Roboter

Schnelle geometrische Pfadplanung für die smallsize Robocup (Roboterfußball) Liga

Abstract, deutsche Übersetzung

Präsentiert wird ein Algorithmus zur Planung der Bewegung eines Roboters auf einem rechteckigen Feld mit Hindernissen. Die Positionen der Hindernisse und des Roboters sind bekannt. Gesucht wird die erste Zwischenposition auf einem Pfad zu einem gegebenen Endpunkt. Der Algorithmus basiert auf einem geometrischen Ansatz wobei jeder Punkt des Pfades auf der Ecke eines oder ein Tangentenschnittpunkt auf einem kreisförmigen Hindernis. Der Algorithmus wurde für den Fall der kleinen Fu-Fighters, der fußballspielenden Roboter der FU-Berlin implementiert.

Abstract, original

Presented is an algorithm for planning the motion of a robot moving on a rectangular field with obstacles. The positions of every obstacle and the robot are known. Searched is the first intermediate point on a path leading to a given endpoint. The algorithm takes a geometric approach where every point of the path is the corner of a polygonal obstacle or a tangent on a circular obstacle. The algorithm was implemented in the case of the FU-Fighter's soccer-robots.


Literatur zur geometrischen Pfadplanung

Danny Z. Chen:  Developing Algorithms and Software for
Geometric Path Planning Problems

"Computing shortest paths is a fundamental topic in computational geometry and arises in many applications. We assess the status of the current research on solving geometric shortest path problems and suggest several possible directions for future work on these and related problems."