Title:
Improved Fast Replanning for Robot Navigation in Unknown Terrain
Improved Fast Replanning for Robot Navigation in Unknown Terrain
Author(s)
Koenig, Sven
Likhachev, Maxim
Likhachev, Maxim
Advisor(s)
Editor(s)
Collections
Supplementary to
Permanent Link
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* 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 one to two orders of magnitudes
faster than planning from scratch since it modifies previous
search results locally. Consequently, it has been extensively used
in mobile robotics. In this paper, we introduce an alternative to
Focussed Dynamic A* that implements the same navigation strategy
but is algorithmically different. Focussed Dynamic A* Lite is
simpler, easier to understand, easier to analyze and easier to extend
than Focussed Dynamic A*, yet is more efficient. We believe
that our results will make D*-like replanning algorithms even more
popular and enable robotics researchers to adapt them to additional
applications.
Sponsor
Date Issued
2002
Extent
Resource Type
Text
Resource Subtype
Paper