Abstract
A randomized sampling-based path planning algorithm for holonomic mobile robots in complex configuration spaces is proposed in this article. A complex configuration space for path planning algorithms may cause different environmental constraints including the convex/concave obstacles, narrow passages, maze-like spaces and cluttered obstacles. The number of vertices and edges of a search tree for path planning in these configuration spaces would increase through the conventional randomized sampling-based algorithm leading to exacerbation of computational complexity and required runtime. The proposed path planning algorithm is named fuzzy greedy rapidly-exploring random tree (FG-RRT). The FG-RRT is equipped with a fuzzy inference system (FIS) consisting of two inputs, one output and nine rules. The first input is a Euclidean function applied in evaluating the quantity of selected parent vertex. The second input is a metaheuristic function applied in evaluating the quality of selected parent vertex. The output indicates the competency of the selected parent vertex for generating a random offspring vertex. This algorithm controls the tree edges growth direction and density in different places of the configuration space concurrently. The proposed method is implemented on a Single Board Computer (SBC) through the xPC Target to evaluate this algorithm. For this purpose four test-cases are designed with different complexity. The results of the Processor-in-the-Loop (PIL) tests indicate that FG-RRT algorithm reduces the required runtime and computational complexity in comparison with the conventional and greedy RRT through fewer number of vertices in planning an initial path in significant manner.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Finn and S. Scheding, Developments and Challenges for Autonomous Unmanned Vehicles, Springer, Berlin, 2012.
C. C. Insaurralde, Intelligent Autonomy for Unmanned Marine Vehicles, Springer, Switzerland, 2015.
T. T. Mac, C. Copot, D. T. Tran, and R. D. Keyser, “Heuristic approaches in robot path planning: a survey,” Robotics and Autonomous Systems, vol. 86, pp. 13–28, 2016.
R. Grabowski, “Big picture for autonomy research in DoD,” Soft and Secure Systems and Software and SW Symposium, 2015.
T. L. Perez and M. A. Wesley, “An algorithm for planning collision-free paths among polyhedral obstacles,” Communications of the ACM, vol. 22, no. 10, pp. 560–570, 1979.
S. Tang, W. Khaksar, N. Ismail, and M. Ariffin, “A review on robot motion planning approaches,” Pertanika Journal of Science and Technology, vol. 20, no. 1, pp. 15–29, 2012.
E. Masehian and D. Sedighizadeh, “Classic and heuristic approaches in robot motion planning-a chronological review,” World Academy of Science, Engineering and Technology, vol. 29, no. 1, pp. 101–106, 2007.
Y. Quinonez, F. Barrera, I. Bugueno, and J. B. Calfa, “Simulation and path planning for quadcopter obstacle avoidance in indoor environments using the ROS framework,” Proc. of the International Conf. Software Process Improvement, pp. 295–304, 2017.
M. Candeloro, A. M. Lekkas, and A. J. Sorensen, “A voronoi-diagram-based dynamic path-planning system for underactuated marine vessels,” Control Engineering Practice, vol. 61, pp. 41–54, 2017.
E. Masehian and M. R. A. Naseri, “A voronoi diagramvisibility graph-potential field compound algorithm for robot path planning,” Journal of Field Robotics, vol. 21, no. 6, pp. 275–300, 2004.
R. Gonzalez, M. Kloetzer, and C. Mahulea, “Comparative study of trajectories resulted from cell decomposition path planning approaches,” Proc. of the 21st International Conf. System Theory, Control and Computing, pp. 49–54, 2017.
Y. Chen, G. Luo, Y. Mei, J. Yu, and X. Su, “UAV path planning using artificial potential field method updated by optimal control theory,” International Journal of Systems Science, vol. 47, no. 6, pp. 1407–1420, 2014.
J. T. Schwartz, and M. Sharir, “On the piano movers’ problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers,” Communications on Pure and Applied Mathematics, vol. 36, no. 3, pp. 345–398, 1983.
S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” The International Journal of Robotics Research, vol. 30, no. 7, pp. 846–894, 2011.
L. E Kavraki, P. Svestka, J. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in highdimensional configuration spaces,” IEEE transactions on Robotics and Automation, vol. 12, no. 4, pp. 566–580, 1996.
S. M. Lavalle, “Rapidly-exploring random trees: a new tool for path planning,” Citeseer, 1998.
K. Yang, Y. Kang, and S. Sukkarieh, “Adaptive nonlinear model predictive path-following control for a fixed-wing unmanned aerial vehicl,” International Journal of Control, Automation and Systems, vol. 11, no. 1, pp. 65–74, 2013.
M. C. Kim and J.B. Song, “Informed RRT* with improved converging rate by adopting wrapping procedure,” Intelligent Service Robotics, vol. 11, no. 1, pp. 53–60, 2017.
I. Noreen, A. Khan, and Z. Habib, “A comparison of RRT, RRT* and RRT*-smart path planning algorithms,” International Journal of Computer Science and Network Security, vol. 16, no. 10, pp. 20–27, 2016.
A. Perez, R. Platt, G. Konidaris, L. Kaelbling, and T. L. Perez, “LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics,” Proc. of the IEEE International Conf. Robotics and Automation, pp. 2537–2542, 2012.
J. J. Kuffner and S. M. LaValle, “RRT-connect: an efficient approach to single-query path planning,” Proc. of the IEEE International Conf. Robotics and Automation, pp. 995–1001, 2000.
D. Schneider, E. Schomerr, and N. Wolpert, “Completely randomized RRT-connect: a case study on 3D rigid body motion planning,” Proc. of the IEEE International Conf. Robotics and Automation, pp. 2944–2950, 2015.
D. J. Webb and J. V. D. Berg, “Kinodynamic RRT*: asymptotically optimal motion planning for robots with linear dynamics,” Proc. of the IEEE International Conf. Robotics and Automation, pp. 5054–5061, 2013.
R. C. Luo and C. Huang, “Anytime dynamic exploring rapid random tree approach in higher dimension search space for non-holonomic robotics,” Proc. of the International Conf. Advanced Robotics and Intelligent Systems, pp. 1–6, 2016.
Y. Dong, E. Camci, and E. Kayacan, “Faster RRT-based nonholonomic path planning in 2D building environments using skeleton-constrained path biasing,” Journal of Intelligent and Robotic Systems, vol. 89, pp. 387–401, 2018.
L. Palmieri, S. Koenig, and K. Arras, “RRT-based nonholonomic motion planning using any-angle path biasing,” Proc. of the IEEE International Conf. Robotics and Automation, pp. 2775–2781, 2016.
F. Burget, M. Bennewitz, and W. Burgard, “BI2RRT*: An efcient sampling-based path planning framework for taskconstrained mobile manipulation,” Proc. of the IEEE International Conf. Intelligent Robots and Systems, pp. 3714–3721, 2016.
D. Kim, J. Lee, and S. Yoon, “Cloud RRT*: Sampling cloud based RRT*,” Proc. of the IEEE International Conf. Robotics and Automation, pp. 2519–2526, 2014.
M. Elbanhawi, M. Simic, and R. Jazar, “Randomized bidirectional b-spline parameterization motion planning,” IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 2, pp. 406–419, 2016.
I. Noreen, A. Khan, H. Ryu, N. L. Doh, and Z. Habib, “Optimal path planning in cluttered environment using RRT*-AB,” Intelligent Service Robotics, vol. 11, no. 1, pp. 41–52, 2018.
R. Cui, Y. Li, and W. Yan, “Mutual information based multi-AUV path planning for scalar field sampling using multidimensional RRT*,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 46, no. 7, pp. 993–1004, 2016.
O. Salzman and D. Halperin, “Asymptotically near-optimal RRT for fast, high-quality motion planning,” IEEE Transactions on Robotics, vol. 32, no. 3, pp. 473–483, 2016.
D. Devaurs, T. Simeon, and J. Cortes, “A multi-tree extension of the transition-based RRT: application to orderingand-pathfinding problems in continuous cost spaces,” Proc. of the IEEE International Conf. Intelligent Robots and Systems, pp. 2991–2996, 2014.
W. Y. Shin, J. J. Shin, B. Kim, and K. Jeong, “Line segment selection method for fast path planning,” International Journal of Control, Automation and Systems, vol. 15, no. 3, pp. 1322–1331, 2017.
C. H. Kim and S. Sugano, “Closed loop trajectory optimization based on reverse time tree,” International Journal of Control, Automation and Systems, vol. 14, no. 6, pp. 1404–1412, 2017.
K. Yang, “Anytime synchronized-biased-greedy rapidlyexploring random tree path planning in two dimensional complex environments,” International Journal of Control, Automation and Systems, vol. 9, no. 4, pp. 750–758, 2011.
C. Moon and W. Chung, “Kinodynamic planner dual-tree RRT (DT-RRT) for two-wheeled mobile robots using the rapidly exploring random tree,” IEEE Transactions on Industrial Electronics, vol. 62, no. 2, pp. 1080–1090, 2015.
L. Palmieri and K. Arras, “Distance metric learning for RRT-based motion planning with constant-time inference,” Proc. of the IEEE International Conf. Robotics and Automation, pp. 637–643, 2015.
S. Khanmohammadi and A. Mahdizadeh, “Density avoided sampling: an intelligent sampling technique for rapidlyexploring random trees,” Proc. of the Eighth International Conf. Hybrid Intelligent Systems, pp. 672–677, 2008.
S. Lee, H. Bang, and D. Lee, “Predictive ground collision avoidance system for UAV applications: PGCAS design for fixed-wing UAVs and processor in the loop simulation,” Proc. of the International Conf. Unmanned Aircraft Systems, pp. 1287–1292, 2016.
Author information
Authors and Affiliations
Corresponding author
Additional information
Recommended by Associate Editor DaeEun Kim under the direction of Editor Euntai Kim.
Ehsan Taheri was born in Iran in 1984. He received his B.Sc. degree in electrical engineering and his M.S. degree in control engineering, in 2006 and 2008, respectively from the Islamic Azad University, Najafabad Branch and Malek Ashtar University of Technology. Currently, he is a Ph.D. candidate in the Malek Ashtar University of Technology. His research interests include Autonomy, Underwater Robots, Path planning, heuristic optimization, and Motion Control.
Mohammad Hossein Ferdowsi received his BSc and MSc degrees in electrical engineering from Sharif University of Technology and his Ph.D. degree in electrical engineering from University of Tehran, in 1977, 1980, and 2004, respectively. From 1985 to 1987, he was a lecturer at Sharif University of Technology, and since 1987, has been at Malek Ashtar University of Technology as a faculty member. His research interest is in multivariable and adaptive control systems, intelligent systems, and target tracking.
Mohammad Danesh received his B.Sc., M.Sc., and Ph.D. degrees in control engineering from the Isfahan University of Technology (IUT), Isfahan, Iran, in 1997, 1999, and 2007, respectively. He has been with the department of Mechanical Engineering, IUT, since 2007. His current research interests include robotics, intelligent systems, mechatronics, control of dynamical systems, and stability analysis.
Rights and permissions
About this article
Cite this article
Taheri, E., Ferdowsi, M.H. & Danesh, M. Fuzzy Greedy RRT Path Planning Algorithm in a Complex Configuration Space. Int. J. Control Autom. Syst. 16, 3026–3035 (2018). https://doi.org/10.1007/s12555-018-0037-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12555-018-0037-6