一种MAKLINK 图多节点链路建模的路径规划研究

孙培刚，张全禹，许春和

（绥化学院电气工程学院，黑龙江绥化 152061）

路径规划建模的智能优化问题一直是人们深入研究的方向，特别是在航海、航空及智能机器人等路径规划研究方面具有非常重要的意义[1]。常用的路径规划建模方法主要有可视图法、栅格法、人工势场法、随机树法和链接图（MAKLINK）法[2]。其中，可视图法算法灵活，规划方法简单，但对障碍物形状有一定的要求，每次搜索需要重新构建视图模型，处理时间较长；栅格法是研究较为广泛的方法之一，常用于机器人路径寻优，但计算复杂，同时要兼顾栅格分辨率、环境信息存储量及规划时间等因素；人工势场法实时性较好，但易陷于锁死状态；随机树法存在搜索空间大、效率低等问题[3]；MAKLINK 法优点是建模的障碍物固定后，连通图位置随之固定，但连通图构建复杂，并与障碍物的数量及形状有关[4]。

文中主要研究了MAKLINK 图路径位置变化时，获得的最优路径是否会与约束条件产生冲突的问题，并通过蚁群算法分别对基本MAKLINK 图和多节点链路MAKLINK 图的规划建模进行了优化，通过改变各自路径端点位置对两种方法优化的路径长度、迭代次数、鲁棒性等参数进行了比较与分析。

1 MAKLINK建模

1.1 MAKLINK图的可行路径构建

在构造MAKLINK 图之前，首先设置障碍物，障碍物的形状和数量可自行设置，将障碍物的某一顶点与其他顶点或空间边界点相连形成链路线，要求链路线不得穿过障碍物。在每条链路线上设置节点，根据MAKLINK 图的实际情况确定节点与节点间连线未穿过障碍物的为可行线段，并形成可行线段集合[5]。通常设置的每条链路线的节点为单节点，即该链路线的中点,如图1 所示。图中阴影部分为障碍物，S 为路径起点，T 为终点，V1～V20 为节点，虚线为链路线，细实线为可行路径集合。

该文在每条链路线上设置多个节点（以三个节点为例，即该链路线的三个等分点，节点号为V1～V60）形成多节点链路，以提高次优路径的精确度，并根据障碍物及节点位置生成可行性路径布局图，可行路径如图2 所示。

图2 多节点链路MAKLINK可行路径示意图

由图2 可知，随着节点数的增加，可行线段数量增多，路径的选择更加广泛，相对于传统的单节点链路，可行路径更加理想，但增加了MAKLINK 图路径规划设计的冗余性。

1.2 dijkstra 算法

dijkstra 算法功能是在众多的可行路径中搜寻一条距离最短的次优化路径，并将次优化路径所经过的节点序列号记录下来，作为蚁群优化的一个初始条件[6-8]，其算法流程如图3 所示。

图3 dijkstra算法流程

通过dijkstra 算法先对各节点间距离进行计算，并将节点距离数据存储到指定变量中。然后根据计算的数据对可行节点间路径的最小值进行全局搜索，并更新和存储节点号。当路径节点到达终点后结束搜索，输出最小路径节点的序列号[9]。通过程序算法计算的节点间距离数据中1 000 代表节点间路径不可行，其他数据为可行路径各节点间的距离数据。根据图2 中的链路、节点及障碍物的位置，计算的S-V1 的距离数据为22.360 6，表示起点S 与节点V1 间的路径距离为22.360 6 m；S 与节点V4 间的计算数据为1 000，表示S 与节点V4 间路径不可行。根据搜索结果，输出的最小路径节点号为S、V6、V10、V45、V31、V20、V42、V49、T，计算的次优路径距离为238.904 1 m。

2 蚁群算法的路径优化

对dijkstra 算法得到的次优化路径通过蚁群算法做进一步优化，以获得MAKLINK 图的最优路径。优化流程如图4 所示。

图4 蚁群优化算法流程

蚁群初始化参数主要包括能见度参数、信息素挥发系数、信息素增强系数及蚂蚁个数等[10-12]。设在t时刻的信息素强度为τij(t)，则：

其中，ρ为蒸发系数，为第k只蚂蚁在节点Vi与Vj的路径上释放的信息素浓度启发信息素信息后，蚂蚁开始依次在每条链路上搜索最佳路径点，链路Li上的搜索点可表示为：

其中，hi∈[0,1]为比例参数，Pi1和Pi2为链路Li上的端点[13]。当蚂蚁搜索到终点后，更新信息素信息，并判断是否满足终止条件，若满足则输出最优化路径信息，否则重新搜索[14-16]。

3 优化结果分析

基本MAKLINK 图单节点链路路径示意图如图5 所示。图中S[5,130]为设置的起点，T[190,70]为设置的终点，在次优化路径的基础上通过蚁群算法对其进行了优化计算，获得最优路径。图中，粗点划线为dijkstra 算法得到的次优化节点路径，粗实线为经过蚁群算法优化的最优路径。

图5 单节点链路最优路径示意图

同等条件下，采用多节点链路法对起点S[5,130]到终点T[190,70]之间的路径进行了优化设计，最优路径示意图如图6 所示。

图6 多节点链路最优路径示意图

文中对基本单节点链路MAKLINK 算法和多节点链路MAKLINK 图算法的适应度值进行了比较分析，适应度值变化曲线如图7 所示。其中点划线表示基本单节点链路MAKLINK 图的适应度值进化曲线，迭代102 次后接近最优解，最短路径为230.6；细实线为多节点链路MAKLINK 图的适应度值进化曲线，迭代147 次后接近最优解，最短路径为227.3。可以看出，多节点链路相比于单节点链路优化的路径减小了1.43%，但由于多节点链路的MAKLINK 图路径规划较为复杂，可行线段数量多，需要较多的迭代计算。

图7 适应度值变化曲线

当MAKLINK 图中起点S 和终点T 的坐标位置分别改为[5,100]和[190,45]时，dijkstra 算法得到的次优化节点路径、最优化路径和距离都随之发生变化。由于单节点链路的优化算法以中心节点为中心，在整条链路上进行全局搜索寻优，容易破坏适应度函数的约束条件，单节点链路的优化路径如图8 所示。可以看出，最优路径已穿过障碍物，破坏了MAKLINK 图算法的约束条件[17-18]。

图8 单节点链路最优路径示意图

图9 为多节点链路路径，虽然建模算法复杂，但是次优化路径较为理想，算法以次优化路径经过的节点为中心，在小范围内进行局部寻优，获得的最优路径比较接近最优解。并且当路径端点坐标变化时，仍然满足约束条件,具有较强的鲁棒性。

图9 多节点链路最优路径示意图

4 结束语

文中基于MAKLINK 图的路径规划及蚁群优化算法，提出了一种多节点链路的路径规划算法，解决了基本MAKLINK 图路径规划算法易于破坏适应度函数约束条件的缺陷，提高了MAKLINK 图路径规划建模的灵活性和对环境条件的适应性。算法也存在一些不足，如随着链路上节点数目的增多，存在可行路径的建模繁琐、迭代次数增加、程序运行时间较长等问题，在最优路径的优化算法等问题上还有待于进一步改进。