Abstract

Abstract: Incremental heuristic search methods can often replan much faster than incremental or heuristic searches individually, yet are simple to use. So far, they have only been used in mobile robotics to move a robot to given goal coordinates in unknown terrain. As far as we know, neither incremental heuristic search methods nor, more generally, heuristic search methods have been applied to the problem of mapping unknown terrain. In this paper, we therefore describe how to apply our incremental heuristic search method D* Lite, that combines ideas from Lifelong Planning A* and Focussed D*, to mapping of unknown terrain, which is rather nontrivial. We then compare its runtime against that of incremental search and heuristic search alone, demonstrating the computational benefits of their combination. By demonstrating the versatility and computational benefits of incremental heuristic search, we hope that this underexploited technique will be used more often in mobile robotics.

The proofs can be found in a technical report.

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.