The path planning problem of complex wild environment with multiple elements still poses challenges. This paper designs an algorithm that integrates global and local planning to apply to the wild environmental path planning. The modeling process of wild environment map is designed. Three optimization strategies are designed to improve the A-Star in overcoming the problems of touching the edge of obstacles, redundant nodes and twisting paths. A new weighted cost function is designed to achieve different planning modes. Furthermore, the improved dynamic window approach (DWA) is designed to avoid local optimality and improve time efficiency compare to traditional DWA. For the necessary path re-planning of wild environment, the improved A-Star is integrated with the improved DWA to solve re-planning problem of unknown and moving obstacles in wild environment with multiple elements. The improved fusion algorithm effectively solves problems and consumes less time, and the simulation results verify the effectiveness of improved algorithms above.
DONG Dejin1,2 (董德金), DONG Shiyin3 (董诗音), ZHANG Lulu1,2 (章露露), CAI Yunze1,2∗ (蔡云泽)
. Multi-AGVs Scheduling with Vehicle Conflict Consideration in Ship Outfitting Items Warehouse[J]. Journal of Shanghai Jiaotong University(Science), 2024
, 29(4)
: 725
-736
.
DOI: 10.1007/s12204-024-2731-2
[1] WANG L, WANG B, WANG C X. Collision-free path planning with kinematic constraints in urban scenarios [J]. Journal of Shanghai Jiao Tong University (Science), 2021, 26(5): 731-738.
[2] PADEN B, ˇC′ AP M, YONG S Z, et al. A survey of motion planning and control techniques for self-driving urban vehicles [J]. IEEE Transactions on Intelligent Vehicles, 2016, 1(1): 33-55.
[3] ROCHA L, ANICETO M, ARA′UJO I, et al. A UAV global planner to improve path planning in unstructured environments [C]//2021 International Conference on Unmanned Aircraft Systems. Athens: IEEE, 2021: 688-697.
[4] JANIS A, BADE A. Path planning algorithm in complex environment: A survey [J]. Transactions on Science and Technology, 2016, 3(1): 31-40.
[5] TANG Z Z, MA H Z. An overview of path planning algorithms [J]. IOP Conference Series: Earth and Environmental Science, 2021, 804(2): 022024.
[6] HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
[7] TANG G, TANG C Q, CLARAMUNT C, et al. Geometric A-star algorithm: An improved A-star algorithm for AGV path planning in a port environment [J]. IEEE Access, 2021, 9: 59196-59210.
[8] LI Y B, WANG Z X, ZHANG S Y. Path planning of robots based on an improved A-star algorithm [C]//2022 IEEE 5th Advanced Information Management, Communicates, Electronic and Automation Control Conference. Chongqing: IEEE, 2022: 826-831.
[9] JIA L, ZHENG J, NIU G, et al. Path planning method based on multi-direction improved A-Star algorithm [C]//Proceedings of 2022 Chinese Intelligent Systems Conference. Singapore: Springer, 2022: 715-726.
[10] JU C Y, LUO Q H, YAN X Z. Path planning using an improved A-star algorithm [C]//2020 11th International Conference on Prognostics and System Health Management. Jinan: IEEE, 2020: 23-26.
[11] ZHANG J, WU J, SHEN X, et al. Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star [J]. International Journal of Advanced Robotic Systems, 2021, 18(5):17298814211042730.
[12] FOX D, BURGARD W, THRUN S. The dynamic window approach to collision avoidance [J]. IEEE Robotics & Automation Magazine, 1997, 4(1): 23-33.
[13] YAN X Z, DING R C, LUO Q H, et al. A dynamic path planning algorithm based on the improved DWA algorithm [C]//2022 Global Reliability and Prognostics and Health Management. Yantai: IEEE, 2022: 1-7.
[14] CHANG L, SHAN L, JIANG C, et al. Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment [J]. Autonomous Robots, 2021, 45(1): 51-76.
[15] WU Y, LOW K H. An adaptive path replanning method for coordinated operations of drone in dynamic urban environments [J]. IEEE Systems Journal, 2021, 15(3): 4600-4611.
[16] TONOLA C, FARONI M, BESCHI M, et al. Anytime informed multi-path replanning strategy for complex environments [J]. IEEE Access, 2023, 11: 4105-4116.
[17] LIU X L, DU X J, ZHANG X S, et al. Evolutionalgorithm-based unmanned aerial vehicles path planning in complex environment [J]. Computers & Electrical Engineering, 2019, 80: 106493.
[18] STENTZ A. The focussed D* algorithm for realtime replanning [C]//14th International Joint Conference on Artificial Intelligence. Montreal: IJCAI, 1995: 1652-1659.
[19] YU J, LIU G D, ZHAO Z Y, et al. Improved D?Lite algorithm path planning in complex environment [C]//2020 Chinese Automation Congress. Shanghai: IEEE, 2020: 2226-2230.
[20] XIE R L, MENG Z J, WANG L F, et al. Unmanned aerial vehicle path planning algorithm based on deep reinforcement learning in large-scale and dynamic environments [J]. IEEE Access, 2021, 9: 24884-24900.
[21] GANGANATH N, CHENG C T, TSE C K. Rapidly replanning A* [C]//2016 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery. Chengdu: IEEE, 2016: 386-389.
[22] CHOWDHURY M I, SCHWARTZ D G. UUV onboard path re-planning using PRM-A* [C]//Global Oceans 2020. Singapore: IEEE, 2020: 1-8.
[23] LI X X, HU X G, WANG Z Q, et al. Path planning based on combination of improved A-STAR algorithm and DWA algorithm [C]//2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture. Manchester: IEEE, 2020: 99-103.
[24] LIU H X, ZHANG Y H. ASL-DWA: An improved Astar algorithm for indoor cleaning robots [J]. IEEE Access, 2022, 10: 99498-99515.
[25] FU Q, NING Y K, JI Y F, et al. Global dynamic path planning based on fusion improved A-star and dynamic window method [C]//2021 IEEE 5th Information Technology, Networking, Electronic and Automation Control Conference. Xi’an: IEEE, 2021: 243-249.
[26] GUAN W, WANG K. Autonomous collision avoidance of unmanned surface vehicles based on improved Astar and dynamic window approach algorithms [J]. IEEE Intelligent Transportation Systems Magazine, 2023, 15(3): 36-50.
[27] KULKARNI P P, KUTRE S R, MUCHANDI S S, et al. Unmanned ground vehicle for security and surveillance [C]//2020 IEEE International Conference for Innovation in Technology. Bangluru: IEEE, 2020: 1-5.
[28] QIU K, BAO Z, CHEN L. Task assignment and path planning for automatic guided vehicles in aircraft assembly workshop [J]. Journal of Shanghai Jiao Tong University, 2023, 57(1): 93-102 (in Chinese).
[29] TSARDOULIAS E G, ILIAKOPOULOU A, KARGAKOS A, et al. A review of global path planning methods for occupancy grid maps regardless of obstacle density [J]. Journal of Intelligent & Robotic Systems, 2016, 84(1): 829-858.
