Artificial potential field guided JPS algorithm for fast optimal path planning in cluttered environments
Journal of the Brazilian Society of Mechanical Sciences and Engineering - Tập 44 - Trang 1-14 - 2022
Tóm tắt
This paper focuses on the path planning improvement for mobile robots in cluttered environments. Due to the uncertainty of searching direction in traditional path planning algorithms, each node often searches for its following path node in irrelevant directions, which increases the time cost and the number of invalid nodes. In this study, an artificial potential field guided jump point search algorithm is proposed to solve this low-efficiency problem. This method builds an APF and a direction map, which represent resultant force distribution and node directionality to the target node, respectively. Then, with consideration of APF influence and direction map guidance, an expansion direction priority for path planning is calculated, which guides and improves the search for subsequent jump points. To evaluate its performance and efficiency, the APF-JPS algorithm is compared with the conventional JPS, RRT, APF and 8-domains A* algorithms in simulation and mobile robot experiments. The experimental results indicate that the APF-JPS algorithm not only plans the shortest available path with the least time cost, but also reaches the highest node utilization rate. Comparing with the conventional JPS algorithm, which ranks second in overall performance, both the number of key nodes and the path planning time decrease by 45.0% and 53.8%, respectively, while the node utilization rate increases by 23.4%. Therefore, the APF-JPS algorithm shows its advantages in path planning, mainly by reducing the system computational load, improving the real-time performance, and increasing the mobile robot endurance time.
Tài liệu tham khảo
Ge WK, Wang BP (2019) Global path planning method for mobile logistics robot based on raster graph method. Bull Sci Technol 35(11):72–75
Wang C, Piao Z, Li L et al (2020) Path planning for mobile robot using fuzzy controllers with artificial potential field. In: 2020 IEEE international conference on unmanned systems (ICUS). IEEE, pp 391–396
Min H, Lin Y, Wang S et al (2015) Path planning of mobile robot by mixing experience with modified artificial potential field method. Adv Mech Eng 7(4):1–17
Rajvanshi A, Islam S, Majid H et al (2015) An efficient potential-function based path-planning algorithm for mobile robots in dynamic environments with moving targets. Br J Appl Sci Technol 9(6):534–550
Wang HB, Yin PH, Zhen W et al (2020) Mobile robot path planning based on improved A* algorithm and Dynamic Window Method. Robot 42(3):346–353
Rath AK, Parhi DR, Das HC et al (2019) Path optimization for navigation of a humanoid robot using hybridized fuzzy-genetic algorithm. Int J Intell Unmanned Syst 7(1):112–119
Keshari A, Mohanta JC (2019) A Knowledge based fuzzy-probabilistic roadmap method for mobile robots navigation. Appl Soft Comput 79:391–409
Rodriguez S, Tang X, Lien JM, Amato NM (2006) An obstacle-based rapidly-exploring random tree. In: IEEE international conference on robotics & automation. pp 895–900
Adiyatov O, Varol HA (2017) A Novel RRT*-based algorithm for motion planning in dynamic environments. In: IEEE international conference on mechatronics and automation, Japan. pp 1416–1421
Zaid T, Qureshi AH, Yasar A et al (2018) Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments. Robot Auton Syst 108:13–27
Klemm S, Oberlnder J, Hermann A et al (2015) “RRT*-connect: faster, asymptotically optimal motion planning. In: 2015 IEEE international conference on robotics and biomimetics (ROBIO 2015), China. pp 1670–1677
Zhang B, Duan Y, Zhang Y et al (2020) Particle swarm optimization algorithm based on Beetle Antennae Search algorithm to solve path planning problem. In: 2020 IEEE 4th information technology, networking, electronic and automation control conference (ITNEC). IEEE, pp 1586–1589
Khaled A, Farid K (2018) Mobile robot path planning using an improved ant colony optimization. Int J Adv Robot Syst 15(3):1–7
Song B, Wang Z, Sheng L (2016) A new genetic algorithm approach to smooth path planning for mobile robots. Assem Autom 36(2):138–145
Gao PG, Liu ZH, Wu ZK et al (2019) A global path planning algorithm for robots using reinforcement learning. In: Pro. Of the IEEE international conference on robotics and biomimetics, China. pp 1693–1698
Chen QL, Zhen YJ, Jiang HY et al (2021) Improved particle swarm optimization algorithm based on neural network for dynamic path planning. J Huazhong Univ Sci Technol (Natl Sci Ed) 49(2):51–55
Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269–271
Dhulkefl EJ, Durdu A, Terziolu H (2020) Dijkstra algorithm using UAV path planning. Selcuk Univ J Eng Sci Technol 8(8):92–105
Hart PE, Nilsson NJ, Raphael B (1972) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):28–29
Guruji AK, Agarwal H, Parsediya DK (2016) Time-efficient A* algorithm for robot path planning. Procedia Technol 23:144–149
Zhong X, Tian J, Hu H et al (2020) Hybrid path planning based on Safe A* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment. J Intell Robot Syst 99(1):65–77
Cheng C, Hao X, Li J et al (2017) Global dynamic path planning based on fusion of improved A* algorithm and dynamic window approach. J Xi’an Jiaotong Univ 51(11):137–143
Harabor D, Grastien A (2011) Online graph pruning for pathfinding on grid maps. In: Aaai conference on artificial intelligence. pp 1–6
Ma XL, Mei H (2020) Research of bidirectional jump point search algorithm of global path planning for mobile robots. Mech Sci Technol Aerosp Eng 39(10):1642–1631
Zheng X, Tu X, Yang Q (2019) Improved JPS algorithm using new jump point for path planning of mobile robot. In: 2019 IEEE international conference on mechatronics and automation (ICMA). pp 2643–2648
Wu P, Gao F, Li K (2022) Humanlike decision and motion planning for expressway lane changing based on artificial potential field. IEEE Access 10:4359–4373