Abstract

Abstract: Mobile robots often operate in domains that are only incompletely known, for example, when they have to move from given start coordinates to given goal coordinates in unknown terrain. In this case, they need to be able to replan quickly as their knowledge of the terrain changes. Stentz' Focussed Dynamic A* (D*) is a heuristic search method that repeatedly determines a shortest path from the current robot coordinates to the goal coordinates while the robot moves along the path. It is able to replan faster than planning from scratch since it modifies its previous search results locally. Consequently, it has been extensively used in mobile robotics. In this article, we introduce an alternative to D* that determines the same paths and thus moves the robot in the same way but is algorithmically different. D* Lite is simple, can be rigorously analyzed, extendible in multiple ways, and is at least as efficient as D*. We believe that our results will make D*-like replanning methods even more popular and enable robotics researchers to adapt them to additional applications. Comment: In the experiments, the non-incremental search methods replanned whenever untraversable cells are observed. One can speed them up greatly by letting them replan only whenever untraversable cells are observed on the current path, in which case D* Lite loses its advantage on small grids. Also, the speed-up of D* Lite is, in general, larger on four-neighbor than eight-neighbor grids.

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.