SP3

Real-Time Planning in Dynamic and Partially-Known Domains
Maxim Likhachev and Sven Koenig

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 AI and robotics. This tutorial will present a broad class of search-based approaches to planning in dynamic and 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 will introduce three efficient strategies to planning in dynamic or only partially known domains, namely planning with a 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 will present analytical results about the runtimes and plan qualities. It will then describe algorithms that efficiently implement these strategies and are suitable for use under real-time conditions. The tutorial will show how all of these algorithms gain drastic efficiency by solving the problem with repeated A*-like searches. The tutorial will explain how these algorithms operate, present their theoretical properties and show their application to a variety of planning problems, such as symbolic planning and motion planning for high degree-of-freedom robot arms, outdoor ground robots and air robots.

Maxim Likhachev is a research assistant professor at the Computer and Information Science Department of the University of Pennsylvania. His research interests are primarily in planning for deterministic and probabilistic domains with applications to robotics. He develops planning methods that can be used in real-time, can be analyzed theoretically and are easy to use. Currently, one of the main thrusts of his research is solving complex high-dimensional planning problems with uncertainty using a series of highly efficient and easy-to-implement deterministic searches. Maxim received his Ph.D. in Computer Science from Carnegie Mellon University in 2005. He then held a 2-year postdoctoral appointment at the Robotics Institute of Carnegie Mellon University, where, in one of his projects, he worked on a planner of complex maneuvers for the CMU Tartanracing vehicle that won the 1st place in the 2007 DARPA Urban Challenge. Maxim has applied his ideas to problems such as high-speed robot navigation in unknown and adversarial environments, coordination of multi-agent systems and motion planning of high-degree of freedom articulated robots.

Sven Koenig is an associate professor in the Computer Science Department at the University of Southern California. Most of his research centers around techniques for decision making (planning and learning) that enable single situated agents (such as robots or decision-support systems) and teams of agents to act intelligently in their environments and exhibit goal-directed behavior in real-time, even if they have only incomplete knowledge of their environment, imperfect abilities to manipulate it, limited or noisy perception or insufficient reasoning speed. Sven received his Ph.D. in Computer Science from Carnegie Mellon University. He also holds M.S. degrees from the University of California at Berkeley and Carnegie Mellon University and has published more than 125 papers in various areas of artificial intelligence and robotics. He is the recipient of an NSF CAREER award, an IBM Faculty Partnership Award, a Charles Lee Powell Foundation Award, a Raytheon Faculty Fellowship Award, and an ACM Recognition of Service Award, among others. He co-founded the Robotics: Science and Systems conference, was conference co-chair of the 2004 International Conference on Automated Planning and Scheduling, program co-chair of the 2005 International Joint Conference on Autonomous Agents and Multi-Agent Systems and program co-chair of the 2007 and 2008 AAAI Nectar programs.

(back)