Motion Planning for Nonholonomic Vehicles with Space Exploration Guided Heuristic Search
Chao Chen · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2016
The development of the modern sensing, actuation, communication, and computation technology unfolds a promising future of mobile robots, especially for intelligent automobiles.Motion planning is one of the most important software components in these autonomous systems.It is responsible for a motion strategy or trajectory while considering the robot kinematic model, the prior knowledge of the environment, the real-time perception, and domain specific rules.Particularly, a motion planning problem for an autonomous vehicle is beyond a theoretical problem of finding an executable collision-free trajectory.An intelligent vehicle should behave rationally in traffic, which includes following a global route from the navigation, adapting local behaviors according to the circumstances, obeying traffic rules, and respecting the convenience of the human traffic participants.Furthermore, the driving tasks are highly diverse, so specific motion planning methods are required for different maneuver types.In this case, an intelligent agent should be able to process all kinds of information with domain knowledge, select the most efficient algorithm for a specific task, and integrate them seamlessly in a system.In this dissertation, a Space Exploration Guided Heuristic Search (SEHS) method is introduced as a base framework for mobile robot motion planning.Several extensions of SEHS such as Orientation-Aware Space Exploration Guided Heuristic Search (OS-EHS) and Space Time Exploration Guided Heuristic Search (STEHS) are developed for specific autonomous driving scenarios.They can be integrated in a hierarchical planning architecture with a high-level task planning in order to process information in different layers and achieve online motion planning for mobile robots, especially autonomous vehicles.The general idea of the Space Exploration Guided Heuristic Search approach is to boost the forward search in continuous state space with heuristics from the subspace properties such as topology and dimension.The SEHS framework consists of two sequential procedures: (1)Space Exploration investigates a low dimensional subspace with distance queries for a path corridor connecting the start and goal locations, (2) Heuristic Search propagates robot states with primitive motions following the path corridor for a trajectory from the start state to the goal state.The space knowledge obtained in the exploration phase enables the search algorithm to adapt the step size of motion primitives and the state resolution regarding the free-space dimension.Furthermore, as a generic exploration and search framework, the SEHS method can flexibly scale the subspace to robot orientation for maneuvering in narrow places as Orientation-Aware Space Exploration Guided Heuristic Search, or include time domain for dynamic scenarios as Space Time Exploration Guided Heuristic Search.A Motion Planning Engine (MPE) is developed as an online planning agent for autonomous driving.Based on the hybrid planning schema, task planning is introduced as the middle layer between route planning and motion planning.It evaluates the symbolic states of the system with traffic domain knowledge, so that a sequence of driving tasks is selected to accomplish the driving mission.Each task can be Zusammenfassung Die Entwicklung der modernen Sensorik, Aktorik, Kommunikations-und Rechentechnik lässt eine vielversprechende Zukunft von mobilen Robotern erwarten, vor allem für intelligente Fahrzeuge.Bewegungsplanung ist eine der wichtigsten Software-Komponenten in diesen autonomen Systemen.Sie ist für eine Bewegungsstrategie oder eine Trajektorie verantwortlich.Die gilt vor allem in Bezug auf das kinematische Modell des Roboters, das Vorwissen über die Umgebung, die Echtzeit-Wahrnehmung und die domänenspezifische Vorschriften.Insbesondere ist ein Bewegungsplanungsproblem für ein autonomes Fahrzeug mehr als das theoretische Problem, eine ausführbare kollisionsfreie Trajektorie zu finden.Ein intelligentes Fahrzeug sollte sich auch im Straßenverkehr rational verhalten.Das umfasst das Folgen eines globalen Pfads einer übergeordneten Navigationskomponente, die Anpassung des lokalen Verhaltens an äußere Umstände, sowie die Befolgung von Verkehrsregeln.Dies alles, unter Berücksichtigung des Komforts menschlicher Verkehrsteilnehmer.Darüber hinaus sind die Fahraufgaben sehr vielfältig, was in der Regel spezifisch optimierte Bewegungsplanungsmethoden für die unterschiedliche Manövertypen erfordert.In diesem Fall sollte ein intelligenter Agent in der Lage sein, alle möglichen Informationen mit Domänenkenntnissen zu bearbeiten, effizienteste Algorithmen für bestimmte Aufgaben zu wählen und alle Funktionen nahtlos in ein System zu integrieren.In dieser Dissertation wird eine Space Exploration Guided Heuristic Search (SEHS) Methode als Basis für die Bewegungsplanung mobiler Roboter eingeführt.Mehrere Erweiterungen von SEHS wie Orientation-Aware Space Exploration Guided Heuristic Search (OSEHS) und Space Time Exploration Guided Heuristic Search (STEHS) sind für bestimmte autonome Fahrszenarien entwickelt worden.Sie können in einer hierarchischen Planungsarchitektur mit einer High-Level-Aufgabenplanung integriert werden, um Daten in verschiedenen Schichten zu verarbeiten und eine Online-Bewegungsplanung für mobile Roboter, insbesondere für autonome Fahrzeuge, zu realisieren.Die Grundidee des Space Exploration Guided Heuristic Search Ansatzes ist es, die Vorwärtssuche in kontinuierlichem Zustandsraum mit Heuristiken von der Eigenschaften des Unterraums zu unterstützen, wie etwa dem Wissen über Topologie und Abmessung des Raumes.Das SEHS Framework besteht aus zwei aufeinanderfolgenden Verfahren: (1) Space Exploration untersucht einen niedrigdimensionalen Unterraum mit Abfragen über Abstände für einen Pfadkorridor zwischen Start-und Zielpose, (2) Heuristic Search propagiert Zustände des Roboters mit Bewegungsprimitiven zum Korridorweg für eine Trajektorie vom Startzustand zum Zielzustand.Die Kenntnisse über den Raum, die in der Explorationsphase erhalten werden, ermöglichen es dem Suchalgorithmus, die Schrittweite der Bewegungsprimitiven und die Auflösung der Zustände zur Freiraumdimension anzupassen.Ferner lässt sich mit dem SEHS Verfahren als generisches Explorations-und Such-Framework der Unterraum flexibel skalieren, um etwa die Ausrichtung des Roboters für Manöver in engen Stellen bei Orientation-Aware Space Exploration Guided Heuristic Search, oder mit der Zeitdomäne für dynamische Szenarien bei Space Time Exploration Guided Heuristic Search.Eine Motion Planning Engine (MPE) wird als Online-Planungsagent für autonomes Fahren entwickelt.Auf Basis eines Hybridplanungsschemas wird Aufgabenplanung als eine Mittelschicht zwischen Routenplanung und Bewegungsplanung eingeführt.Diese evaluiert die symbolischen Zustände des Systems mit domänenspezifischem Wissen über den Verkehr, damit eine Folge von Fahraufgaben ausgewählt werden kann, um die Fahrmission auszuführen.Jede Aufgabe kann als ein Bewegungsplanungsproblem dargestellt werden, das mit einem geeigneten Kontext in angemessenem Umfang beschränkt wird, so dass es mit einem passenden Planungsalgorithmus in der Bewegungsplanungsebne effizient gelöst werden kann.Außerdem werden die Planungsergebnisse kontinuierlich mit der Echtzeitsituation verifiziert und falls nötig neu geplant.Somit verbindet die MPE die Inputs wie Verkehrsregeln, Fahrplan, Objekt-Liste und Fahrzeugzustand, plant Bewegungen mit Lenk-und Beschleunigungsbefehlen und gewährleistet die Sicherheit während des gesamten Fahrvorgangs.Darüber hinaus wurde eine C++ Bibliothek mit dem Namen AutoDrive für autonomes Fahren entwickelt.Die Bibliothek besteht aus Paketen mit Funktionen für allgemeine Mathematik, Fahrzeugkinematik, Umwelt-Modelle und verschiedenen Planungsalgorithmen. Eine Simulationsumgebung wurde ebenfalls bereitgestellt, um Planungsverfahren und Ergebnisse in verschiedenen Verkehrsszenarien zu visualisieren.Die AutoDrive Bibliothek bietet eine kompakte und essenzielle Software-Basis für Bildung, Forschung und die Prototypentwicklung von mobilen Robotern oder autonomen Fahranwendungen.This thesis is dedicated