双向搜索机制的改进A*算法研究

doi:10.3778/j.issn.1002-8331.2002-0016

计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (8): 231-237.DOI: 10.3778/j.issn.1002-8331.2002-0016

双向搜索机制的改进A*算法研究

孔继利，张鹏坤，刘晓平

北京邮电大学现代邮政学院，北京 100876

出版日期:2021-04-15 发布日期:2021-04-23

Research on Improved A* Algorithm of Bidirectional Search Mechanism

KONG Jili, ZHANG Pengkun, LIU Xiaoping

School of Modern Post, Beijing University of Posts and Telecommunications, Beijing 100876, China

Online:2021-04-15 Published:2021-04-23

摘要/Abstract

摘要：

针对大规模环境下传统A*算法路径寻优存在的内存占有率高、计算效率低下的问题，提出了一种改进A*算法。引入了双向搜索机制，以原始起点、终点和对向搜索所处的当前节点作为目标点进行搜索操作，使AGV的路径寻优具备更加合理的方向性；优化评价函数，改进了评价函数的传统计算方式，通过测试为评价函数选择了合适的权重系数，减少路径寻优过程中的冗余点，提升路径寻优的计算效率，节约内存占有率。为了验证改进A*算法的有效性，在Matlab平台中进行编程，在不同尺寸的含障碍栅格地图中进行了仿真。仿真结果表明：改进A*算法在路径寻优过程中所遍历的节点数量较少，搜索过程中的计算效率更高，并且可获得到达目标点的最短路径。

关键词: 双向搜索, 改进A*算法, 路径寻优

Abstract:

Aiming at the problems of high memory occupancy and low computing efficiency of A* algorithm in large-scale environment, an improved A* algorithm is proposed. Firstly, a bidirectional search mechanism is introduced. It searches with the original starting point, the end point and the oppositecurrent point as the target point, so that the AGV path optimization has directionality. Secondly, the evaluation function is optimized. It selects the appropriate weight coefficient for the evaluation function, so as to improve the calculation efficiency of path optimization. In order to verify the effectiveness of the improved A* algorithm, it is programmed in Matlab platform and simulated in different sizes of grid map with obstacles. The simulation results show that the number of nodes traversed by the improved A* algorithm is less, the calculation efficiency is higher and the shortest path can be obtained.

Key words: bidirectional search, improved A* algorithm, path optimization

孔继利，张鹏坤，刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8): 231-237.

KONG Jili, ZHANG Pengkun, LIU Xiaoping. Research on Improved A* Algorithm of Bidirectional Search Mechanism[J]. Computer Engineering and Applications, 2021, 57(8): 231-237.

[1]	张子然，黄卫华，陈阳，章政，李梓远. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.
[2]	刘建娟，薛礼啟，张会娟，刘忠璞. 融合改进A*与DWA算法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(15): 73-81.
[3]	王晓军，王博，杨春霞，晋民杰，陈海波. 紧致密集Auto Store系统AGV路径规划与避碰策略[J]. 计算机工程与应用, 2021, 57(15): 259-270.
[4]	胡蔚旻，靳文舟. 改进平滑A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(16): 204-210.
[5]	钟志峰，易明星，陈智军，谭普，曾张帆. 基于改进A*算法的导购路径规划方法[J]. 计算机工程与应用, 2019, 55(5): 129-134.
[6]	吴鹏，桑成军，陆忠华，余双，方临阳，张屹. 基于改进A*算法的移动机器人路径规划研究[J]. 计算机工程与应用, 2019, 55(21): 227-233.
[7]	张昕，严沛，郭阳，王慧慧. 基于k-shell的复杂网络最短路径近似算法[J]. 计算机工程与应用, 2019, 55(14): 54-60.
[8]	顾鸿儒，孙连坤. 基于层次颜色Petri网的交通紧急调度算法与建模[J]. 计算机工程与应用, 2016, 52(16): 261-270.
[9]	王慧，王铮. 基于新路由表的双向搜索chord路由算法[J]. 计算机工程与应用, 2014, 50(23): 95-99.
[10]	王佳乐，顾幼瑾. 基于属性位复用的约束性关联规则挖掘算法[J]. 计算机工程与应用, 2011, 47(7): 131-134.
[11]	刘雨露¹，方　刚¹，唐曙光². 位序互补的空间关联规则挖掘算法[J]. 计算机工程与应用, 2011, 47(4): 134-137.
[12]	何志东，俞鹤伟，陶铭. 双向搜索蚁群算法在QoS单播路由中的应用[J]. 计算机工程与应用, 2010, 46(31): 106-108.
[13]	赵志刚，李陶深，杨林峰. 求多目标优化问题的粒子群优化算法[J]. 计算机工程与应用, 2009, 45(29): 37-40.
[14]	方刚,刘雨露. 基于事务互补的双向挖掘算法[J]. 计算机工程与应用, 2008, 44(36): 168-170.
[15]	王敏¹,高太平^1,2,刘桂枝^1,3,刘宏英^1,4. 交叉立方体网络上的一种双向搜索路由算法[J]. 计算机工程与应用, 2007, 43(35): 123-125.

双向搜索机制的改进A*算法研究

Research on Improved A* Algorithm of Bidirectional Search Mechanism

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics