面向变电站运维的智能机器人路径规划算法研究

吴振跃，章程熙，陆 昱，乔亚兴，黄维华，周 琪

(1.国网上海市电力公司市南供电公司，上海 200072；2.上海服泽能源科技有限公司，上海 200025)

近年来，国家对电力系统建设投入很大，变电站工作环境复杂，稳定性要求极高，这给当前变电站运维提出了更高的要求。智能机器人以其稳定、可靠、智能的优点在国内电力系统内变电站运维中应用应前景广阔[1-4]。

变电站运维机器人在变电站运维工作中具有广阔的应用前景。提高智能机器人自主性是发展的重要趋势。该领域中，路径规划是一个基本问题[5]。运维机器人执行任务时需要规划出一条从起始点到指定位置的安全、平稳的路线。这条路径应该尽量使得从起点到目的地的成本最低[6]。路径规划的好坏直接决定了任务是否能够顺利完成。因此，路径规划对于变电站运维机器人的任务完成起到举足轻重的作用，它是变电站运维机器人实现自主导航的基础[7]。变电站运维机器人路径规划算法成为变电站运维机器人技术的研究重点。因此，研究基于全局地图的路径规划技术具有很好的应用前景和使用价值。

本文针对变电站运维机器人寻路问题对标准 A 星算法进行深入的研究，分析A星算法启发函数计算的启发代价与实际代价之间的关系对于寻路结果的影响，提出基于向量叉积因子的A星算法。最后设计仿真软件，通过仿真试验证明基于向量叉积因子的A星算法在变电站运维环境中的路径规划性能优越。

1 路径规划算法

A星算法是在Dijkstra算法基础上进行改进，使用启发信息来引导搜索方向，让搜索不再具有 “盲目性”，使搜索过程更具智能性，极大提高了搜索的效率，得到了广泛的应用。

该算法是从起始点开始在它周围的可能成为路径的点中选择出最合适的点，点的合适程度可用估价函数来计算，代价越小就越合适。选择出最合适的点，然后以该点为扩展点，将它周围可能组成路径的点再进行代价计算。这样循环下去，直至找到目标点。因此，该算法的重点在于它的估价函数。

1.1 A 星算法的估价函数

在启发式搜索中，估价函数占有重要地位。它用来计算地图中各个顶点的重要程度。通过估价函数计算各个顶点的数值来评估顶点对于组成路径的重要程度。

依据各个顶点的重要程度来规划出一条从起始点到终点的最优路径。

A星算法的估价函数：

F(n)=G(n)+H(n)

(1)

式中n——当前节点；F(n)是节点n到目标节点的总估算代价；G(n)——从起始点开始沿着已经生成的路径到当前节点的实际代价；H(n)——从当前节点到目标节点的最优路径的估计代价，被称为启发函数。

在变电站运维机器人路径规划问题中，需要对地图进行栅格化处理然后对环境进行建模，通过建立网格地图对环境进行抽象处理。

在网格地图中，不同情况下应采用不同的启发式函数。启发式函数的距离应与所允许的移动方式相匹配。

设当前点坐标为(x1,y1) ，目标点坐标 (x2,y2)。

(1)在正方形网格中，允许向四邻域移动，可以扩展当前点的上、下、左、右四个点。此时应使用曼哈顿距离作为启发函数。曼哈顿距离是两个点在标准坐标系上的绝对轴距总和。在两维空间中的计算公式：

d=|x1-x2|+|y1-y2|

(2)

(3)

在正方形网格中，允许任何方向的移动，应采用欧式距离作为启发函数，欧式距离为两个点之间的直线距离。二维空间中欧式距离的计算公式：

(4)

1.2 A 星算法的寻路流程

A星算法在扩展路径时，为了避免重复遍历节点，A星算法将创建两个空表：OPEN表和CLOSE表。OPEN表用来存放没有访问过的节点，CLOSE用来存放已经访问过的节点。A星算法使用估价函数计算考察点的估计代价，将选择估价函数值最小的点进行路径扩展，具体流程如下。

(1)定义两个空表，命名为OPEN表和CLOSED表，其中OPEN用于存放未访问过的顶点，CLOSED表用于存放已经访问过的顶点；

(2)把起始点S存储到OPEN表中；

(3)判断OPEN表是否有顶点，若没有顶点，则搜索过程失败；

(4)若OPEN表中有顶点，选出OPEN表中总估计代价值最小的节点N，将其移入CLOSED表；

(5)判断节点N是否为目标顶点T，若是，则表示路径搜索成功，算法结束；

(6)若不是目标节点T，则扩展搜索N的子顶点Vi(i≤n，n为节点N的子节点数目)，计算每个子节点的总估价代价F(Vi)值。判断Vi是否存在于OPEN表或CLOSED表中：

若Vi同时不存在于OPEN表和CLOSED表中，则将其存放于OPEN表，并给它加个指针指向父顶点N；

若Vi已存在于OPEN表中，则对OPEN表中的总估价代价F(Vi)值进行更新，若新计算的F(Vi)值比OPEN表中F(Vi)旧值更小，则代替之，并将它的指针改为指向父顶点N；

若Vi已存在于CLOSED表中，则忽略此顶点，继续访问节点N的其他子顶点。

(7)跳转至步骤(3)，一直循环下去，直到满足算法退出条件：找到路径或者寻找路径失败。程序流程图，如图1 所示。

2 基于向量叉积因子的A星算法

因为估价函数含有启发部分，它包含目标点等有用的信息，使得A 星算法的搜索具有方向性，从而减少了遍历点的数目，提高了算法的效率。通过分析A 星算法的启发代价，针对启发代价与实际代价有差异的问题，提出了向量叉积因子优化的A 星算法。

