An experimental analysis of optimization base motion planning

Abstract

Through the advance of technology, robots aren't just objects from science fiction novels, but they are becoming more and more part of our everyday life and are specially designed and constructed to support us. From little household helper that finish domestic chores to big industrial robots that assemble huge machines and automobiles, there are hundreds of different types of robots. Especially in interaction with humans it is important for a robot to react to environmental changes. In case of upcoming difficulties the robots ought not to freeze in place and take a lot of time to calculate their possibilities on how to avoid obstacles that might be in their way. Rapidly-exploring random trees and other sampling-based methods are one way to solve this problem, where robots are able to find a viable solution and execute it. However, the resulting solutions were not efficient enough and post-processing consisting of optimization methods had to be applied to smooth out the trajectories. The necessity of this optimization lead to a new generation of planning methods that were based on optimization alone. In many domains, these optimization-based motion planners constitute the state-of-the-art.

This thesis compares various optimization-based motion planners within an efficient common environmental representation with respect to the following criteria: speed, accuracy, and applicability. Through a variety of tests with arbitrary obstacles the methods will be compared and the results presented. The document concludes with an outlook on further work and possibilities.

Durch den technischen Fortschritt sind Roboter nichtmehr nur Objekte aus Science-Fiction Büchern sondern Teile unseres Lebens. Sie werden zu einem immer größer werdenden Teil unseres alltäglichen Lebens und werden speziell dazu entwickelt, uns bei vielen Aufgaben zu unterstützen. Es gibt bereits eine Vielzahl an Robotern: von Haushaltshelfern, die kleine Arbeiten verrichten, bis hin zu größeren, industriellen Robotern, die gewaltige Maschinen und Automobile zusammenbauen. Besonders in der Interaktion mit Menschen ist es für einen Roboter wichtig auf Veränderungen in seinem Umfeld zu reagieren, zum Beispiel wenn ein Hindernis aufkommt, soll der Roboter im Stande sein, in kürzester Zeit eine neue Route zu berechnen, und so die Aussetzzeit so minimal wie möglich zu halten. Rapidly-exploring random trees und andere Abtastmethoden sind nur ein Paar mögliche Methoden, bei denen Roboter eine Lösung finden, sie umsetzen und so möglich entstandene Probleme beheben. Die dabei entstandenen Methoden sind jedoch nicht immer effizient und erfordern eine Nachbesserung durch Optimierungsverfahren, um die berechneten Bewegungen zu verbessern. Die Notwendigkeit solcher Optimierungen führt zu einer neuen Generation von Bewegungsplanern, die auf diese Methoden basieren. In vielen Bereichen werden sie mittlerweile als Standard angesehen. In dieser Arbeit werden verschiedene Bewegungsplaner, die auf Optimierungsverfahren aufbauen, in einer vordefinierten Umgebung verglichen. Dabei wird der Wert auf folgende Faktoren gelegt: Geschwindigkeit, Genauigkeit und Anwendbarkeit. Durch eine Vielzahl von Tests werden die Bewegungsplaner verglichen und die Resultate präsentiert. Abschließend zeigen wir weitere Möglichkeiten auf, die in näherer Zukunft vielleicht durchführbar sein werden.