ALAMT  Vol.2 No.2 , June 2012
A Linear Interpolation-Based Algorithm for Path Planning and Replanning on Girds
Abstract: 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.
Cite this paper: 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.

[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.