改进A*算法的机器人全局最优路径规划

王中玉 曾国辉 黄勃 方志军

摘 要：针对传统A*算法规划的路径存在很多冗余点和拐点的问题，提出了一种基于A*算法改进的高效路径规划算法。首先，改进评价函数的具体计算方式，减小算法搜索每个区间的计算量，从而降低寻路时间，并改变生成路径;其次，在改进评价函数具体计算方式的基础上，改进评价函数的权重比例，减少生成路径中的冗余点和拐点;最后，改进路径生成策略，删除生成路径中的无用点，从而提高路径的平滑性;此外，考虑到机器人的实际宽度，改进后算法引入障碍物扩展策略保证规划路径的可行性。将改进A*算法与三种算法进行仿真对比，实验结果表明，改进后的A*算法规划的路径更加合理，寻路时间更短，平滑性更高。

关键词：A*算法;路径规划;评价函数;生成策略;障碍物扩展

中图分类号：TP242.6

文献标志码：A

Global optimal path planning for robots with improved A* algorithm

WANG Zhongyu， ZENG Guohui*， HUANG Bo， FANG Zhijun

School of Electronic and Electrical Engineering， Shanghai University of Engineering Science， Shanghai 201620， China

Abstract：

There are many redundant points and inflection points in the path planned by the traditional A* algorithm. Therefore， an efficient path planning algorithm based on A* algorithm was proposed. Firstly， the specific calculation method of the evaluation function was improved to reduce the calculation amount of the algorithm searching each interval， thereby reducing the path finding time and changing the generation path. Secondly， on the basis of improving the specific calculation method of the evaluation function， the weight ratio of the evaluation function was improved， and the redundant points and inflection points in the generation path were reduced. Finally， the path generation strategy was improved to delete the useless points in the generation path， improving the smoothness of the path. In addition， considering the actual width of the robot， the improved algorithm introduced an obstacle expansion strategy to ensure the feasibility of the planned path. The comparison of the improved A* algorithm with three algorithms shows that the path of the improved A* algorithm is more reasonable， the path finding time is shorter， and the smoothness is higher.

Key words：

A* algorithm; path planning; evaluation function; generation strategy; obstacle expansion

0 引言

近年來，移动机器人技术一直在快速发展。预计移动机器人不仅是一种即将到来的新式武器，也是老龄化社会一种新的劳动力。路径规划在移动机器人任务管理系统中是一项关键技术，在整个移动机器人研究领域中也是一个热门而相当复杂的问题[1-2]。规划的路径应该是最佳无冲突，并且有助于在复杂环境中实现特定任务[3-4]。现有的路径规划主要分为两大类：传统规划方法和智能方法[5-6]。传统的路径规划算法主要指基于全局环境模型的图搜索算法和潜在的现场方法。应用较多的智能规划方法包括神经网络[7]、人工势场法[8]、粒子群算法[9]、遗传算法[10]、蚁群算法[11]和模拟退火算法[12]。A*算法是一种属于智能规划方法的启发式算法，它具有简单的估值功能，广泛地应用于各种类型搜索问题，如计算机游戏无碰撞检测、无人机路径规划和移动机器人路径规划[13-14]。

在路径规划领域，A*算法具有计算量小、寻路时间短、规划路径相对最优等突出特点。因此，大量学者对A*算法进行深入研究并加以改进，以适用于不同领域机器人的路径规划。如航海领域，主要在A*算法的评价函数中增加角度转向成本，以满足船舶调头、转弯的实际需要[15]。航空领域，主要在A*算法的评价函数中增加坡度成本和燃耗成本，以满足无人机等飞行器的空间约束[16]。而在陆地的移动机器人路径规划中，A*算法的改进主要分为两方面：一方面是减少寻路时间，如同步双向A*算法在路径的起点和目标点同时运行A*算法，缺陷是受地图环境影响大，寻路时间和生成路径可能更差[17];另一方面是优化生成路径，主要通过增加搜索矩阵的搜索方向来实现，如双向时效A*算法，缺陷是增加了寻路时间[18]。

