TU Darmstadt / ULB / TUprints

Automated Hierarchical, Forward-Chaining Temporal Planner for Planetary Robots Exploring Unknown Environments

Delfa Victoria, Juan Manuel (2016)
Automated Hierarchical, Forward-Chaining Temporal Planner for Planetary Robots Exploring Unknown Environments.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
dissertation.pdf
Copyright Information: CC BY-NC-SA 4.0 International - Creative Commons, Attribution NonCommercial, ShareAlike.

Download (41MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Automated Hierarchical, Forward-Chaining Temporal Planner for Planetary Robots Exploring Unknown Environments
Language: English
Referees: von Stryk, Professor Oskar ; Policella, Dr. Nicola ; Gao, Professor Yang
Date: 21 June 2016
Place of Publication: Darmstadt
Date of oral examination: 17 June 2015
Corresponding Links:
Abstract:

The transition of mobile robots from a controlled environment towards the real-world represents a major leap in terms of complexity coming primarily from three different factors: partial observability, nondeterminism and dynamic events. To cope with them, robots must achieve some intelligence behaviours to be cost and operationally effective.

Two particularly interesting examples of highly complex robotic scenarios are Mars rover missions and the Darpa Robotic Challenge (DRC). In spite of the important differences they present in terms of constraints and requirements, they both have adopted certain level of autonomy to overcome some specific problems. For instance, Mars rovers have been endowed with multiple systems to enable autonomous payload operations and consequently increase science return. In the case of DRC, most teams have autonomous footstep planning or arm trajectory calculation.

Even though some specific problems can be addressed with dedicated tools, the general problem remains unsolved: to deploy on-board a reliable reasoning system able to operate robots without human intervention even in complex environments. This is precisely the goal of an automated mission planner. The scientific community has provided plenty of planners able to provide very fast solutions for classical problems, typically characterized by the lack of time and resources representation. Moreover, there are also a handful of applied planners with higher levels of expressiveness at the price of lowest performance. However, a fast, expressive and robust planner has never been used in complex robotic missions. These three properties represent the main drivers for the outcomes of the thesis.

To bridge the gap between classical and applied planning, a novel formalism named Hierarchical TimeLine Networks (HTLN) combining Timeline and HTN planning has been proposed. HTLN has been implemented on a mission planner named QuijoteExpress, the first forward-chaining timeline planner to the best of our knowledge. The main idea is to benefit from the great performance of forward-chaining search to resolve temporal problems on the state-space. In addition, QuijoteExpress includes search enhancements such as parallel planning by division of the problem in sub-problems or advanced heuristics management. Regarding expressiveness, the planner incorporates HTN techniques that allow to define hierarchical models and solutions. Finally, plan robustness in uncertain scenarios has been addressed by means of sufficient plans that allow to leave parts of valid plans undefined. To test the planner, a novel lightweight, timeline and ROS-based executive named SanchoExpress has been designed to translate the plans into actions understandable by the different robot subsystems.

The entire approach has been tested in two realistic and complementary domains. A cooperative multirover Mars mission and an urban search and rescue mission. The results were extremely positive and opens new promising ways in the field of automated planning applied to robotics.

Alternative Abstract:
Alternative AbstractLanguage

Der Übergang von beweglichen Robotern von einer kontrollierten Umgebung in eine reale Welt stellt einen großen Komplexitätssprung dar, der hauptsächlich auf drei unterschiedlichen Faktoren beruht: teilweise Beobachtbarkeit, Nicht-Determinismus und dynamische Ereignisse. Um diese zu beherrschen müssen Roboter ein gewisses intelligentes Verhalten entwickeln, um kostengünstig operieren zu können.

Mars Rover Missions und der Darpa Robotic Challenge (DRC) sind zwei besonders interessante Beispiele von hochkomplexen Roboterszenarien. Trotz wichtiger Unterschiede in Randbedingungen und Anforderungen besitzen beide Szenarien ein gewisses Autonomieniveau, um spezielle Probleme überwinden zu können. Mars Rover zum Beispiel, wurden mit multiplen Systemen ausgestattet, um autonome Nutzlastoperationen zu ermöglichen und dadurch den wissenschaftlichen Nutzen zu erhöhen. Im Falle von DRC nutzen die meisten Teams autonome Schrittplanung oder autonome Berechnung der Bewegung des Roboterarms.

Obwohl einige spezielle Probleme mit eigens dafür entworfenen Tools bearbeitet werden können, bleibt das generelle Problem ungelöst: Die On-board-Installierung eines zuverlässigen Entscheidungssystem, das in der Lage ist, Roboter ohne menschliche Intervention selbst in komplexen Umgebungen zu steuern. Genau dies ist das Ziel eines automatisierten Missionsplanungstools.

Wissenschaftler haben eine Vielzahl von Planungstools entwickelt, die in der Lage sind, sehr schnelle Lösungen für klassische Probleme zu liefern, die sich typischerweise dadurch auszeichnen, dass Zeit und Ressourcen stellen können. Darüber hinaus gibt es eine Handvoll angewandter Tools mit tieferer Detailtreue, was aber zu Lasten deren Performance geht. Ein schneller, expressiver und robuster Missionsplaner wurde jedoch noch nie in einer komplexen Robotormission benutzt. Diese drei Eigenschaften stellen die Hauptmotivation dar für das Ergebnis dieser Arbeit.

Ein neuer Formalismus, Hierarchical TimeLine Networks (HTLN), wurde vorgeschlagen, der Zeitplan und HTN Planung verknüpft, um die Lücke zwischen klassischer und angewandter Planung zu schließen.

HTLN wurde in dem Planungstool QuijoteExpress implementiert. Dieses Tool ist nach unserem Wissen, das erste forward-chaining Zeitplanungstool. Die Idee ist von der hohen Performance der forwardchaining Suche zu profitieren, um zeitliche Probleme im Zustandsraum zu lösen. Zusätzlich enthält QuijoteExpress Suchverfeinerungen wie paralleles Planen durch Aufteilen des Problems in Unterprobleme oder fortgeschrittenes Management von Heuristiken. Bezüglich Expressiveness verwendet das Planungstool HTN Techniken, die erlauben hierarchische Modelle und Lösungen zu definieren. Zu guter Letzt wurde Planungsrobustheit durch das Konzept von “ausreichender Planung” adressiert , die erlaubt, dass Teile von gültigen Plänen undefiniert bleiben.

Um das Planungstool zu testen, wurde ein neues “light” Zeitplan- und ROS-basiertes Executable entworfen, um die Pläne in Aktionen zu übersetzen, die von den verschiedenen Robotersubsystemen verstanden werden können.

German
Uncontrolled Keywords: Automated Planning, Automated Execution, Mars Rover, Mobile Robot, Forward-Chaining, HTN, HTLN, Timeline Planning, Non-determinism, Uncertainty
URN: urn:nbn:de:tuda-tuprints-55376
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Algorithmics
20 Department of Computer Science > Intelligent Autonomous Systems
Date Deposited: 05 Oct 2016 09:46
Last Modified: 09 Jul 2020 01:19
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/5537
PPN: 387452478
Export:
Actions (login required)
View Item View Item