基于A-Star和DWA算法的野外环境路径规划

摘要/Abstract

摘要：多要素复杂野外环境的路径规划问题仍然是一个挑战。设计了一种将全局规划和局部规划相结合的算法，应用于野外环境路径规划。提出了野外环境地图的建模过程。设计了三种优化策略来克服接触障碍物边缘、冗余节点和扭曲路径等问题，以提高A-Star算法性能，并设计了一种新的加权成本函数来实现不同的规划模式。此外，与传统的动态窗口方法（DWA）相比，改进的DWA避免了局部最优，提高了时间效率。为了对野外环境进行必要的路径重规划，将改进的A-Star与改进的DWA相结合，实现了野外环境中存在未知障碍物和移动障碍物的多要素重规划。改进的融合算法有效地解决了上述问题，节省了时间，仿真结果验证了改进算法的有效性。

关键词:路径规划，路径重规划，野外环境，A-Star算法，DWA算法

Abstract: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.

Key words:path planning, path re-planning, wild environment, A-Star algorithm, dynamic window approach(DWA)

中图分类号:

TP242

董德金1,2，董诗音3，章露露1,2，蔡云泽1,2. 基于A-Star和DWA算法的野外环境路径规划[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 725-736.

DONG Dejin^1,2(董德金), DONG Shiyin³(董诗音), ZHANG Lulu^1,2(章露露), CAI Yunze^1,2∗(蔡云泽). Multi-AGVs Scheduling with Vehicle Conflict Consideration in Ship Outfitting Items Warehouse[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(4): 725-736.

参考文献

[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.