基于双向搜索改进A*算法的自动导引车路径规划

• 作者: 陈德童 刘贤达 刘生伟
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 自动导引车 A*算法 路径规划 动态窗口 双向搜索
• 年，卷（期）: 2021,（z2）
• 所属期刊栏目: 应用前沿、交叉与综合|Frontier & interdisciplinary applications
• 页码范围: 309-313
• 页数: 5页
• 分类号: TP242.2
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2021040557

摘要

在面积比较大的或划分精细的栅格地图中进行自动导引车(AGV)行驶路径规划时,经典的A*算法搜索得到的路径往往冗余节点和转折点较多,搜索路径时间较长.为了提高A*算法的实时性,提出了一种基于双向搜索路径的A*算法.首先,对于A*算法的启发函数引入父节点和Chebyshev Distance,改进启发函数;其次,引入双向路径搜索的动态窗口,同时从路径的起点和终点搜索路径,得到一条初始路径,并论述了动态窗口的大小对于双向搜索路径的影响;最后,依据关键点搜索原理,剔除初始路径中存在的冗余节点,得到最终的搜索路径.实验证明,相较于单向改进A*算法和改进人工势场算法,双向搜索改进A*算法搜索路径耗费时间分别降低了22.9％和78.4％,路径包含节点数分别降低了82.2％和99.5％,证明了算法的有效性.