Abstract

Abstract: Planning in nondeterministic domains is typically intractable due to the large number of contingencies. Two techniques for speeding up planning in nondeterministic domains are agent-centered search and assumption-based planning. Both techniques interleave planning in deterministic domains with plan execution. They differ in how they make planning deterministic. To determine how suboptimal their plans are, we study two planning methods for robot navigation in initially unknown terrain that have successfully been used on mobile robots but not been analyzed before. The planning methods differ both in the technique they use to speed up planning and in the robot-navigation task they solve. Greedy Mapping uses agent-centered search to map unknown terrain. Dynamic A* uses assumption-based planning to navigate to a given goal location in unknown terrain. When we formalize abstractions of these planning methods on undirected graphs G=(V,E), they turn out to be similar enough that we are able to analyze their travel distance in a unified way. We discover that neither method is optimal in a worst-case sense, by a factor of Ω(log |V|/log log |V|). We also derive factor O(sqrt(|V|)) upper bounds to show that these methods are not very badly sub-optimal in this sense. These results provide a first step towards explaining the good empirical results that have been reported about Greedy Mapping and Dynamic A* 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.

Download the paper in pdf.

Download the paper in gzipped postscript (large download time).

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.