Fast replanning for navigation in unknown terrain

TLDR

Mobile robots often operate in partially known domains, requiring rapid replanning as terrain knowledge updates, and Stentz's Focussed Dynamic A* (D*) achieves this by locally modifying previous search results to find shortest paths faster than planning from scratch, making it widely used in mobile robotics. The study introduces D*/Lite, an alternative to D* that computes identical paths while differing algorithmically. D*/Lite follows the same path‑finding logic as D* but with a simpler, more analyzable algorithm that can be extended in multiple ways. D*/Lite is simple, rigorously analyzable, extendable, and at least as efficient as D*, and its adoption is expected to increase the popularity of D*-like replanning methods.

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/sup */ (D/sup */) 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/sup */ that determines the same paths and thus moves the robot in the same way but is algorithmically different. D/sup */ Lite is simple, can be rigorously analyzed, extendible in multiple ways, and is at least as efficient as D/sup */. We believe that our results will make D/sup */-like replanning methods even more popular and enable robotics researchers to adapt them to additional applications.