SMART PROBABILISTIC ROAD MAP (SMART-PRM): FAST ASYMPTOTICALLY OPTIMAL PATH PLANNING USING SMART SAMPLING STRATEGIES

(Received: 21-Dec.-2023, Revised: 27-Feb.-2024 , Accepted: 14-Mar.-2024)

Authors Muhammad Aria Rajasa Pohan, Jana Utama,

Keywords #Probabilistic road map #Fast asymptotically optimal #Path planning #Intelligent sampling #Informed search

Abstract An asymptotically optimal path-planning guarantees an optimal solution if given sufficient running time. This research proposes a novel, fast, asymptotically optimal path-planning algorithm. The method uses five smart sampling strategies to improve the probabilistic road map (PRM). First, it generates samples using an informed search procedure. Second, it employs incremental search techniques on increasingly dense samples. Third, samples are generated around the best solution. Fourth, generated around obstacles. Fifth, it repairs the found route. This algorithm is called the Smart PRM (Smart-PRM). The Smart-PRM was compared to PRM, informed PRM and informed rapidly-exploring random tree*-connect. Smart-PRM can generate the optimal path for any test case. The shortest distance between the start and goal nodes is the optimal path criterion. Smart-PRM finds the best path faster than competing algorithms. As a result, the Smart-PRM has the potential to be used in a wide variety of applications requiring the best path-planning algorithm.

References

[1] 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, DOI: 10.1109/TRO.2016.2539377, June 2016.

[2] M. Larrañaga, M. Assaad, A. Destounis and G. S. Paschos, "Asymptotically Optimal Pilot Allocation over Markovian Fading Channels," IEEE Transactions on Information Theory, vol. 64, no. 7, pp. 5395-5418, DOI: 10.1109/TIT.2017.2772814, July 2018.

[3] I. Noreen, A. Khan and Z. Habib, "Optimal Path Planning Using RRT* Based Approaches: A Survey and Future Directions," Int. J. of Advanced Computer Science and Applications, vol. 7, no. 11, pp. 97-107, DOI: 10.14569/ijacsa.2016.071114, Jan. 2016.

[4] M. A. Hossain and I. Ferdous, "Autonomous Robot Path Planning in Dynamic Environment Using a New Optimization Technique Inspired by Bacterial Foraging Technique," Robotics and Autonomous Systems, vol. 64, pp.137-141, 2015.

[5] C. Friedrich, A. Csiszar, A. Lechler and A. Verl, "Efficient Task and Path Planning for Maintenance Automation Using a Robot System," in IEEE Transactions on Automation Science and Engineering, vol. 15, no. 3, pp.1205-1215, DOI: 10.1109/TASE.2017.2759814, July 2018.

[6] H. Yang, J. Qi, Y. Miao, H. Sun and J. Li, "A New Robot Navigation Algorithm Based on a Double-layer Ant Algorithm and Trajectory Optimization," IEEE Transactions on Industrial Electronics, vol. 66, no. 11, pp. 8557-8566, 2018.

[7] Y. Rasekhipour, A. Khajepour, S. -K. Chen and B. Litkouhi, "A Potential Field-based Model Predictive Path-planning Controller for Autonomous Road Vehicles," IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 5, pp.1255-1267, DOI: 10.1109/TITS.2016.2604240, May 2017.

[8] M. Diana and J. Marescaux, "Robotic Surgery," British Journal of Surgery, vol. 102, no. 2, pp. e15–e28, DOI: 10.1002/bjs.9711, January 2015.

[9] M. Elbanhawi and M. Simic, "Sampling-based Robot Motion Planning: A Review," IEEE Access, vol. 2, pp. 56-77, DOI: 10.1109/ACCESS.2014.2302442, 2014.

[10] Y. Yang, J. Pan and W. Wan, "Survey of Optimal Motion Planning," IET Cyber‐systems and Robotics, vol. 1, no. 1, pp.13-19, 2019.

[11] R. Mashayekhi, M. Y. I. Idris, M. H. Anisi and I. Ahmedy, "Hybrid RRT: A Semi-dual-tree RRT-based Motion Planner," IEEE Access, vol. 8, pp.18658-18668, DOI: 10.1109/ACCESS.2020.2968471, 2020.

