A Linear Interpolation-Based Algorithm for Path Planning and Replanning on Girds


Field D* algorithm is widely used in mobile robot navigation since it can plan and replan any-angle paths through non-uniform cost grids. However, it still suffers from inefficiency and sub-optimality. In this article, a new linear interpolation-based planning and replanning algorithm, Update-Reducing Field D*, is proposed. It employs different approaches during initial planning and replanning respectively in order to reduce the number of updates of the rhs-values of vertices. Experiments have shown that Update-Reducing Field D* runs faster than Field D* and returns smoother and lower-cost paths.

Share and Cite:

C. Zheng, J. Cai and H. Yin, "A Linear Interpolation-Based Algorithm for Path Planning and Replanning on Girds," Advances in Linear Algebra & Matrix Theory, Vol. 2 No. 2, 2012, pp. 20-24. doi: 10.4236/alamt.2012.22003.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] D. Ferguson, M. Likhachev and A. Stentz, “A Guide to Heuristic-Based Path Planning,” Proceedings of the Workshop on Planning under Uncertainty for Autonomous Systems at the International Conference on Automated Planning and Scheduling, Monterey, 5-10 June 2005, pp. 918.
[2] P. Hart, N. Nilsson and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, 1968, Vol. 4, No. 2, pp. 100-107.
[3] S. Koenig, M. Likhachev and D. Furcy, “Lifelong Planning A*,” Artificial Intelligence Journal, Vol. 155, No. 1-2, 2004, pp. 93-146.
[4] S. Koenig and M. Likhachev, “Improved Fast Replanning for Robot Navigation in Unknown Terrain,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2002), Washington, 11-15 May 2002, pp. 968-975.
[5] A. Botea, M. Müller and J. Schaeffer, “Near Optimal Hierarchical Path-Finding,” Journal of Game Development, 2004, Vol. 1, No. 1, pp. 1-22.
[6] A. Nash, K. Daniel, S. Koenig and A. Felner, “Theta*: Any-Angle Path Planning on Grids,” Proceedings of the National Conference on Artificial Intelligence, 22-26 July 2007, Vancouver, pp. 1177-1183.
[7] D. ?i?lák, P. Volf and M. Pěchou?ek, “Accelerated A* Path Planning,” Springer-Verlag, Berlin, 2009.
[8] D. Ferguson and A. Stentz, “The Field D* Algorithm for Improved Path Planning and Replanning in Uniform and Non-Uniform Cost Environments,” Technical Report, Carnegie Mellon University, Pittsburgh, 2005.
[9] M. W. Otte and G. Grudic, “Extracting Paths from Fields Built with Linear Interpolation,” IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, 10-15 October 2009, pp. 4406-4413.
[10] D. Ferguson and A. Stentz, “The Delayed D* Algorithm for Efficient Path Replanning,” Proceedings of the IEEE International Conference on Robotics and Automation, Barcelona, 18-22 April 2005, pp. 2045-2050.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.