sampling based motion planning; decomposition based planning; hierarchical planning; motion planning
en
Abstract:
Das Planen von kollisionsfreien Pfaden ist eine Aufgabe, die in vielen Gebieten wie Industrieautomatisierung, Molekularbiologie und autonomen Fahrzeugen von Interesse ist. Sampling-basierte Planungsalgorithmen wie Rapidly Exploring Random Trees (RRT) sind in der Lage, solche Planungsprobleme effizient zu lösen.<br />Seit der Einführung dieser Algorithmen wurden Schwachstellen -- wie enge Passagen im Zustandsraum und Empfindlichkeit gegenüber der gewählten Entfernungsmetrik -- identifiziert. Aktuelle Methoden zerlegen den freien Raum zwischen Hindernissen der Problembeschreibung in nicht-\-überlappende Zellen (Workspace Decomposition) und verwenden diese Struktur, um den Planungsprozess zu steuern.<br />Das Ziel der vorliegenden Arbeit ist es, eine grundlegende Analyse von Erweiterungen für RRT-basierter Planer zu präsentieren, die von Workspace Decompositions Gebrauch machen. Basierend auf der Analyse sind Methoden zu implementieren und potentielle Verbesserungen umzusetzen.<br />Wir bieten einen detaillierten Überblick über die Grundlagen von Pfadplanungsalgorithmen einschließlich früher Methoden, die Vorläufer für aktuelle Workspace Decomposition-Methoden darstellen. Das Hauptaugenmerk liegt dabei auf neuen Methoden, die anhand der Nachbarschaftsstruktur der Zellen einen Graphen aufbauen und diesen verwenden, um den Suchprozess mit einem Greedyverfahren zur Zelle zu führen, welche den Zielzustand beinhaltet.<br />Wir präsentieren vier Workspace Decomposition-basierte Erweiterungen der RRT-Methode. Diese umfassen zwei Samplingerweiterungen, eine Adaption der Graph-Methode auf RRTs sowie eine neue Methode genannt ``Two Layer-RRT'' (TL-RRT).<br />TL-RRT wendet den RRT-Ansatz auf die diskrete Graph-Schicht an, die den kontinuierlichen Suchprozess leitet.<br />In einer detaillierten Analyse zeigen wir die Verwandtschaft zwischen graph-geleiteten Methoden und der Potential Fields-Planungsmethode auf.<br /> Eine große Anzahl von Testfällen, welche die umgesetzten Methoden gezielt auf Schwachstellen untersuchen sollen, wurden im Rahmen dieser Arbeit entwickelt. Der Vergleich unserer Planungsmethoden mit der Standard-RRT Methode zeigt, dass die Sampling-Methoden eine Beschleunigung von bis zu einem Faktor 3 erreichen können. Die beiden graph-basierten Methoden erreichen eine signifkante Reduktion der Planungszeit um einen Faktor von bis zu 22.<br />Eine gravierende Schwachstelle des Greedyverfahrens konnte identifiziert werden. Sie bewirkt, dass die Planungszeit auf speziellen Planungsproblemen signifikant verlängert wird oder verhindert, dass diese Methoden eine existierende Lösung finden. Weiters zeigen wir, dass unser TL-RRT Ansatz in der Lage ist, dieses Problem zu bewältigen.<br />
de
Motion planning is a challenging task recurring in different scientific fields like molecular biology, industrial automation and autonomous vehicles. Recent sampling-based planners, like Rapidly exploring Random Trees (RRTs), are able to solve challenging planning tasks in these domains. These methods employ an incremental construction of a search structure in the high dimensional state space of the problem to compute a solution.<br />Narrow passages and metric sensitivities are major problems of these planners and recent methods use a workspace decomposition (a decomposition of the free space between obstacles into cells) in order to guide the exploration process. The goal of this thesis is to give a thorough analysis of extensions of RRT-based motion planning by the application of workspace decompositions and to develop and evaluate improvements based on this analysis. For this purpose, we give an introduction to the principles of motion planning and discuss early planning algorithms, which are related to the current extensions of sampling-based planners. Of central interest are recent planners which build a graph employing the adjacency relationship of cells and greedily guide the planner towards the cell containing the goal state.<br />We present four RRT-planners based on a decomposition of the workspace including two sampling extensions, an adaptation of a greedy graph-guidance method and an innovative new approach called Two Layer-RRT (TL-RRT). TL-RRT employs the RRT-approach on the discrete graph layer used to guide the continuous exploration process.<br />In the analysis of the methods we underline the connection between the greedy graph-guided approach and potential fields methods. A benchmark set is presented which is designed to test the influence of identified weaknesses of the planning approaches on challenging holonomic, non-holonomic and kinodynamic planning instances. We compare the performance of the four proposed planners to the standard RRT-method on these benchmarks. The sampling methods show speedups of a factor up to three on planning problems involving narrow passages. The guided planners are able to reduce planning time by a factor up to 22.<br />We identify a severe problem of greedily guided planners which leads to significantly decreased performance or prevents them from finding an existing solution. We show that TL-RRT is able to overcome this challenge and shows comparable speedups on other planning instances.<br />We conclude that the application of workspace decomposition guidance is able to significantly improve planning performance and reduces the impact of narrow passages and metric sensitivities in RRT-based planners.