[12] S. Karaman and E. Frazzoli, "Sampling-based Algorithms for Optimal Motion Planning," Int. J. of Robotics Research, vol. 30, no. 7, pp.846-894, Jun. 2011.

[13] H. Qureshi et al., "Triangular Geometry Based Optimal Motion Planning Using RRT*-motion Planner," Proc. of 2014 IEEE 13th Int. Workshop Adv. Motion Control (AMC), pp.380-385, DOI: 10.1109/AMC.2014.6823312, Yokohama, Japan, 2014.

[14] J. Nasir, F. Islam, U. Malik, Y. Ayaz, O. Hasan, M. Khan and M. S. Muhammad, "RRT*-SMART: A Rapid Convergence Implementation of RRT," Int. Journal of Advanced Robotic Systems, vol. 10, no. 7, p. 299, 2013.

[15] I. B.Jeong, S. J. Lee and J. H. Kim, "Quick-RRT*: Triangular Inequality-based Implementation of RRT* with Improved Initial Solution and Convergence Rate," Expert Systems with Applications, vol. 123, pp. 82-90, 2019.

[16] J. D. Gammell, T. D. Barfoot and S. S. Srinivasa, "Informed Sampling for Asymptotically Optimal Path Planning," IEEE Transactions on Robotics, vol. 34, no. 4, pp. 966-984, Aug. 2018.

[17] J. Wang, W. Chi, M. Shao and M. Meng, "Finding a High-quality Initial Solution for the RRTs Algorithms in 2D Environments", Robotica, vol. 37, no. 10, pp. 1677-1694, 2019.

[18] R. Mashayekhi, M. Y. I. Idris, M. H. Anisi, I. Ahmedy and I. Ali, "Informed RRT*-Connect: An Asymptotically Optimal Single-Query Path Planning Method," IEEE Access, vol. 8, pp. 19842-19852, DOI: 10.1109/ACCESS.2020.2969316, 2020.

[19] J. Dai, D. Li, J. Zhao and Y. Li, "Autonomous Navigation of Robots Based on the Improved Informed-RRT Algorithm and DWA," Journal of Robotics, vol. 2022, Article ID: 3477265, pp.1-9, 2022.

[20] H. Ryu and Y. Park, "Improved Informed RRT* Using Gridmap Skeletonization for Mobile Robot Path Planning," Int. J. of Precision Engineering and Manufacturing, vol. 20, no. 11, pp.2033-2039, 2019.

[21] D. Wu, L. Wei, G. Wang, L. Tian and G. Dai, "APF-IRRT*: An Improved Informed Rapidly-exploring Random Trees-star Algorithm by Introducing Artificial Potential Field Method for Mobile Robot Path Planning," Applied Sciences, vol. 12, no. 21, p. 10905, 2022.

[22] M. Aria, "Path Planning Algorithm Using Informed Rapidly Exploring Random Tree*-Connect with Local Search," J. of Eng. Science and Technology, Special Issue on INCITEST, pp. 50-57, 2020.

[23] M. Aria, "Optimal Path Planning Using Informed Probabilistic Road Map Algorithm," Journal of Engineering Research, ASSEEE Special Issue, pp.1-15, DOI: 10.36909/jer.ASSEEE.16105, 2021.

[24] G. Chen, N. Luo, D. Liu, Z. Zhao and C. Liang, "Path Planning for Manipulators Based on an Improved Probabilistic Roadmap Method," Robotics and Computer-Integrated Manufacturing, vol. 72, pp.102196, DOI: 10.1016/j.rcim.2021.102196, 2021.

[25] A. Ravankar, A. Ravankar, T. Emaru and Y. Kobayashi, "HPPRM: Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots," IEEE Access, vol. 8, pp.221743-221766, DOI: 10.1109/ACCESS.2020.3043333, 2020.

[26] C. Liu, S. Xie, X. Sui, Y. Huang, X. Ma, N. Guo and F. Yang, "PRM-D* Method for Mobile Robot Path Planning," Sensors, vol. 23, no. 7, p. 3512, 2023.

