Tutorial on Greedy-Online Planning and its Application to Robot Navigation


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.


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).

Home Page of Sven Koenig