Meta-heuristic local planning

Abstract

Die Fähigkeit in dynamischen Umgebungen zu navigieren ist eine wesentliche Funktion für mobile Roboter. Um eine sichere Fahrt zu garantieren, wird die Navigation in zwei Schritte aufgeteilt - globale und lokale Planung. Ein globaler Planer findet anhand einer Karte einen Weg zum gewünschten Ziel. Dieser Weg fungiert als Orientierungshilfe für eine lokale Planungskomponente. Der lokale Planer verwendet unter Berücksichtigung der aktuellsten Sensormessungen lokale Informationen und Strategien zur Kollisionsvermeidung um sicher der Orientierungshilfe so exakt wie möglich zu folgen. Effektive lokale Planer wie Dynamic Window Approach (DWA) basieren auf einem Sampling des Controlspace des Roboters. Für einen kurzen Zeitraum wird die Applikation von Steuerwerten simuliert und die resultierenden Trajektorien generiert. Mit einer Kostenfunktion werden die Trajektorien gewichtet und die Steuerwerte der besten Trajektorie and die Motorsteuerung weitergeleitet. Das Ziel dieser Arbeit ist eine Analyse und Verbesserung der Leistung von lokalen Planern durch Einsatz bekannter metaheuristischer Algorithmen bei der Selektion der Trajektorien. Zu diesem Zweck wird eine Einführung zu lokalen Planungsmethoden präsentiert, gefolgt von einer Diskussion zu Metaheuristiken. Die Ansätze basierend auf Iterated Local Search, Variable Neighborhood Search und Tabu Search werden implementiert und mit einem einfachen Planer getestet. Die Resultate zeigen eine signifikante Verbesserung der Leistung verglichen mit der Brute-Force-Methode, die üblicherweise bei dieser Art lokaler Planung verwendet wird. In weiterer Folge wird der VNS Ansatz gewählt um den Selektionsprozess in einer existierenden Implementierung von lokalen Planern zu ersetzen. Algorithmen basierend auf Trajectory roll-out (VNS-ROL) und DWA (VNS-DWA) werden entwickelt und mit einer Simulationsoftware evaluiert. Die Leistung der adaptierten Planer übertrifft dabei die ursprünglichen Implementierungen in allen Testszenarien.

Navigation is a crucial task for mobile robots driving through dynamic environments. Besides the difficulties involved in finding a way from a starting to some goal location, the problem gets more difficult if unknown objects, dynamics of the robotic vehicle and uncertainties from sensor readings have to be taken into account. To guarantee a safe passage common approaches divide the navigation task into two parts - global and local planning. A global planner finds an initial path to the desired goal location based on a previous obtained map. The retrieved path is used as a guide for a local path planning component. This local path planner uses so called local information obtained through recent sensor readings and applies obstacle avoidance strategies to safely and efficiently follow the guide as precise as possible. Very effective local planning methods like the Dynamic Window Approach (DWA) or Trajectory Roll-out are based on sampling the control space of the robot. For a short amount of time the application of these controls is simulated generating corresponding trajectories. By using appropriate cost functions the resulting trajectories are weighted and the best one yields the optimal target values for the motor controller. The goal of this thesis is to analyze these approaches and improve the performance of local planners by applying well known meta-heuristic search strategies in the trajectory selection process. For this purpose an introduction to local planning and obstacle avoidance methods is presented, followed by a discussion of applicable single solution based meta-heuristics. Approaches based on Iterated Local Search, Variable Neighborhood Search and Tabu Search are implemented and tested using a sample planner based on DWA. These algorithms are analyzed and evaluated using random created instances of sensor maps. Results are documenting a significant increase in performance compared to the brute force evaluation commonly used in local planner. With the gained knowledge of these tests the VNS approach is selected to substitute the selection process in a popular implementation of local planner within the Robot Operating System. Two algorithms based on trajectory Roll-out (VNS-ROL) and DWA (VNS-DWA) are developed and evaluated using a sophisticated simulation engine. The altered planner outperform the original implementations on all tested instances.