Sommer, G. (2005). Robot motion planning with genetic algorithms [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-15640
E325 - Institut für Handhabungsgeräte und Robotertechnik
-
Date (published):
2005
-
Number of Pages:
145
-
Keywords:
Bahnplanung; mobile Roboter; genetische Algorithmen; evolutionäre Algorithmen
de
Motion Planning; Path Planning; Evolutionary Algorithms; Genetic Algorithms; mobile Robots
en
Abstract:
Die autonome Navigation ist eines der zentralen Forschungsfelder im Bereich der mobilen Robotik. Einen wichtigen Punkt zur Erreichung dieses Zieles stellt die Kollisionsvermeidung von Hindernissen dar. Daher ist die Planung von kollisionsfreien, zusammenhängenden Pfaden zwischen Anfangs- und Endpunkten eine fundamentale Voraussetzung für die autonome Fortbewegung von mobilen Robotern.<br />Das Gebiet der Bewegungsplanung für Roboter ist seit drei Jahrzehnten ein aktives Forschungsgebiet und zahlreiche klassische Algorithmen zur Pfadplannung wurden entwickelt. Ihnen allen gemeinsam ist, dass sie zuerst einen möglichst exakten Plan der Umgebung entwickeln und danach einen Algorithmus zum Auffinden eines optimalen Weges zwischen Anfangs- und Endpunkt darauf anwenden. Der Schwachpunkt dieser Methoden liegt darin, dass sie sehr unflexibel auf Änderungen in der Umgebung reagieren und sehr langsam in großen und komplexen Umgebungen sind. Einen vielversprechenden Weg diese Probleme zu überwinden, stellen heuristische Methoden dar. Diese unterscheiden sich von den klassischen Pfadplanungsalgorithmen dadurch, dass sie eine Umgebungskarte mittels stochastischen statt deterministischen Methoden erstellen. Eine beliebte heuristische Methode sind Evolutionäre Algorithmen. Sie basieren auf dem Darwinschen Prinzip 'Überleben der Geeignetsten' und haben sich als eine effektive Optimierungsmethode für komplexe Suchräume herausgestellt. In dieser Arbeit werden Genetische Algorithmen zur Pfadplanung eines synchrongetrieben Roboters verwendet. Wir zeigen, dass solche Algorithmen schnelle und robuste Werkzeuge für Planungsaufgaben in Umgebungen mit Hindernissen sind. Es werden zuerst Ergebnisse von Simulationsstudien vorgestellt, die anschließend auf der mobilen Roboterplattform Nomad 200 implementiert werden.<br />
de
Autononomous navigation is one of the key problems in the field of mobile robots. To achieve this goal an important factor is to prevent the vehicle from colliding with obstacles.<br />Planning a collision free, feasible path from the starting to the goal point is therefore a fundamental requirement for autonomous navigation. Robot motion planning has been an active research area for the last three decades and numerous classical path planning algorithms have been developed. They all have in common that they build a preferable exact map of the environment at first and then use a certain algorithm to find an optimal path to reach the desired goal. The drawback of these methods is that they are inflexible with respect to changes of the environment or target points and that they are rather slow in large and complex environments. A promising way to overcome that difficulties is to use sampling-based or heuristic methods . They differ from the classical ones by constructing a roadmap with probabilistic or random techniques instead of a deterministic way. A popular heuristic optimization method are Evolutionary algorithms. They are based on the Darwinian principle 'survival of the fittest' and have demonstrated to be effective procedures in complex search spaces. In this work we use Genetic algorithms for planning motions of a synchronous drive robot. We show that such planners are fast and robust tools for planning tasks in environments with obstacles. We first did some simulation studies and tested it afterwards on the Nomad 200 platform.