Delfa Victoria, Juan Manuel
Automated Hierarchical, Forward-Chaining Temporal Planner for Planetary Robots Exploring Unknown Environments.
Technische Universität Darmstadt, Darmstadt
[Ph.D. Thesis], (2016)
Available under CC-BY-NC-SA 4.0 International - Creative Commons Attribution Non-commercial Share-alike 4.0.
Download (41MB) | Preview
|Item Type:||Ph.D. Thesis|
|Title:||Automated Hierarchical, Forward-Chaining Temporal Planner for Planetary Robots Exploring Unknown Environments|
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.
|Place of Publication:||Darmstadt|
|Uncontrolled Keywords:||Automated Planning, Automated Execution, Mars Rover, Mobile Robot, Forward-Chaining, HTN, HTLN, Timeline Planning, Non-determinism, Uncertainty|
|Classification DDC:||000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik|
|Divisions:||20 Department of Computer Science > Algorithmics
20 Department of Computer Science > Intelligent Autonomous Systems
|Date Deposited:||05 Oct 2016 09:46|
|Last Modified:||05 Oct 2016 09:49|
|Referees:||von Stryk, Professor Oskar and Policella, Dr. Nicola and Gao, Professor Yang|
|Refereed:||17 June 2015|