本文提出了一种在已知环境中移动机器人全局路径规划的新方法。分析A*算法的问题并进行三方面的改进。首先通过改变A*算法评价函数的具体计算方法，减少寻路时间。再通过改变启发函数的权重和改进路径生成策略减少冗余点与拐点，规划全局最优路径。此外，考虑到移动机器人的实际宽度，采用障碍物扩展策略，确保生成的路径安全可行。通过几个模拟实验验证了A*算法的改进真实有效。

1 A*算法规划机器人路径

A*算法规划移动机器人路径的过程可概括为两部分：一是环境建模;二是算法引入，生成路径。

1.1 环境建模

规划移动机器人路径的前提是对实际环境进行模型搭建，A*算法采用栅格法构建移动机器人路径规划的环境。栅格法是移动机器人路径规划最常用的方法，最早是由Morave和Elfesc H P和Elfes A提出的，其基本思想是将有限的规划空间划分为多个大小相同并赋有二进制数的栅格单元[19]。基于栅格图的移动机器人路径规划通常将机器人视为移动粒子，并且记录其在栅格上的状态。为简化分析，本文作出以下假设：

假设1 在路径规划的过程中，障碍物的位置和大小是已知且不改变的。忽略障碍物的高度信息。

假设2 规划的移动机器人路径，每一步都占据整个栅格。忽略移动机器人的高度信息。

假设3 移动机器人二维工作空间的长是L，宽是W。将该工作空间划分为大小相同的R*S个栅格，每个栅格的信息用Nij表示，如式（1）整个工作空间的信息可以用Ω表示：

Ω=∑Nij; i∈[1，R]，  j∈[1，S]（1）

如式（2）每个栅格的状态信息具体地表示为：

Nij=0， 无障碍

1，有障碍 （2）

其中：当Nij取值为0时，表示当前栅格是无障碍物的自由空间;当Nij取值为1时，表示当前栅格是有障碍物的。

从理论上讲，移动机器人在行走时会有许多方向和细微动作。但考虑到模型的复杂性，A*搜索算法定义，移动机器人在栅格中每一步行走仅有8个可供参考的方向，即8搜索方向A*算法，它们分别是前、后、左、右、左前、左后、右前、右后。移动机器人8个运动方向如图1所示。

1.2 A*算法引入

A*算法是由Hart和Nilsson在1968年提出的一种的启发式图搜索算法，最早应用于解决各种数学问题[20]。在人工智能领域中，主要运用A*算法解决各种路径规划问题。其基本思想是，确定一个评价函数，从起点开始根据评价函数不断向目标点的方向进行搜索，同时记录每一次搜索确定的点，直至搜索到目标点为止。最后从目标点返回到起始位置，获得最小成本路径。A*算法的评价函数如式（3）所示。

f（n）=g（n）+h（n）（3）

在式（3）中， f（n）是当前点的评价函数，其函数主要由两部分组成：第一部分是过去成本函数g（n），用于评价起点到当前点的代价;第二部分是当前成本函数h（n），用于评价当前点到目标节点的代价。在二维空间中，代价的值通常指两个节点之间的距离，因此函数g（n）和函数h（n）的值通常采用欧氏距离计算得來。

g（n）=（xn-xs）2+（yn-ys）2（4）

h（n）=（xt-xn）2+（yt-yn）2（5）

在式（4）和式（5）中，（xs，ys）是起点Ps坐标，（xn，yn）是当前点Pn坐标，（xt，yt）是目标点Pt坐标。进一步，可以得知A*算法的评价函数是Dijkstra算法和最佳优先搜索（Best-First-Search， BFS）算法的结合。在评价函数f（n）中，若g（n）的权重为1，h（n）的权重为0，则A*算法可视为Dijkstra算法，倾向于广度优先搜索即偏向于接近起点的顶点，是两点之间经典的路径最短算法。若g（n）的权重为0，h（n）的权重为1，则A*算法可视为BFS算法，算法搜索启发性更强即偏向于接近目标点的顶点，是路径规划中典型的启发式搜索算法，但规划的路径一般不是最优，因此，合理分配A*算法评价函数的权重比例，则算法规划的路径将更短、更平滑。

