Tutorial on Greedy-Online Planning and its Application to Robot Navigation
Abstract
Mobile robots must be able to make good decisions in complex situations that involve a substantial degree of uncertainty, yet find solutions in a timely manner despite a large number of potential contingencies. Unfortunately, planning in non-deterministic domains is typically time-consuming due to the large number of contingencies. Greedy on-line planning interleaves planning and plan execution, which speeds up planning by sacrificing the optimality of the resulting plans. Examples include agent-centered search and assumption-based planning. Agent-centered search (local search) restricts planning to the part of the terrain around the current location of the robot. Assumption-based planning, on the other hand, makes assumptions about the outcomes of action executions. Both methods have advantageous properties. For example, they do not need to be in control of the robot at all times and are easy to integrate into complete robot architectures.
The tutorial on greedy on-line planning covers algorithms, their analysis using a unifying graph-theoretic framework (including complexity results), and their integration into complete robot architectures. The running example is robot navigation in initially unknown terrain. We will describe complete robot systems for this application and show videos of their operation. The tutorial is completely self-contained and teaches the necessary knowledge from mobile robotics, artificial intelligence, graph theory, and algorithm theory. It should be of interest to both experimental and theoretical researchers that work in the areas of mobile robotics or artificial intelligence.
Speakers
The material for the tutorial has been provided by the two researchers listed below, both of which are experts on the topic of greedy on-line planning. They have been selected to cover the theory of greedy on-line planning as well as practical approaches, including robot navigation software.
Sven Koenig (Georgia Institute of Technology, USA)
Sven Koenig is an assistant professor at Georgia Institute of
Technology. He received his Ph.D. degree from Carnegie Mellon
University for his dissertation on "Goal-Directed Acting with
Incomplete Information." He also holds M.S. degrees from the
University of California at Berkeley and Carnegie Mellon University as
well as German degrees in Management Science and Computer Science.
Sven has published over 50 journal articles, conference papers, and
technical reports. He is the recipient of various awards and
fellowships, including the NSF CAREER award, an IBM Faculty
Partnership Award, the Raytheon Faculty Fellowship Award from Georgia
Tech, the Tong Leong Lim Pre-Doctoral Prize from the University of
California at Berkeley, and a Fulbright Fellowship.
Anthony Stentz (Carnegie Mellon University, USA)
Anthony Stentz is a senior research scientist in the Robotics
Institute at Carnegie Mellon University. He received his B.S. in
Physics from Xavier University in 1982, his M.S. in Computer Science
from Carnegie Mellon University in 1984, and his Ph.D. in Computer
Science from CMU in 1989. Anthony has made contributions in a broad
range of research areas, including robotics, software architecture,
intelligent planning, sensing, and perception. He is best known for
developing D*, a real-time planning algorithm for unknown, uncertain,
and changing environments that has been used in dozens of robot
systems around the world. Anthony has published over 100 journal
articles, conference papers, technical reports, patents, and
videos. He is the recipient of the Alan Newell Award for Research
Excellence.
Tutorial Material
Here are some slides:
Additional Information
Here are pointers to additional material:
For questions or requests of additional information, please send email to Sven Koenig (skoenig@usc.edu).