Fast Replanning for Navigation in Unknown Terrain

June 2005

Fast Replanning for Navigation in Unknown Terrain

Authors:

Sven Koenig and Maxim Likhachev

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.
@article{Koenig-2005-109501,
author = {Sven Koenig And Maxim Likhachev},
title = {Fast Replanning for Navigation in Unknown Terrain},
journal = {Proceedings of IEEE Transactions on Robotics},
year = {2005},
month = {June},
volume = {21},
number = {3},
pages = {354 - 363},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.