2 改进A*算法

2.1 A*算法的实施

A*算法在规划移动机器人路径时，有两个起辅助作用的链表。一个是存放已经生成节点的Closed链表，另一个是存放下一步要探索节点的Open链表。如移动机器人在当前位置探索下一步要行走的方向时，当前点的位置存放在Closed链表中，要探索的8个临近栅格的位置，存放在Open链表中。在执行A*算法规划路径时，以评价函数f（n）为标准，从Open链表中选出代价值最小的位置存入Closed链表中。循环往复，直至在Open链表中出现目标点为止，最后在Closed链表中从目标点返回到起始位置，获得最小成本路径。程序运行结束后，可以获得相对最优的路径。

A*算法的流程如图2所示。

具体步实施骤如下：

步骤1 创建两个名为Open和Closed的两个链表，将环境地图中的障碍物位置信息存放在Closed链表中，将起始点的位置存放在Open链表中。

步骤2 检查Open链表是否为空。如果为空，跳到步骤8，否则进行步骤3。

步骤3 检查Open链表是否包含目标点，如果包含目标点，跳到步骤6，否则进行步骤4。

步骤4 从Open链表中选取评价函数最小值的f（n）点放入Closed链表中。

步骤5 将下一步可搜索的点放入Open链表中，具体表现为：在8个邻近栅格点中，如果该节点不在两个链表中，则将其添加到Open链表中，并将其父节点指向当前点。 如果该节点已经在Open链表中，则将评价函数的成本f（n）与Open表中的原始值进行比较。如果它小于等于原始值，则记录新值并将其父点的指针指向当前点;如果节点在Closed链表中，则跳过它并继续扩展其他节点。跳到步骤2。

步骤6 将目标点放入Closed链表中。

步骤7 在Closed链表中，从目标点返回到起始位置，获得最小的成本路径。

步骤8 程序运行结束。

2.2 A*算法的改进

A*算法结合了Dijkstra算法和BFS算法。Dijkstra算法属于广度优先算法，在进行移动机器人路径规划时，需要进行大量节点遍历。为减小Dijkstra算法的搜索范围和计算的复杂度，因此引入了BFS算法。然而，在A*算法的启发式搜索中，仍添加了一些冗余点，规划的路径也就存在了很多拐点和冗余点（如图6传统A*算法规划路径中椭圆形区域所示）。对于实际的机器人路径规划，机器人易于在拐点处偏差，冗余点会增加路径规划的时间，因此，A*算法规划的路径不是最优。本文对A*算法进行三方面改进，以减少寻路时间优化生成路径。

2.2.1 改进评价函数计算方式

第一方面是改进评价函数f（n）中过去成本函数g（n）的具体计算方式，减少寻路时间。改进后的过去成本函数g′（n）如式（6）所示，改进后A*算法的评价函数如式（7）所示：

g′（n）=g′（n-1）+c（n）（6）

f（n）=g′（n）+h（n）（7）

在式（6）中c（n）是当前点Pn和父节点Pn-1的成本函数，表达式如式（8）所示，g′（n-1）是父节点Pn-1的过去成本函数，表达式如式（9）所示。在计算当前点Pn的评价函数值时，由于父节点Pn-1的过去成本函数g′（n-1）是已知的，所以，只需要计算c（n）即可：

c（n）=（xn-xn-1）2+（yn-yn-1）2（8）

g′（n-1）=g′（n-2）+c（n-1）=

∑n-1i=1（xi-xi-1）2+（yi-yi-1）2（9）

由式（4）和式（8）可推得式（10），因为c（n）是计算当前点Pn和其相邻父节点Pn-1欧氏距离，g（n）是计算当前点Pn和起点Ps的欧氏距离，当前点Pn和起点Ps距离的增大时g（n）的计算量随之增大，所以对于任意当前点Pn的c（n）计算量一定小于等于g（n）的计算量。在整个规划路径中需要探索大量节点，改进后算法可节省大量计算，减少寻路时间。

