Abstract
A new synchronized biased-greedy RRT is proposed which leverages the strengths of the biased and greedy RRTs. It combines the advantage of the biased RRT that grows trees towards the goal location, with the ability of the greedy RRT that makes trees traverse the environment in a single iteration. The proposed method achieves performance improvements compared to other RRT variants, not only in computational time but also in the quality of the path. Two enhancements are made to the initial path to relax the sub-optimality of the RRT path; first a path pruning algorithm is executed to eliminate redundant nodes and an anytime strategy is adapted to continuously enhance the quality of the path within the deliberation time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, Cambridge, MA, 2005.
E. Frazzoli, M. Dahleh, and E. Feron, “Real-time motion planning for agile autonomous vehicles,” Proc. of American Control Conference, Arlington, Virginia, June 2001.
S. LaValle and J. Kuffner, “Randomized Kinodynamic planning,” The International Journal of Robotics Research, vol. 20, no. 5, pp. 378–400, May 2001.
D. Ferguson, N. Kalra, and A. Stentz, “Replanning with RRTs,” Proc. of IEEE International Conference on Robotics and Automation, Orlando, Florida, May 2006.
S. LaValle, “Rapidly-exploring random trees: a new tool for path planning,” TR 98-11, Computer Science Dept, Iowa State University, 1998.
J. Saunders, B. Call, A. Curtis, R. Beard, and T. McLain, “Static and dynamic obstacle avoidance in miniature air vehicles,” AIAA Infotech@ Aerospace, Arlington, Virginia, September 2005.
E. Koyuncu, N. Ure, and G. Inalhan, “Integration of path/maneuver planning in complex environments for agile maneuvering UCAVs,” Journal of Intelligent and Robotic Systems, vol. 57, no. 1–4, pp. 143–170, February 2010.
M. Wzorek and P. Doherty, “Reconfigurable path planning for an autonomous unmanned aerial vehicle,” Proc. of IEEE International Conference on Hybrid Information Technology, Cheju, Korea, November 2006.
N. Aminy, D. Boskovic, and K. Raman, “A fast and efficient approach to path planning for unmanned vehicle,” Proc. of AIAA Guidance, Navigation, and Control Conference, Keystone, Colorado, August 2006.
D. Ferguson and A. Stentz, “Anytime RRTs,” Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, China, pp. 5369–5375, October 2006.
M. Kalisiak and M. Panne, “RRT-blossom: RRT with a local flood-fill behavior,” Proc. of IEEE International Conference on Robotics and Automation, Orlando, Florida, pp. 1237–1242, May 2006.
J. Bruce and M. Veloso, “Real-time randomized path planning for robot navigation,” Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne, Switzerland, October 2002.
K. Yang and S. Sukkarieh, “An analytical continuous curvature path smoothing algorithm,” IEEE Trans. on Robotics, vol. 26, no. 3, pp. 561–568, June 2010.
Author information
Authors and Affiliations
Corresponding author
Additional information
Recommended by Editorial Board member Youngjin Choi under the direction of Editor Jae-Bok Song.
Kwangjin Yang received his B.S. degree in Mechanical Engineering from Korea Air Force Academy in 1996, an M.S degree in Mechanical Engineering from Pohang University of Science and Technology in 2002 and a Ph.D. degree in Aerospace, Mechanical and Mechatronic Engineering from the University of Sydney in 2010. His research interests include path planning, RUAV control, cooperative control.
Rights and permissions
About this article
Cite this article
Yang, K. Anytime synchronized-biased-greedy rapidly-exploring random tree path planning in two dimensional complex environments. Int. J. Control Autom. Syst. 9, 750–758 (2011). https://doi.org/10.1007/s12555-011-0417-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12555-011-0417-7