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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:57240", author = "M. Imran Akram and Ahmed Pasha and Nabeel Iqbal", title = "Optimal Path Planner for Autonomous Vehicles", 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.", volume = "1", number = "3", pages = "632-4", }
