[1]张湘,余捷,于廷海,等.基于双向搜索改进A*算法路径规划[J].福建理工大学学报,2024,22(06):567-572.[doi:10.3969/j.issn.2097-3853.2024.06.009]
　ZHANG Xiang,YU Jie,YU Tinghai,et al.Path planning of improved A* algorithm based on bidirectional search[J].Journal of Fujian University of Technology;,2024,22(06):567-572.[doi:10.3969/j.issn.2097-3853.2024.06.009]
点击复制

基于双向搜索改进A*算法路径规划
分享到：

《福建理工大学学报》[ISSN:2097-3853/CN:35-1351/Z]

卷:
第22卷
期数:
2024年06期
页码:
567-572
栏目:
出版日期:
2024-12-25

文章信息/Info

Title:
Path planning of improved A* algorithm based on bidirectional search
作者:
张湘; 余捷; 于廷海; 王奕辉; 叶盛
（福建理工大学）福建省汽车电子与电驱动技术重点实验室
Author(s):
ZHANG Xiang;  YU Jie;  YU Tinghai;  WANG Yihui;  YE Sheng
Fujian Provincial Key Laboratory of Automotive Electronics and Electric Drive Technology
关键词:
双向A*算法; 启发式函数; 路径规划; 移动机器人
Keywords:
bidirectional A* algorithm; heuristic functions; path planning; mobile robots
分类号:
TP242.6
DOI:
10.3969/j.issn.2097-3853.2024.06.009
文献标志码:
A
摘要:
为改善传统路径规划A*算法搜索速度慢的问题，提出了一种基于双向搜索改进A*算法。新型算法选用欧几里得距离作为启发式函数并引入双向搜索策略，采用了24邻域搜索法和自适应地图的动态权重系数实现对启发式函数的自动调节，提高算法的路径规划效率及其对不同地图的适应性。在不同环境下的进行了两组仿真实验，结果表明，与现有4种算法比较，该算法在搜索节点数量和规划时间方面具有较大的性能提升。
Abstract:
In order to address the issue of slow search speed in the traditional A* algorithm for path planning, a novel approach based on bidirectional search, known as the improved A* algorithm, is proposed. This new algorithm utilizes the Euclidean distance as the heuristic function and incorporates bidirectional search strategy. Additionally, it employs a 24-neighborhood search method and dynamically adjusts the weight coefficients of the heuristic function using an adaptive map, thereby enhancing the efficiency of path planning and adapting to different maps. Two sets of simulation experiments were conducted in different environments. Results demonstrate significant performance improvements of the algorithm in terms of the number of search nodes and planning time, as compared with the four existing algorithms.

参考文献/References:

［1］ YANG C L. A novel algorithm for path planning of the mobile robot in obstacle environment［J］. International Journal of Circuits，Systems and Signal Processing，2021，15：225-235.［2］ 王宇斌，沈振军，王昱宸，等. 基于A*算法的四面体机器人路径规划研究［J］. 机械传动，2024，48（2）：42-47.［3］ GUAN W，WANG K. Autonomous collision avoidance of unmanned surface vehicles based on improved A-star and dynamic window approach algorithms［J］. IEEE Intelligent Transportation Systems Magazine，2023，15（3）：36-50.［4］ WANG Z，XIANG X B. Improved astar algorithm for path planning of marine robot［C］∥37th Chinese Control Conference （CCC）. Wuhan: IEEE，2018：5410-5414.［5］ ZHENG H Z，DAI M，ZHANG Z S，et al. The navigation based on hybrid A star and TEB algorithm implemented in obstacles avoidance［C］∥29th International Conference on Mechatronics and Machine Vision in Practice （M2VIP）. Queenstown，New Zealand: IEEE，2023：1-6.［6］ WANG HW，QI X Y，LOU S J，et al. An efficient and robust improved A* algorithm for path planning［J］. Symmetry，2021，13（11）：2213.［7］ 张澳. 基于2D激光雷达AGV自然导航技术研究［D］. 福州：福建工程学院，2023.［8］ 王中玉，曾国辉，黄勃. 基于改进双向A*的移动机器人路径规划算法［J］. 传感器与微系统，2020，39（11）：141-143，147.［9］ 张学锋,胡伟鹏,石军花,等.基于改进双向A*算法的移动机器人路径规划研究［J/OL］.重庆工商大学学报(自然科学版),1-13［2024-09-14］.http:∥kns.cnki.net/kcms/detail/50.1155.N.20240305.1733.005.html.［10］ LI M H，QIAO L J，JIANG J F. A multigoal path-planning approach for explosive ordnance disposal robots based on bidirectional dynamic weighted-A* and learn memory-swap sequence PSO algorithm［J］. Symmetry，2023，15（5）：1052.［11］ WANG P K，MUTAHIRA H，KIM J，et al. ABA*-adaptive bidirectional A* algorithm for aerial robot path planning［J］. IEEE Access，2023，11：103521-103529.［12］ ZHONG T J，ZHANG H，DONG F Y，et al. FGP-astar algorithm based on path planning for mobile robots［C］∥2nd International Conference on Computing，Communication，Perception and Quantum Technology （CCPQT）. Xiamen，China: IEEE，2023：207-215.［13］ LIANG C L，ZHANG X K，WATANABE Y，et al. Autonomous collision avoidance of unmanned surface vehicles based on improved A star and minimum course alteration algorithms［J］. Applied Ocean Research，2021，113：102755.［14］ 杜传胜，高焕兵，侯宇翔，等. 基于改进双向A*算法的消防机器人路径规划［J］. 计算机与现代化，2023（4）：15-19，25.［15］ 姜媛媛，丰雪艳. 基于改进A*算法的煤矿救援机器人路径规划［J］. 工矿自动化，2023，49（8）：53-59.［16］ LI C G，HUANG X，DING J，et al. Global path planning based on a bidirectional alternating search A* algorithm for mobile robots［J］. Computers & Industrial Engineering，2022，168：108123. ［17］ 贾明超，冯斌，吴鹏，等. 一种融合改进A*算法与改进动态窗口法的文旅服务机器人路径规划［J］. 图学学报，2024，45（3）：505-515.［18］ 魏博闻，严华. 一种面向非结构化环境的改进跳点搜索路径规划算法［J］. 科学技术与工程，2021，21（6）：2363-2370.［19］ 蒋承杰，朱华，谢瑶，等. 基于改进A*算法的移动机器人的路径规划［J］. 制造技术与机床，2024（6）：33-36，73.

更新日期/Last Update: 2024-12-25