Optimal Path Planner for Autonomous Vehicles

Authors: M. Imran Akram, Ahmed Pasha, Nabeel Iqbal

Abstract:

In this paper a real-time trajectory generation algorithm for computing 2-D optimal paths for autonomous aerial vehicles has been discussed. A dynamic programming approach is adopted to compute k-best paths by minimizing a cost function. Collision detection is implemented to detect intersection of the paths with obstacles. Our contribution is a novel approach to the problem of trajectory generation that is computationally efficient and offers considerable gain over existing techniques.

Keywords: dynamic programming, graph search, path planning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070367

References:

[1] J. F. Canny and M. C. Lin, "An opportunistic global path planner," Algorithmica, vol. 10, 1993, pp 102-120.
[2] L. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars. "Probabilistic roadmaps for path planning in high-dimensional configuration space," IEEE Trans. on Robotics and Automation, 12(4): 1996, pp. 566-580.
[3] R. Bohlin and L. E. Kavraki, "Path planning using lazy PRM," in Proceedings of the International Conference on Robotics and Automation, vol. 1, 2000, pp 521-528.
[4] R. W. Beard, T. W. McLain, M. Goodrich, and E. P. Anderson, "Coordinated target assignment and intercept for unmanned air vehicles," IEEE Transactions on Robotics and Automation, vol. 18, December 2002, pp. 911-922.
[5] T. McLain and R. Beard, "Cooperative rendezvous of multiple unmanned air vehicles," in Proc. AIAA Guidance, Navigation and Control Conf., Denver, CO, Aug. 2000, AIAA Paper 2000-4369 (CDROM).
[6] W.B. Randal, W. M. Timothy, "Coordinated target assignment and intercept for Unmanned Air Vehicles," in proceedings of the 2002 IEEE International Conference On Robotics & Automation, Washington, DC. May 2002.
[7] E. P. Anderson, R.W. Beard, "An algorithmic implementation of constrained extremal control for UAVs," AIAA Guidance, Navigation, and Control Conference and Exhibit 5-8 August 2002, Moneterey, California.
[8] P. Chandler, S. Rasumussen, and M. Pachter, "UAV cooperative path planning," in Proc. AIAA Guidance, Navigation, and Control Conf., Denver, CO, Aug. 2000, AIAA Paper 2000-4370.
[9] R. Sedgewick, Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1988.
[10] R. V. Helgason, J. L. Kennington, K. R. Lewis, "Cruise missile mission planning: A heuristic algorithm for automatic path generation," Journal of Heuristics, vol. 7, 2001, pp. 473-494.
[11] R. Helgason, J. Kennington, and K. Lewis. (1997a), "Cruise missile mission planning with a probability side constraint," Technical Report 97-CSE-3, Department of Computer Science and Engineering, SMU, Dallas, TX 75275-0122.
[12] R. Helgason, J. Kennington, and K. Lewis. (1997a), "Cruise missile strike planning: Automatic multiple path generation," Technical Report 97-CSE-24, Department of Computer Science and Engineering, SMU, Dallas, TX 75275-0122.
[13] M. B. Milam, K. Mushambi, and R. M. Murray, "A computational approach to real-time trajectory generation for constrained mechanical systems," in Proc. IEEE Conf. Decision and Control, Sydney, Australia, 2000, pp. 845-851.
[14] S. Sun, M. B. Egerstedt, and C. F. Martin, "Control theoretic smoothing splines," IEEE Trans. Automat. Contr., vol. 45, Dec. 2000, pp. 2271- 2279.
[15] G. Yang, V. Kapila, "Optimal path planning for unmanned air vehicles with kinematic and tactical constraints", Proceedings of the 41st IEEE Conference on Decision and Control Las Vegas, Nevada USA, December 2002.
[16] D. Eppstein, "Finding the k shortest paths," SIAM Journal of Computing, vol. 28, no. 2, 1998, pp. 995-1020.