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.

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 test problems for nondeterminitsic planners from artificial intelligecena and guidance for empirical robotics researchers for how to localize robots quickly by interleaving planning and plan execution.

We also study path planning for robots in known terrain, including coverage planning and motion planning, with the objective to develop tractable planning methods that result in solutions of high quality.

Overview Publications on Directions on Robot Planning Research

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

Representative Publications on Warehouse Automation

Representative Publications on Collective Construction

The TERMES domain is a multi-agent path finding domain with additional temporal and spatial constraints. We submitted the TERMES domain for a single robot as a benchmark domain to the International Planning Competition (IPC), and it was used in the IPC 2018. You can download its PDDL description or use it in an online planning system.

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