谷月 张德育 晋峰高
摘 要：随着全球科技技术的不断发展，人类对未知的不断探索和对科技的需求不断增加，移动机器人也在科技的浪潮中应运而生，并且一直处在人工智能科技的前沿。移动机器人的应用与人们的生活联系越来越紧密，其最重要的研究方向是对路径搜索算法的研究，比如某些寻路游戏机器人、资源探索机器人、自动寻路机器人、搜索营救机器人等。该文对机器人路径搜索算法的研究，在A*算法的基础上做了改进，整体提高了搜索的效率。
关键词：人工智能;移动机器人;路径搜索;A*算法
中图分类号：TP242 文献标识码：A 文章编号：2096-4706（2020）13-0030-03
Abstract：With the continuous development of global science and technology，humans continuous exploration of the unknown and the increasing demand for science and technology in the process，the development of intelligent robot also arises at the historic moment in the tide of science and technology，has been in the forefront of artificial intelligence technology. The application of mobile robot is more and more closely related to peoples life. The most important research direction of intelligent robots is the study of path search algorithms，such as some pathfinding game robots，resource exploration robots，automatic pathfinding robots，search and rescue robots，etc. The research on the robot path search algorithm is improved on the basis of the A* algorithm，which improves the search efficiency as a whole.
Keywords：artificial intelligence;mobile robot;path search;A* algorithm
0 引 言
近年来，人工智能技术不断发展，其在移动机器人的应用越来越广泛，移动机器人在实际生活中应用最多、最重要的是路径搜索问题。在未知环境中，通过移动机器人进行路径搜索的研究还不是太完备，搜索算法的效率还有待提升。移动机器人的路径搜索问题主要是从搜索时间、搜索效率、搜索能耗等方面进行研究的，机器人的路径搜索所解决的问题是在复杂环境中自主搜索出一条可行的较优路径。目前广泛使用的搜索算法是启发式搜索算法中的A*算法，在简单环境下，A*算法可以较高效地搜索出最优路径。但是在复杂环境下，移动机器人使用A*算法进行路径搜索却变得不那么容易，搜索的效率还有待提高，因为复杂环境下障碍物的分布多且形状复杂，机器人需要在避障的同时搜索路径，因此对路径搜索算法的效率会有影响，一些常用的路径搜索算法在复杂环境下的搜索效率也会受到很大的影响。
因此本文基于校内对移动机器人路径搜索项目的研究，以A*算法为研究重点，进行改进，对移动机器人路径搜索的整个过程进行研究。并提出改进的想法，阐述改进的过程。
1 复杂环境中环境模型的建立
环境模型的建立是路径搜索算法研究过程中非常重要的一步，环境模型的建立有视图法、拓扑法和栅格法。栅格法是由一个个大小相等的正方形小格组成，构成一个连通图，可用坐标表示各个栅格，障碍物在栅格中用黑色表示。路径搜索算法搜索路径的过程就是设置一个初始节点和一个目标节点，通过搜索算法生成从初始节点到目标节点的最优路径。
机器人的环境模型是对其现实环境的仿照，为了更准确地描述机器人所处的环境，采用正方形栅格表示法来建立环境模型。按照真实的地图环境和机器人的大小比例，建立大小合适的正方形栅格地图用于算法的研究，在这里我们将被控物体看成是点状物体，它的移动环境是二维平面，黑色格块对应栅格地图中的障碍物，白色格块是可以通行的自由格块;将每一个正方形栅格与坐标相对应，坐标可用P（x，y）表示，每个栅格都有对应的属性。
当栅格的属性为0时，栅格为自由栅格，可以通行;当栅格的属性为1时，栅格为障碍物栅格，不可以通行;当栅格的属性为2时，栅格表示路径搜索的初始位置;当栅格的属性为3时，栅格表示路径搜索的目标位置。
栅格大小的选取影响着整个移动机器人路径搜索算法的效率，栅格如果选取得过大，相应的计算量会变少，但得到的路径长度可能会变大;另一方面，栅格选取得过小，虽然搜索路径的效率会提高，但是搜索时间会变长，搜索过程缓慢。所以栅格大小的选取根据所处的环境来决定，栅格长度选取为l=（r+R）+λ;其中，r是障碍物的半径大小，R是机器人的半径大小，λ是设定的安全距离。由以上条件可知，移动机器人在复杂环境下路径搜索算法的研究可转化为通过在已得到的环境模型中的无障碍物的区域搜索，最终得到的一个连续路径。
2 A*搜索算法的改进
启发式算法是路径搜索算法中最常用的搜索算法，A*算法也属于其中，启发式搜索算法就是根据对栅格地图中每一个栅格的相邻栅格位置进行搜索比较，从相邻栅格中找到距离目标点最近的栅格，再从这个栅格进行搜索比较，直到搜索到目标节点为止。然而在启发式搜索中，对于栅格位置的评估是十分重要的，根据选取最佳搜索节点的策略不同，采用不同的估价函数有着不同的效果，其中A*搜索算法中的估价函数表示为：
传统A*算法能够有效地对目标进行全局路径搜索，但是在较为复杂的环境中，A*算法优化后得到的路径冗余点较多、运动路线折线多、转折次数多、转折角度大，这些缺陷严重影响路径搜索的效果，直接影响算法的执行效率。为此，本文提出对传统A*算法改进的想法，并对考察节点数、花费时间、路径开销和是否最优四个方面进行优化改进。在标准A*算法的基础上增加父节点，防止走到死路，减少冗余点。该A*算法改进成跳点搜索的方法进行优化，这种方法能够减少搜索的节点和转折次数。
本文对A*改进并进行路径搜索的流程图如图1所示。
2.1 A*搜索算法流程
传统A*搜索算法的搜索步骤如下：
（1）把起始节点看作是点A进行搜索，建立一个开启列表，将点A加入此列表。开启列表存储待搜索的节点。
（2）在节点A的可搜索方向进行搜索，搜索所有可到达目标节点的相邻节点，将这些节点存储到开启列表中。
（3）节点A已经搜索完毕，就从开启列表中将其删除，将节点A加入闭合列表。
（4）按照公式F=G+H计算A点所有周围点的H值，选取开启列表中H值最低的节点B，将此节点作为A之后搜寻到的节点，并加入闭合列表中。
（5）继续从B节点开始搜索所有相邻节点，除去闭合列表中的节点。
（6）如果存在B的相邻节点不在开启列表中，则将它们加入，如果节点B的相邻节点都已经在开启列表中，并且存在G值低于B点G值的点，那么放弃B节点作为A的下一个节点。然后按照F值最低原则选择开启列表里其他节点作为A点的下一个节点。
（7）重复这个过程，直到目标节点被添加进关闭列表。
2.2 A*回溯算法
传统的A*算法是通过将搜索路径过程中的信息存储起来，然后再从最后一个节点信息向第一个信息节点逆向提取，提取出的节点可形成一条路径，即为搜索到的路径。但是在多障碍物的环境下会出现死胡同现象，搜索过程中无法找到下一个最优节点，搜索过程一直等待，无法进行下去，形成死路，无法搜索到最优路径。算法的搜索效率变低，因此改进的A*回溯算法是在原来的基础上增加了父节点，避免走弯路，而且在较为复杂的环境中也能更好地进行路径搜索。从而达到提取最优路径的效果。
本文通过增加父指针对搜索步骤进行改进，如果当前搜索到的下一个节点比当前节点更优时，就删除当前节点，将当前节点加入闭合列表。然后父指针就指向该节点。搜索的过程不会改变。最终会通过闭合列表和父节点列表，根据父指针开始逆向搜索到开始节点，忽略冗余点，得到路径。
在搜索节点的数目上、搜索时间上，增加父节点的A*回溯算法比标准A*算法有明显的优势，A*回溯算法有效地避免了死路，有效节省了路径开销。
2.3 A*跳点搜索
在路径优化过程中，为了进一步减少搜索的节点和冗余点，在A*算法搜索过的路径节点中，选取跳点作为新的节点，将式（1）中的估价函数作为初始值进行比较，根据代价函数的大小比较和不穿过障碍物为评价标准。如果选取的跳点的代价函数小于初始值并且没有穿过障碍物，则选取这个跳点为新的路径节点，将这些新的路径节点连接起来就组成了新的路径，仅包含开始节点、中间转折点和目标节点。
3 实验结果与分析
经过改进后的A*算法与标准A*算法的路径搜索仿真如图所示，图2为传统的A*算法路径仿真图，图3为改进后的A*算法路径仿真图。
由仿真图的对比中可以看出改进算法后搜索的路径冗余点减少、运动路线折线减少、转折次数变少、转折角度更平滑。
4 结 论
本文在A*算法的基础上对移动机器人的路径搜索进行研究，引入了父节点，对一些搜寻到死路节点时的情况进行了优化;而且通过A*回溯算法可以删除多余的冗余点，缩短路径搜索的时间。再进一步通过跳点搜索的原理，将A*回溯算法搜索的路径进行优化，进一步减少扩展节点，将整个搜索的路径长度缩短、减少转折次数、缩小转折角度、平滑搜索到的路径，在一定情况下可以提高路径搜索的效率，优化路径搜索的结果。
参考文献：
[1] 柯星.动态环境下多移动机器人路径规划研究 [D].成都：电子科技大学，2013.
[2] 邬再新，李艳宏，刘涛.多移动机器人路径规划技术的研究现状与展望 [J].机械，2008（1）：1-3+16.
[3] 王洪斌，郝策，张平，等.基于A*算法和人工势场法的移动机器人路径规划 [J].中国机械工程，2019，30（20）：2489-2496.
[4] 王殿君.基于改进A*算法的室内移动机器人路径规划 [J].清华大学学报（自然科学版），2012，52（8）：1085-1089.
[5] 纪海宾，师彩云.基于Origin的移动机器人测距传感器参数标定 [J].现代信息科技，2020，4（9）：40-42+45.
作者简介：谷月（1996—），女，汉族，河北任丘人，硕士，研究方向：系统监控与网络管理技术。
