RRT*-SMART: A Rapid Convergence Implementation of RRT*

Jauwairia Nasir; Fahad Islam; Usman Malik; Yasar Ayaz; Osman Hasan; Mushtaq Khan; Mannan Saeed Muhammad

doi:10.5772/56718

journal article Jan 01, 2013

RRT-SMART: A Rapid Convergence Implementation of RRT

Jauwairia Nasir

Fahad Islam Usman Malik Yasar Ayaz Osman Hasan Mushtaq Khan Mannan Saeed Muhammad

International Journal of Advanced Robotic Systems Vol. 10 No. 7 · SAGE Publications

View at Publisher Save 10.5772/56718

Abstract

Many sampling based algorithms have been introduced recently. Among them Rapidly Exploring Random Tree (RRT) is one of the quickest and the most efficient obstacle free path finding algorithm. Although it ensures probabilistic completeness, it cannot guarantee finding the most optimal path. Rapidly Exploring Random Tree Star (RRT*), a recently proposed extension of RRT, claims to achieve convergence towards the optimal solution thus ensuring asymptotic optimality along with probabilistic completeness. However, it has been proven to take an infinite time to do so and with a slow convergence rate. In this paper an extension of RRT*, called as RRT*-Smart, has been prposed to overcome the limitaions of RRT*. The goal of the proposecd method is to accelerate the rate of convergence, in order to reach an optimum or near optimum solution at a much faster rate, thus reducing the execution time. The novel approach of the proposed algorithm makes use of two new techniques in RRT*–Path Optimization and Intelligent Sampling. Simulation results presented in various obstacle cluttered environments along with statistical and mathematical analysis confirm the efficiency of the proposed RRT*-Smart algorithm.

Topics

No keywords indexed for this article. Browse by subject →

References

22

[1]

Kanehara M., Kagami S., Kuffner J.J., Thompson S., Mizoguhi H. (2007) “Path shortening and smoothing of grid-based path planning with consideration of obstacles”, IEEE International Conference on Systems, Man and Cybernetics, (ISIC), pp. 991–996. 10.1109/icsmc.2007.4414077

[2]

Petrovic I. and Brezak M. (2011) “A visibility graph based method for path planning in dynamic environments”, in proceedings of 34th International Convention on Information and Commuincation Technology, Electronics and Microelectronics (MIPRO), pp. 711–716.

[3]

Sleumer N.H. (1999)

[4]

10.1109/70.127236

[5]

Ghorbani A., Sasa Shiry, and Nodehi A. (2009) “Using Genetic Algorithm for a Mobile Robot Path Planning”, Proceedings of the 2009 International Conference on Future Computer and Communication (ICFCC). pp. 164–166. 10.1109/icfcc.2009.28

[6]

10.1109/tsmcb.2003.811769

[7]

Geraerts Roland (2006)

[8]

Geraerts Roland (2006) “On Experimental Research in Sampling-based Motion Planning”, In (IROS) Workshop on Benchmarks in Robotics Research, pp. 31–34.

[9]

Lavalle S.M. (1998)

[10]

Sampling-based algorithms for optimal motion planning

Sertac Karaman, Emilio Frazzoli

The International Journal of Robotics Research 10.1177/0278364911406761

[11]

Garcia I., How J. P. (2005) “Improving the efficiency of Rapidly-exploring Random Trees Using a Potential Function Planner”, in the proceedings of 44th IEEE Conference on Decision and Control, and the European Control Conference, pp. 7965–7970. 10.1109/cdc.2005.1583450

[12]

10.1109/his.2008.74

[13]

Kuffner J. and LaValle S. M. (Apr. 2000) RRT-connect: “An efficient approach to single-query path planning”, in Proc. of IEEE Intl. Conf. on Robotics and Automation, pp. 995–1001. 10.1109/robot.2000.844730

[14]

10.1109/70.508439

[15]

10.1142/s0218195999000285

[16]

Randomized Kinodynamic Planning

Steven M. LaValle, James J. Kuffner

The International Journal of Robotics Research 10.1177/02783640122067453

[17]

10.1109/tro.2011.2160466

[18]

