Abstract

A. Mudgal, C. Tovey and S. Koenig. Analysis of Greedy Robot-Navigation Methods. InAbstract: Robots often have to navigate robustly despite incomplete information about
the terrain or their location in the terrain. In this case, they often use
greedy methods to make planning tractable. In this paper, we analyze two such
robot-navigation methods. The first method is Greedy Localization, which
determines the location of a robot in known terrain by always moving it to the
closest location from which it will make an observation that reduces the
number of its possible locations, until it has reduced that number as much as
possible. We reduce the upper bound on the number of movements of Greedy
Localization from O(n^{3/2}) to O(n log n) on grid graphs and thus
close to the known lower bound of Ω(n log n/ log log n), where n is the
number of (unblocked) vertices of the graph that discretizes the terrain. The
second method is Dynamic A* (D*), which is used on several prototypes of both
urban reconnaissance and planetary robots. It moves a robot in initially
unknown terrain from given start coordinates to given goal coordinates by
always moving the robot on a shortest presumed unblocked path from its current
coordinates to the goal coordinates, pretending that unknown terrain is
unblocked, until it has reached the goal coordinates or there are no more
presumed unblocked paths. We reduce the upper bound on the number of movements
of D* from O(n^^{3/2}) to O(n log^{2} n) on arbitrary graphs
and O(n log n) on planar graphs (including grid graphs) and thus close to the
known lower bound of Ω(n log n/ log log n), where n is the number of
(blocked and unblocked) vertices of the graph that discretizes the terrain.

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.