2.1 向量叉积的计算

在栅格地图中，设起点坐标为(start_x,start_y),目标点坐标为(goal_x,goal_y), 当前节点的坐标为(current_x,current_y)。

设从当前点到终点的横坐标差为dx1；从当前点到终点的纵坐标差为dy1；从起点到终点的横坐标差为dx2；从起点到终点的纵坐标差为dy2。因此，从起点到目标点的向量与从当前节点到目标点的向量叉积：

cross=|dx|·dy2-dx2·dy1

(5)

2.2 向量叉积对启发函数权重的优化

计算出从起点到目标点的向量与从当前节点到目标点的向量叉积值后，把向量叉积因子加入到启发函数权重中，以此对估价函数进行优化。因为向量叉积值比较大，过大的向量叉积值会使计算出来的计算代价远远大于实际代价，所以将它乘0.001后再加入到启发函数的权重中。

设启发函数的权重：

weight=1+0.001cross

(6)

则估价函数：

F(n)=G(n)+(1+0.001cross)

(7)

因为启发函数的权重始终是大于1的，向量叉积因子增加了启发函数的权重，这将使得A星算法在扩展时候更具有方向性。在扩展的点距离起点到目标点之间的连线相对较远时，向量叉积值将会变大，所以启发函数的权重变大，该点的估计代价也将会变大。

因为选择open表中的所有点的估计代价最小的节点进行扩展，所以通过增加函数向量叉积因子的权重将会放大当前点的启发代价，使得A星算法忽略掉远离起点到目标点的连线点，算法扩展时更倾向于扩展与起点到目标点的连线距离相对近的点。这使得A星算法扩展点大大减少，提高了算法的运行效率，可以在很短时间内得到一个路径较佳的结果，这对于大地图寻路问题将有很强的适用性。

综上所述，增加启发函数的权重将会使A星算法更具有方向性，在权重中加入向量叉积因子会使得该权重更具有智能性，它将更偏向于遍历离起点与目标点之间连线较近的节点。通过这种增加权重的方式，将一些起点与目标点之间连线较远的点挤出考察区域，这将使算法运行过程中遍历节点的数目将大大减少，从而提高算法运行效率。

3 路径规划算法仿真

搭建试验平台对改进后的A星算法进行试验。通过与标准A星算法、向量叉积因子优化的A星算法进行对比，证明向量叉积因子优化的A星算法在寻路方面具有优越性。

3.1 仿真软件设计

本次试验平台为笔记本电脑联想-Y430p，处理器为 intel core i5-4210M，内存为12 GB，使用的操作系统为Win10，使用的编程软件为VC++6.0，编程语言为 C 语言。 基于VC++6.0软件新建了一个Win32 Application项目。仿真界面设计如图2所示。

该仿真软件主要有地图构建、自建地图、算法选择、结果显示这4个功能。

3.1.1 地图构建

可以设置障碍密度和栅格大小来新建一个随机地图，可以将起点栅格设置为红色，无障碍的栅格设置为白色，有障碍的栅格设置为黑色，目标点栅格设置为绿色。

单击清空地图的按钮可以清除界面上的地图信息和寻路结果信息。

单击清除路径的按钮可以清除界面上的路径。

单击保存地图的按钮可以保存当前的地图，默认保存地图的文件路径在项目当前路径下。

单击读取地图的按钮可以读取最近一张保存的地图。

单击扩展点的按钮可以显示算法运行的扩展点，显示的栅格颜色为黄色，再次单击该按钮可以取消显示扩展点。

3.1.2 地图设置

可以自由设定地图，先单击清空地图按钮，新建一个空白的栅格地图，然后单击起点、终点和障碍点按钮，分别设置起点、终点和障碍点，可实现自建地图的功能。

单击取消点、起点、终点和障碍点的按钮可以修改地图，使用取消点的功能

可以取消掉起点，然后使用起点的功能选择新的起点，从而实现改变起点位置的功能。

3.1.3 算法选择

启发函数的权重可以选择权重为1的标准值、含有向量叉乘因子的权重。

3.1.4 结果显示

算法运行结果主要包含两个部分，路径和运行结果指标。

路径通过设置不同颜色显示不同算法的路径，在四邻域A星算法中，设置权重为1的算法运行结果路径颜色为蓝色，含有向量叉乘因子的权重的算法运行结果路径颜色为紫色、模糊权重的算法结果路径为棕色。在八邻域A星算法中，设置权重为1的算法运行结果路径颜色为黄色，含有向量叉乘因子的权重算法运行结果路径颜色为灰色、模糊权重的算法结果路径为青色。

3.2 A星算法仿真

由理论部分可知，启发函数的权重有以下两种：值为1的标准权重、含有向量叉乘因子的权重。通过仿真试验，比较不同权重下A星算法的运行结果，证明向量叉积因子优化的权重对改进A星算法性能上的优越性。

建立一个随机地图，障碍密度为30% ，栅格大小为8，进行仿真试验，分别仿真了启发函数权重为1的标准A星算法，含有向量叉乘因子的启发函数权重的A星算法。

通过进行仿真试验，得到的试验结果如图3所示。

4 结语

作为寻路算法领域可靠性比较高的算法，A星算法有广泛的应用前景。本文在标准A星算法的基础上，提出了一种思路：使用向量叉积因子作为智能的启发函数权重，提出了基于向量叉积因子的A星算法。该优化方法可以大大减少遍历点数目，提高了算法的运行时间。