[27] J. D. Gammell, T. D. Barfoot and S. S. Srinivasa, "Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search," Int. J. of Robotics Research,, vol. 39, no. 5, pp. 543–567, DOI: 10.1177/0278364919890396, Jan. 2020.

[28] M. Iqbal, K. Zhang, S. Iqbal and I. Tariq, "A Fast and Reliable Dijkstra Algorithm for Online Shortest Path," SSRG Int. J. of Computer Science and Engineering, vol. 5, no. 12, pp. 24–27, DOI: 10.14445/23488387/ijcse-v5i12p106, Dec. 2018.

[29] M. A. R. Pohan, B. R. Trilaksono, S. P. Santosa and A. S. Rohman, "Path Planning Algorithm Using the Hybridization of the Rapidly-exploring Random Tree and Ant Colony systems," IEEE Access, vol. 9, pp. 153599–153615, DOI: 10.1109/access.2021.3127635, Jan. 2021.

[30] M. A. R. Pohan and J. Utama, "Efficient Sampling-based for Mobile Robot Path Planning in a Dynamic Environment Based on the Rapidly-exploring Random Tree and a Rule-template Sets," Int. J. of Engineering, vol. 36, no. 4, pp. 797-806, 2023.

[31] C. Scheffer and J. Vahrenhold, "Approximate Shortest Distances among Smooth Obstacles in 3D," J. of Computational Geometry, vol. 10, no. 1, pp. 389-422, 2019.

[32] M. A. R. Pohan, "Asymptoticcaly-Optimal Path Planning Using the Improved Probabilistic Road Map Algorith," Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali and Elektronika Terapan, vol. 10, no. 2 , pp. 116-127, 2022.

[33] M. I. Abdulakareem and F. A. Raheem, "Development of Path Planning Algorithm Using Probabilistic Roadmap Based on Ant Colony Optimization," Engineering and Technology J., vol. 38, no. 3, pp. 343-351, 2020.

[34] M. A. R. Pohan, "LabVIEW Libraries Untuk Algoritma Perencanaan Jalur Robotik," Telekontran: Jurnal Ilmiah Telekomunikasi, Kendali and Elektronika Terapan, vol. 10, no. 1, pp. 47-62, 2022.

[35] J. Nasir, F. Islam, U. Malik, Y. Ayaz, O. Hasan, M. Khan and M. S. Muhammad, "RRT*-SMART: A Rapid Convergence Implementation of RRT," Int. J. of Advanced Robotic Systems, vol. 10, no. 7, p. 299, 2013.

[36] Y. Xue, X. Zhang, S. Jia, Y. Sun and C. Diao, "Hybrid Bidirectional Rapidly-exploring Random Trees Algorithm with Heuristic Target Graviton," Proc. of 2017 IEEE Chinese Automation Congress (CAC), pp. 4357-4361, DOI: 10.1109/CAC.2017.8243546, Jinan, China, 2017.

[37] M. Al-Khalil, R. Abu-Rhayyem, A. Hammoudeh and T. A. Edwan, "Unmanned Ground Vehicle with Virtual Reality Vision,"Jordanian Journal of Computers and Information Technology (JJCIT), vol. 4, no. 1, pp. 58-79, DOI: 10.5455/jjcit.71-1510942341, April 2018.

[38] M. Aria and J. Utama, "An Autonomous Parking System Using the Hybridization of the Rapidly-Exploring Random Trees Star and Ant Colony System," Journal of Advanced Research in Applied Sciences and Engineering Technology, vol. 31, no. 1, pp. 291-297, 2023.

[39] M. A. R. Pohan and J. Utama, "Efficient Autonomous Road Vehicles Local Path Planning Strategy in Dynamic Urban Environment Using RRT-ACS, Bi-directional Rule Templates and Configuration Time-Space," Journal of Engineering Science and Technology, vol. 18, no. 5, pp. 2388-2397, 2023.

[40] M. Aria, "New Sampling Based Planning Algorithm for Local Path Planning for Autonomous Vehicles," J. of Engineering Science and Technology, Special Issue on INCITEST, pp. 66-76, 2019.