ICRA 2010 Tutorial on Real-Time Planning in Dynamic and Partially-Known Domains

Slides (PDF, 12MB)

Location:

2010 IEEE International Conference on Robotics and Automation in Anchorage, Alaska, USA
ECSH Room 1

Date/Time:

Friday, May 7, 2010, 2:00-5:30PM

Abstract

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.

Outline

Motivation and objectives

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. This presents an important but challenging problem in AI and robotics. This tutorial presents a broad class of search-based approaches to planning in dynamic or only partially known domains under real-time conditions. These approaches typically come with solid theoretical analyses, generalize well across different domains and are simple to implement.

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.

Intended Audience

The tutorial is self-contained and assumes only the knowledge equivalent to an undergraduate robotics/AI class. It will therefore be of interest to many robotics students and researchers, both those that are interested in the many applications that require real-time planning in dynamic or only partially known domains and those that are interested in learning about planning methods that (for the most part) are not yet contained in the standard textbooks.

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.