Lavalle S. M. and Kuffner J.J. (2000) “Rapidly Exploring Random Trees: Progress and Prospects”, In Proceedings Workshop on the Algorithmic Foundations of Robotics.

[19]

Karaman S., Walter Matthew R., Parez A., Farazolli E. and Teller S. (2011) “Anytime Motion Planning using the RRT”, in proceedings of International Conference on Robotic and Automation, pp. 1478–1483. 10.1109/icra.2011.5980479

[20]

Zucker M., Kuffner J. and Branicky M. (2007) “Multipartite RRTs for Rapid Replanning in Dynamic Environments”, in Proc. Of Internation Conference on Robotics and Automation, pp. 1603–160. 10.1109/robot.2007.363553

[21]

Bialkowski, Karaman S., and Frazzoli E. (2011) “Massively Parallelizing the RRT and the RRT*,” in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 10.1109/iros.2011.6048813

[22]

Latombe J.C. (1990)

Cited By

214

Urban mobile robot routing using fast search random tree method (RRT) in obstacle environments

Hsin-Yin Hsieh, Kuan‑Hung Chen · 2024

Journal of the Brazilian Society of...

An improved RRT algorithm based on prior AIS information and DP compression for ship path planning

Qiyong Gu, Rong Zhen · 2023

Ocean Engineering

Online planning for relative optimal and safe paths for USVs using a dual sampling domain reduction-based RRT* method

Naifeng Wen, Rubo Zhang · 2020

International Journal of Machine Le...

Metrics

214

Citations

22

References

Details

Published: Jan 01, 2013
Vol/Issue: 10(7)
License: View

Authors

J

Jauwairia Nasir

Robotics & Intelligent Systems Engineering (RISE) Lab, Department of Robotics and Artificial Intelligence, School of Mechanical & Manufacturing Engineering (SMME), National University of Sciences and Technology (NUST), Islamabad, Pakistan; Department of Electrical Engineering, School of Electrical Engineering & Computer Sciences (SEECS), National University of Sciences and Technology (NUST), Islamabad, Pakistan

F

Fahad Islam

Robotics & Intelligent Systems Engineering (RISE) Lab, Department of Robotics and Artificial Intelligence, School of Mechanical & Manufacturing Engineering (SMME), National University of Sciences and Technology (NUST), Islamabad, Pakistan; Department of Electrical Engineering, School of Electrical Engineering & Computer Sciences (SEECS), National University of Sciences and Technology (NUST), Islamabad, Pakistan

U

Usman Malik

Robotics & Intelligent Systems Engineering (RISE) Lab, Department of Robotics and Artificial Intelligence, School of Mechanical & Manufacturing Engineering (SMME), National University of Sciences and Technology (NUST), Islamabad, Pakistan

Y

Yasar Ayaz

Robotics & Intelligent Systems Engineering (RISE) Lab, Department of Robotics and Artificial Intelligence, School of Mechanical & Manufacturing Engineering (SMME), National University of Sciences and Technology (NUST), Islamabad, Pakistan

O

Osman Hasan

Department of Electrical Engineering, School of Electrical Engineering & Computer Sciences (SEECS), National University of Sciences and Technology (NUST), Islamabad, Pakistan

M

Mushtaq Khan

Robotics & Intelligent Systems Engineering (RISE) Lab, Department of Robotics and Artificial Intelligence, School of Mechanical & Manufacturing Engineering (SMME), National University of Sciences and Technology (NUST), Islamabad, Pakistan

M

Mannan Saeed Muhammad

Robotics & Intelligent Systems Engineering (RISE) Lab, Department of Robotics and Artificial Intelligence, School of Mechanical & Manufacturing Engineering (SMME), National University of Sciences and Technology (NUST), Islamabad, Pakistan; Department of Electronic Engineering, College of Engineering, Hanyang University, Seoul, South Korea

Cite This Article

Jauwairia Nasir, Fahad Islam, Usman Malik, et al. (2013). RRT*-SMART: A Rapid Convergence Implementation of RRT*. International Journal of Advanced Robotic Systems, 10(7). https://doi.org/10.5772/56718

RRT*-SMART: A Rapid Convergence Implementation of RRT*

You May Also Like

RRT-SMART: A Rapid Convergence Implementation of RRT