Maxim LikhachevResearch Assistant Professor
|
Sven KoenigAssociate Professor
|
Real-world agents often have to operate in domains that are dynamic or only partially known, yet have to plan sufficiently fast to be able to act under real-time conditions, which is an important but challenging problem in robotics. This half-day tutorial gives an overview of approaches to real-time planning in dynamic and only partially-known domains, all of which gain drastic efficiency by planning with a series of A* search. The presented A*-based planners come with solid theoretical analyses, generalize well across different domains and are simple to implement. The tutorial explains the approaches, presents analytical results about their runtimes and plan qualities and demonstrates their application to various problems in robotics, including motion planning for high degree-of-freedom robot arms, planning dynamically-feasible paths for outdoor ground robots (including the winner of the Urban Challenge race in 2007) and path planning for aerial robots.
The tutorial first introduces three efficient strategies to planning in dynamic or only partially known domains: planning with limited planning horizon, planning under the simplifying assumption that the domain is deterministic, and probabilistic planning. The runtimes of these strategies are often inversely correlated with their plan qualities. The tutorial presents analytical and experimental results about the runtimes and plan qualities of these strategies. It then describes algorithms that efficiently implement these strategies and are suitable for the use under real-time conditions. The tutorial shows how all of these algorithms gain drastic efficiency by solving the problem with repeated A*-like searches. The tutorial explains how these algorithms operate, presents their theoretical properties and shows their applications to a variety of planning problems such as motion planning for high degree-of-freedom robot arms, symbolic planning, planning dynamically-feasible trajectories for outdoor ground robots including the Urban Challenge winner in 2007 and planning dynamically feasible paths for aerial robots.
Robotics researchers have been interested in the topic for a long time since robots typically operate not only in dynamic and partially known domains but also under real-time conditions. This tutorial focuses on search-based approaches to planning in dynamic and partially known domains, developed by the tutorial presenters and others, that are efficient and usable under real-time conditions. Thus, the tutorial will introduce novices and expert non-specialists to a subarea in robotics/AI and instruct them in methodologies of emerging importance.