Project "Robot Planning Tasks and Methods"
(scroll down for publications)

Path planning for robots in unknown terrain has been studied in both theoretical robotics and theoretical computer science. However, empirical robotics researchers have often developed their own planning methods. These planning methods have been demonstrated on mobile robots that solve complex real-world tasks and perform well in practice. However, they are very different from the planning methods that have traditionally been studied in artificial intelligence, theoretical robotics, and theoretical computer science, and their properties are not yet well understood. In joint work with Craig Tovey, we therefore study the properties of these robot navigation methods (such as Planning with the Freespace Assumption, Greedy Mapping, Avoiding the Past, and Greedy Localization) formally with the goal to understand how good they really are and in which situations they should be used. The results provide guidance for empirical robotics researchers when to use which method and how to improve on them. In particular, we can prove that some common-sense navigation methods developed by empirical robotics researchers indeed result in small travel distances of the robots. These results provide a first step towards explaining the good empirical results that have been reported about these navigation methods in the experimental literature. More generally, they show how to use tools from graph theory to analyze the plan quality of practical planning methods for nondeterministic domains. Empirical researchers have now started to cite our analytical results as justification of their choice of navigation methods, for example, researchers at Carnegie Mellon University. We also study localization. Even though this is a central problem for mobile robots, the question of how difficult it is to localize a robot has not been studied in depth. We can prove that finding good (= within a log factor of optimal) localization plans is already NP-hard but our experiments show that greedy methods often perform well. These results provide guidance for empirical robotics researchers for how to localize robots quickly by interleaving planning and plan execution. This work has also resulted in test problems for nondeterministic planners from artificial intelligence, that are now used by researchers from IRST as part of their test suites for testing their planners. We also study path planning for robots in known terrain, including coverage planning and motion planning. The emphasis of our research is on developing tractable planning methods that result in solutions of high quality.

Representative Publications on Navigating to a Goal

Representative Publications on Mapping

Representative Publications on Localization

Representative Publications on Coverage

Representative Publications on Motion Planning

Representative Publications on Pursuit Evasion

Some of this material is based upon work supported by the National Science Foundation under Grant No. 0098807. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.

Home Page of Sven Koenig