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

摘要

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