A. Mudgal, C. Tovey, S. Greenberg and S. Koenig. Bounds on the Travel Cost of a Mars Rover Prototype Search Heuristic. SIAM Journal on Discrete Mathematics, 19, (2), 431-447, 2005.

Abstract: D* is a greedy heuristic planning method that is widely used in robotics, including several Nomad class robots and the Mars Rover Prototype, to reach a destination in unknown terrain. We obtain nearly sharp lower and upper bounds of Ω(n log n / log log n) and O(n log n) respectively on the worst-case total distance traveled by the robot, for the grid graphs on n vertices typically used in robotics applications. For arbitrary graphs, we prove an O(n log2 n) upper bound.

Download the paper in pdf.

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.