Improved fast replanning for robot navigation in unknown terrain
- 25 June 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 968-975
- https://doi.org/10.1109/robot.2002.1013481
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.Keywords
This publication has 12 references indexed in Scilit:
- GRAMMPS: a generalized mission planner for multiple mobile robots in unstructured environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimal route re-planning for mobile robots: a massively parallel incremental A* algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Path planning and navigation of mobile robots in unknown environmentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Hybrid evolutionary motion planning using follow boundary repair for mobile robotsJournal of Systems Architecture, 2001
- A new solution for path planning in partially known or unknown environment for nonholonomic mobile robotsRobotics and Autonomous Systems, 2001
- Fully Dynamic Algorithms for Maintaining Shortest Paths TreesJournal of Algorithms, 2000
- Experiments with driving modes for urban robotsPublished by SPIE-Intl Soc Optical Eng ,1999
- An incremental algorithm for a generalization of the shortest-path problemPublished by Springer Nature ,1996
- Efficient search and hierarchical motion planning by dynamically maintaining single-source shortest paths treesIEEE Transactions on Robotics and Automation, 1995
- DIFFERENTIAL A*: AN ADAPTIVE SEARCH METHOD ILLUSTRATED WITH ROBOT PATH PLANNING FOR MOVING OBSTACLES AND GOALS, AND AN UNCERTAIN ENVIRONMENTInternational Journal of Pattern Recognition and Artificial Intelligence, 1990