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

Changwen Zheng, Jiawei Cai, Huafei Yin

National Key Laboratory of Integrated Information System Technology Institute of Software, Chinese Academy of Sciences, Beijing, China.

DOI: 10.4236/alamt.2012.22003                

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.

Keywords

Field D* Algorithm; Path Planning and Replanning; Any-Angle Path; Linear Interpolation; Grid Cell

Conflicts of Interest

The authors declare no conflicts of interest.

References

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