c（n）≤g（n）（10）

由式（6）和式（9）推得式（11），由式（4）和式（11）推得式（12）。由式（12）得，在相同起点Ps和当前点Pn的情况下，g′（n）的值小于等于g（n）的值，这等价于降低了过去成本函数g′（n）在评价函数f（n）中的权重比例，将导致生成路径的改变，为了减少这种影响，生成合理路径，本文进行第二方面改进。

g′（n）=∑ni=1（xi-xi-1）2+（yi-yi-1）2（11）

g′（n）≤g（n）（12）

各点和成本函数的关系如图3所示。

2.2.2 改进评价函数权重比例

第二方面是改进评价函数的权重比例，以此减少生成路径的冗余点和拐点，减少无用区间搜索。由1.2节介绍可知，在A*算法启发式搜索的过程中。当h（n）的权重比例偏大时，评价函数f（n）的启发式信息强烈，尽管减少了路径搜索的工作量，但规划的路径一般不是最佳。当h（n）的权重比例偏小时，评價函数f（n）的启发式信息比较弱，虽可优化生成路径，但这直接导致路径搜索工作量的增加。在本文中引入了权重比例的概念，以此达到平衡启发式信息的强度和优化路径缩短寻路时间的目的。

11+X+X1+X=1（13）

本文构建的两项权重系数关系如式（13）所示，在式（13）中X为自变量，取值范围是[0，+∞），两项权重系数之和为1，当自变量X从0变化到+∞时，第一项权重系数从1减少至0，第二项权重系数从0增加到1，两者成反比例关系，将该权重系数引入A*算法的评价函数中，可自由调节g′（n）和h（n）的比例，满足需求。

f′（n）=11+X g′（n）+X1+X h（n）（14）

将式（13）引入式（7）后得可调节权重比例的评价函f′（n）如式（14）所示。在式（14）中，随着X取值不同，过去成本函数g′（n）和当前成本函数h（n）权重范围都是0～1。当X取值为1时，可得式（15）。与式（7）相比，搜索相同区间其评价函数值等比例缩小。

f′（n）=0.5g′（n）+0.5h（n）（15）

在地图环境相同的情况下，A算法运用式（15）评价函数和式（7）评价函数搜索区间和规划路径是一致的。因此X的取值探索应从1开始扩展，经过加权求平均最终取得合适值，使评价函数的权重比例更加合理，从而缩短寻路时间、优化生成路径。

2.2.3 改进路径生成策略

第三方面是改进路径生成策略，进一步优化生成路径。当A*算法搜索到目标点Pt（xt，yt）初步确定全局路径生成点时，改进路径生成策略，将目标点Pt设为当前点Pn（xn，yn），

并判断当前点Pn和其祖父节点Pn-2（xn-2，yn-2）之间是否存在障碍物，即作一条连接当前点Pn和其祖父节点Pn-2的直线M，由于已知当前节点Pn和其祖父节点Pn-2的坐标，直线M的解析式可由式（16）和式（17）求得：

k=（yn-2-yn）（xn-2-xn）（16）

y=k（x-xn）+yn（17）

根据直线M方程，求出横坐标在（xn-2，xn）之间线上的所有点Pa，并逐个判断这些点是否处于障碍物区，如果有点处于障碍物区间，则不作改变。如果所有点Pa都不在障碍物区，则删除当前点Pn的父节点Pn-1指向其祖父节点Pn-2。当前点Pn优化后，依次对下一节点进行优化，直到起点为止完成第1次路径优化。改进后A*算法可设置多次优化，能够删除大量冗余点，优化生成路径。该策略如图4所示。

改进路径生成策略的伪代码如下：

有序号的程序——————————Shift+Alt+Y

程序前

PathSmoothing（ps，pt）

1）

Pn ←（xt，yt）

2）

while（Pn ！= Ps）

3）

M ← Getline（Pn，Pn-2）

4）

Pa ← GetPoint（M，xn-2，xn）

5）

if PointFree（Pa）

6）

Pn-1←（xn-2，yn-2）

7）

Pn ← Pn-1

8）

end while

程序后

在上述伪代码中，GetLine（）表示求得穿过当前两点的直线方程，GetPoint（）表示求得直线M上横坐标范围为是（xn-2，xn）的所有点，PointFree（）表示当前点不处于障碍物区域。

2.2.4 障碍物扩展策略

在移动机器人路径规划的模拟实验中通常不考虑机器人的实际宽度，这导致算法规划的路径过于接近障碍物。在实际运行时，可能导致机器人损坏并无法到达目标点Pt。针对这一问题，本文提出了障碍物扩展策略。如1.1节所述地图划分为R*S个栅格，栅格对应坐标范围是（x1，y1）到（xR，yS）且每个栅格的信息Nij是已知的。障碍物扩展策略就是将所有栅格逐一进行检测，如果有栅格处于障碍物区间则将邻近8个栅格設置为禁止搜索，即可视为障碍物扩展区域。采用障碍物扩展策略后，规划的路径与障碍物栅格具有安全距离，并且可以应用于具有一定宽度的真实机器人的工程实践中。

该策略如图5所示。在图5中5为障碍物区域，1、2、3、4、6、7、8、9为障碍物扩展区域。

障碍物扩展策略的伪代码如下：

有序号的程序——————————Shift+Alt+Y

程序前

ObsExpansion（（x1，y1），（xR，yS））

1）

for i=1 to R

2）

for  j=1 to S

3）

Pn ←（xi，xj）

4）

if Nij=1

5）

ExtArea（Pn）;

6）

end if

7）

end for

8）

end for

程序后

在上述伪代码中，ExtArea（）表示探索当前点Pn的8个邻近栅格，处于障碍区间的栅格不作改变，没有处于障碍区间的栅格设置为障碍物扩展区。

3 仿真验证

为验证改进A*算法的有效性和灵活性，本文在不同环境下进行了仿真，仿真软件平台为Matlab R2017a，硬件平台为Intel Core i5-3230M 2.6GHz CPU，RAM 4GB。

首先，本文构建了一个包含许多障碍物的栅格图，尺寸为100×100像素（density independent pixels， dip），即X轴坐标范围是[0，100]，Y轴的范围是[0，100]。在此栅格图中上方黑色圆点为起点，坐标为（50，85），下方黑色圆点为目标点，坐标为（50，20），黑色区间代表障碍物，白色为无障碍区间。并在此栅格图上，运用传统A*算法进行路径规划。构建的栅格图和传统A*算法路径规划仿真结果如图6所示。由图6可得传统A*算法规划的路径确实存在很多冗余点和拐点。

其次，改进A*算法评价函数计算方式和在此基础上进一步改进A*算法评价函数的权重比例，其仿真结果如图7所示。由图7可得，改进A*算法评价函数的计算方式，可以改善最终生成的路径。再改进评价函数的权重比例（加权求平均得X取值1.1），可进一步优化生成路径，虽然最终生成的路径冗余点和拐点减少，路径转弯角度减小，整体更加平滑，但最终生成的路径中依然存在一些冗余点和拐点。

完成上述两步改进后再进一步改进A*算法路径生成策略，以及完成上述三步改进后最后添加障碍物扩展策略，其仿真结果如图8所示，而添加障碍物扩展策略后的仿真结果就是本文改进后A*算法在该地图上的最终仿真结果。由图8可得，通过改进路径生成策略（本文设置经过2次节点优化策略）最终生成的路径更进一步减少了路径中存在的冗余点和拐点。但此时生成的路径仍然存在过于靠近障碍物区域的问题，如果将其应用于实际的机器人路径规划中，则机器人将与障碍物碰撞。因此，将障碍物扩展策略添加到程序中解决该问题，最终生成的路径与附近的障碍物保持一定距离，解决了实际机器人与障碍物碰撞的问题。

传统A*算法及其改进方法的寻路时间数据如表1所示。结合图6～8可得，改进A*算法评价函数的具体计算方式和权重比例，可减少寻路时间、提高算法的效率并改善生成路径，但最终生成路径中仍存在很多冗余点和拐点。再改进A*算法的路径生成策略引入障碍物扩展策略，可进一步优化生成路径，但会增加寻路时间。综合本文改进方法的优缺点，由最终生成路径和寻路时间可得，本文改进后A*算法优化了生成路径，减少了寻路时间。

另一个栅格地图是模仿室内环境构建的，大小为100×100dip。室内环境包括走廊和房间。具有不同尺寸的矩形被设置为房间中的障碍物，起点坐标为（25，85），目标点坐标为（70，15）。如图9到图10所示，用传统A*算法、本文改进后A*算法、文献[17]中的同步双向A*算法 和文献[18]中的双向时效A*算法分别对该栅格地图进行路径规划，进而对比分析。不同算法的寻路时间数据如表2所示。

结合图9、10和表2可得，本文改进后A*算法生成路径的平滑性明显优于其他三大算法，寻路效率也具有较大的优势。此外，改进后A*算法生成的路径可以使机器人和障碍物保持安全距离，可以满足工程实践的需要。

4 结语

传统A*算法在障碍物空间中规划的路径一般不是最优，它包含很多冗余点和拐点。本文先改进传统A*算法评价函数的具体计算方式，减少搜索区间的计算量，从而提高算法的搜索效率;其次改变评价函数中权重比例，以此减少生成路径中的拐点和冗余点;最后改进传统A*算法的路径生成策略，进一步平滑生成路径。此外，引入障碍物扩展策略使机器人和障碍物保持安全距离，以满足实际工程需要。在仿真实验中，与其他五种算法相比，移动机器人可以在障礙物空间中找到安全且更平滑的路径，缩短了寻路时间，从而证明改进后A*算法对全局路径规划是非常合适和有效的。但改进后的算法仍存在一些不足之处，如该算法只能应用在已知的静态环境中，下一步的研究将集中在动态环境中，运用A*算法快速规划移动机器人全局最优且安全的路径。

参考文献 （References）

[1]陆新华，张桂林.室内服务机器人导航方法研究[J].机器人，2003，25（1）：80-87.（LU X H， ZHANG G L. Summarization on indoor service robot navigation [J]. Robot， 2003， 25（1）： 80-87.）

[2]CHEN D， LU Q， YIN K， et al. A method for solving local minimum problem of local path planning based on particle swarm optimization [C]// Proceedings of the 2017 Chinese Automation Congress. Piscataway， NJ： IEEE， 2017： 4944-4949.

[3]JEDDISARAVI K， ALITAPPEH R J， PIMENTA L C A， et al. Multi-objective approach for robot motion planning in search tasks [J]. Applied Intelligence， 2016， 45（2）： 1-17.

[4]张超超，房建东.基于定向加权A*算法的自主移动机器人路径规划[J].计算机应用，2017，37（S2）：77-81.（ZHANG C C， FANG J D. Path planning of autonomous mobile robot based on directional weighted A* algorithmm [J]. Journal of Computer Applications， 2017， 37（S2）： 77-81.）

[5]HAO Z-B， HONG B-R， HUANG Q-C. Study of coverage path planning based on grid-map [J]. Application Research of Computers， 2007， 24（10）： 56-58.

[6]PAN H， GUO C， WANG Z. Research for path planning based on improved astart algorithm [C]// Proceedings of the 2017 4th International Conference on Information， Cybernetics and Computational Social Systems. Piscataway， NJ： IEEE， 2017： 225-230.

[7]GUO Y， WANG W， WU S. Research on robot path planning based on fuzzy neural network and particle swarm optimization [C]// Proceedings of the 2017 29th Chinese Control and Decision Conference. Piscataway， NJ： IEEE， 2017： 2146-2150.

[8]MONTIEL O， SEPULVEDA R， OROZCO-ROSAS U. Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field [J]. Journal of Intelligent and Robotic Systems， 2015， 79（2）： 237-257.

[9]韩明，刘教民，吴朔媚，等.粒子群优化的移动机器人路径规划算法[J].计算机应用，2017，37（8）：2258-2263.（HAN M， LIU J M， WU S M， et al. Path planning algorithm of mobile robot based on particle swarm optimization [J]. Journal of Computer Applications， 2017， 37（8）： 2258-2263.）

[10]NI J， WANG K， HUANG H. Robot path planning based on an improved genetic algorithm with variable length chromosome [C]// Proceedings of the 2016 12th International Conference on Natural Computation， Fuzzy Systems and Knowledge Discovery. Piscataway， NJ： IEEE， 2016： 145-149.

[11]吳天羿，许继恒，刘建永.基于改进蚁群算法的越野路径规划[J].计算机应用，2013，33（4）：1157-1160.（WU T Y， XU J H， LIU J Y. Cross-country path planning based on improved ant colony algorithm [J]. Journal of Computer Applications， 2013， 33（4）： 1157-1160.）

[12]LIU K， ZHANG M. Path planning based on simulated annealing ant colony algorithm [C]// Proceedings of the 2016 9th International Symposium on Computational Intelligence and Design. Piscataway， NJ： IEEE， 2016： 461-466.

[13]LI Y， ZHANG H， ZHU H. IBAS： index based a-star [J]. IEEE Access， 2018， 6： 11707-11715.

[14]JEDDISARAVI K， ALITAPPEH R J， GUIMARAES F G. Multi-objective mobile robot path planning based on A* search [C]// Proceedings of the 2016 6th International Conference on Computer and Knowledge Engineering. Piscataway， NJ： IEEE， 2016： 7-12.

[15]WANG Z， XIANG X. Improved astar algorithm for path planning of marine robot[C]// Proceedings of the 2018 37th Chinese Control Conference. Piscataway， NJ： IEEE， 2018： 296-300.

[16]WANG Q， ZHANG A， QI L. Three-dimensional pathplanning for UAV based on pmproved PSO algorithm [C]// Proceedings of the 2014 26th Chinese Control and Decision Conference. Piscataway， NJ： IEEE， 2014： 3982-3986.

[17]林娜，李天啸.基于双向A*算法的城市无人机航路规划[J].沈阳航空航天大学学报，2016，33（4）：55-60.（LIN N， LI T X. Urban UAV route planning based on bidirectional A* algorithm [J]. Journal of Shenyang Aerospace University， 2016， 33（4）： 55-60.）

[18]高民东，张雅妮，朱凌云.应用于机器人路径规划的双向时效A*算法[J].计算机应用研究，2019，36（3）：792-795.（GAO M D， ZHANG Y N， ZHU L Y. Bidirectional time-efficient A* algorithm for robot path planning [J]. Application Research of Computers， 2019， 36（3）： 792-795.）

[19]陈瑶.变电站智能巡检机器人全局路径规划设计与实现[D].济南：山东大学，2015：94.（CHEN Y. Design and implementation of global path planning for substation intelligent patrol inspection robot[D]. Jinan： Shandong University， 2015： 94.）

[20]向光海.变电站巡检机器人路径规划系统设计与实现[D].成都：西南交通大学，2015：77.（XIANG G H. Design and implementation of path planning system for substation inspection robot [D]. Chengdu： Southwest Jiaotong University， 2015： 77.）

This work is partially supported by the National Natural Science Foundation of China （61603242）， the Open Project of Jiangxi Collaborative Innovation Center of Economic Crime Investigation， Prevention and Control Technology （JXJZXTCX-030）.

the Jiangxi Province Economic Crime Investigation and Prevention and Control Technology Collaborative Innovation Center Open Fund

WANG Zhongyu， born in 1993， M. S. candidate. His research interests include robot control， path planning algorithm.

ZENG Guohui， born in 1975， Ph. D.， associate professor.His research interests include robot control， power electronics and its control technology.

HUANG Bo， born in 1985， Ph. D.， lecturer. His research interests include requirements engineering， software engineering， artificial intelligence.

FANG Zhijun， born in 1971， Ph. D.， professor. His research interests include pattern recognition， intelligence computation， video analysis.