Motion planning for car-like robots

Abstract

Routenplanung bzw. Bewegungsplanung sind aktuell spannende Forschungsgebiete der Robotertechnik. Angefangen von CNC Maschinen bis hin zu humanoiden Robotern gibt es verschiedenste Anwendungsbereiche für Roboter. Ein wichtiger Anwendungsbereich ist der automotive Sektor. Hier nehmen Arbeiten an autonomen Fahrzeugen, die sich im städtischen Bereich frei bewegen können, einen bedeutenden Stellenwert ein. Darüber hinaus gibt es noch weitere, weniger bekannte, jedoch ebenfalls anspruchsvolle Anwendungsgebiete für mobile Roboter. Großes Potential haben dabei mobile Roboter im landwirtschaftlichen Bereich. Genau diesem Anwendungsgebiet ist diese Diplomarbeit gewidmet. Sie beschäftigt sich hauptsächlich mit der Routenplanung für mobile Roboter im landwirtschaftlichen Kontext und geht dabei speziell auf die Anfordernisse dieses Bereichs ein. Ein Beispiel für eine Anwendung ist das Mähen einer bestimmten Fläche auf einem Feld.<br />Das Ziel dieser Arbeit ist es, einen Routenplanungsalgorithmus für automobilähnliche Roboter zu entwickeln und zu implementieren. Die Entwicklung ist an ein bereits existierendes Fahrzeug angelehnt. Dieses Fahrzeug ist mit einem präzisen satelliten-gestützten Navigationssystem und digitalem Kompass ausgestattet. Der genannte Algorithmus soll es ermöglichen, einen Pfad zwischen zwei beliebigen Punkten zu finden, sowie einen definierten Bereich, wie z.B. eine Arbeitsfläche, in parallelen Bahnen abzufahren.<br />Um dieses Ziel zu erreichen, werden im ersten Schritt einige vielversprechende Planungsstrategien und Ansätze untersucht. Im Anschluss daran werden Algorithmen diskutiert, die speziell für mobile Roboter geeignet sind. Diese Ansätze gehen von dem grundlegenden Problem aus, unter Berücksichtigung von Hindernissen und spezifischen Systemeigenschaften, einen zulässigen Pfad zwischen zwei beliebigen Punkten zu finden. Bei der Untersuchung dieser Algorithmen wird auch auf die praktische Umsetzbarkeit geachtet.<br />Basierend auf den zuvor vorgestellten Ansätzen wird ein Algorithmus entwickelt und diskutiert, der es ermöglicht, ein beliebiges Feld in parallelen Bahnen abzufahren, wobei größter Wert auf Effizienz und Realisierbarkeit gelegt wird. Um zu verifizieren, ob der generierte Pfad für das Fahrzeug fahrbar ist, wird das Verhalten eines solchen Fahrzeugs simuliert. Dabei wird ein realistisches Modell eines automobilähnlichen Fahrzeugs angenommen. Weiters werden die Fehler der Sensoren (Positionsfehler und Orientierungsfehler) realitätsnahe berücksichtigt.<br />Um das Fahrzeug entlang eines Pfades zu bewegen, wird ein geeigneter Steuer- bzw. Regelalgorithmus verwendet. Analysen zeigen, dass der neu entwickelte Algorithmus alle gewünschten Anforderungen erfüllt.<br />

Motion planning is one of the most challenging tasks in robotics. Dedicated algorithms are used in many different applications starting from CNC machines to human-like robots. An interesting research area within this field is motion planning for car-like robots. In the last few years, car-like robots became increasingly important, because precise positioning systems like GPS or GLONASS and modern sensor technologies allowed navigating in rural or even in urban terrains.<br />These car-like robots can be used for different kinds of purposes. In the automotive domain, they may pave the way for driving in urban terrain. In the agriculture area, applications for harvesting, fertilizing or lawn mowing can be realized. This thesis focuses on motion planning for car-like robots and particularly on applications where an arbitrary working area should be covered as efficient as possible.<br />The aim of this thesis is to develop a path planning application which is able to compute a feasible path between two arbitrary points.<br />Furthermore, the path shall fully cover a predefined area avoiding obstacles. Moreover, it is desired that the predefined working area is cruised in parallel lanes (e.g., for mowing a soccer field). The path shall be calculated based on lists of geodetic data which represent arbitrary but simple polygons.<br />At the beginning, basic concepts of system theory and system modeling will be studied. Next, different approaches for solving the basic motion planning problem will be discussed. Then, system models for car-like robots will be addressed. Based on such a system model, motion planning concepts are examined which are suitable for car-like robots.<br />Considering the benefits and the drawbacks of all investigated algorithms, a solution based on randomized trees is proposed. Finally, an algorithm for motion planning covering predefined areas in parallel lanes is introduced.<br />A proof-of-concept implementation in combination with a simulation framework allows evaluating the quality and the feasibility of the computed path. The simulation is based on a simple path following controller and a realistic system model for a car-like robot which considers errors of the system (e.g., GPS and heading errors) close to reality. Analyses of the simulation show that the car-like robot is able to follow the computed path even in presence of system errors.