多目标点路径规划技术是移动机器人完成自主导航任务的前提与基础，其目的在于使移动机器人能在具有障碍物的环境中按照路径最短的评价标准寻找一条经过所有目标点的无碰撞路径^[1]。在实际生产生活中为尽量减少往返于各个目标点之间所需的路程和能耗，则需要优化各个任务的执行顺序，即考虑移动机器人的多目标点路径规划问题^[2-3],其求解方法主要有精确算法^[4]和启发式算法^[5-6]两类。精确算法主要用于解决规模相对较小的组合类优化问题，其计算时间往往随问题规模的增大呈爆炸式增长。启发式算法在可接受范围内给出问题的解，相比于精确算法，在处理大规模多目标点路径规划技术时，具有更高的鲁棒性、可行性^[7]。因此国内外学者主要采用启发式算法对多目标点路径规划技术及其变体问题进行研究，并针对不同地图环境提出了多种优化方法^[8-16]。文献[8]提出一种移动机器人多目标搜寻的D*–蚁群融合算法，计算出各目标点之间的最短避障距离，并将其作为评价依据规划出一条最优路径；文献[9]针对粒子群算法存在的早熟现象，将反向学习策略引入粒子群算法，并针对相应的惯性权重和学习因子进行改进。与传统的启发式算法相比，离散头脑风暴(discrete brain storm optimization, DBSO)算法^[10]具有结构简单、设计参数少以及较强的搜索能力等优点，被广泛应用于无人机路径规划^[11]、机器人定位建图^[12]、多目标协同搜索范式^[13]、多车型绿色车辆路径优化^[14]、水面清理垃圾机器人^[15]、变电站的巡检机器人^[16]等领域。文献[13]通过在环境和机器人约束下，将机器人群中的成员与DBSO算法中的个体进行匹配，提出了一种基于机器人BSO的群体机器人协同搜索框架。文献[14]设计DBSO算法解决以系统总成本最小为目标的多目标绿色车辆路径优化模型。针对DBSO算法在解决多目标路径规划时易陷入局部最优而导致早熟收敛的问题，许多学者提出了不同的解决方案^[17-18]。其中文献[17]提出一种在DBSO算法中通过保持种群多样性的策略，提高了算法跳出局部最优的概率；文献[18]提出基于讨论机制的头脑风暴算法，通过改变组内与组间讨论次数以调节算法的局部与全局搜索能力，避免了提前陷入局部最优的可能。

基于上述讨论，本文针对障碍物环境下的多目标点路径规划问题设计了一种启发式自适应离散头脑风暴算法。首先，考虑障碍物对路径规划的影响，将距离评判依据由欧式距离替换为目标点间的最短避障距离，提高规划路径的合理性。其次，针对传统DBSO算法在解决组合类优化问题时提前陷入局部最优的问题，提出一种启发式自适应路径优化策略，主要包括：1）设计交换、插入操作产生新的路径从而增加路径多样性；2）设计双向启发式交叉算子，提高路径的质量和算法收敛速度；3）设计与迭代次数相关的适应度选择函数，克服算法迭代前期收敛速度慢和后期路径多样性下降的问题，提高算法跳出局部最优的能力。

1.   多目标点路径规划问题

机器人多目标路径规划问题一般性描述为：某机器人要遍历 $ n $ 个目标点，且每个目标只访问一次，最终回到初始地点，求一条以最短距离经过所有目标点的路径^[19]。

定义遍历 $n$ 个目标点的路径为 ${S_i} = $ $({s_{i,1}}, {s_{i,2}},\cdots, {s_{i,n}},{s_{i,n + 1}})$ ， ${s_{i,n + 1}} = {s_{i,1}}$ ，目标点 ${s_{i,j}}$ 的坐标为 $({x_{i,j}},{y_{i,j}})$ 。令 $d$ 为目标点 ${s_{i,j}}$ 和 ${s_{i,j + 1}}$ 之间的最短避障距离^[20]，则遍历路径的总距离为

本文的目标是，设计离散头脑风暴算法，使 $ {D_i} $ 值最小，即实现移动机器人以最短路径遍历所有目标点。

2.   启发式自适应离散头脑风暴算法

针对移动机器人多目标路径规划问题，本文设计一种启发式路径优化策略产生新路径。同时，为解决传统DBSO算法早熟的问题，设计适应度选择函数降低算法过早陷入局部最优的可能。算法总体流程图如图1所示，具体实现步骤如下：

图  1  算法总体流程

Fig.  1  Overall flow chart of algorithm

下载: 全尺寸图片

1）初始化参数并产生 $m$ ( $m = n$ )条路径；

2）设计K-Means++聚类算法，将 $n$ 条路径分为 $K$ 个组，每组中距离最小的路径为中心个体；

3）设计与迭代次数相关的适应度选择函数，确定路径优化方式；提出启发式自适应优化路径策略，通过交换、插入操作增加路径多样性，而通过双向启发式交叉算子以提高路径质量和算法收敛速度；

4）保留适应度值低的路径，直至最大迭代次数输出最优路径，采用A*路径规划算法根据输出的最优路径依次规划行驶路线。

2.1   初始化路径及各参数

本文将所有目标点进行1~n(n为目标点个数)整数编码。在多目标点路径规划中，一条路径代表一个潜在的可行解，路径代表机器人经过目标点的顺序序列。本文采用随机生成的方式构造初始路径，并采用式(1)计算各路径的适应度值，适应度值越低表明路径越短。

2.2   K-Means++聚类算法

为了减小初始聚类中心的选取对算法的影响，本文采用聚类效果更好的K-Means++聚类算法^[21]替代传统的K-Means聚类算法。K-Means++聚类算法是在K-Means聚类算法基础上，通过设置不同位置作为聚类中心的概率来获得相对距离更远的聚类中心，降低对聚类结果的影响，从而提高算法鲁棒性。其算法实现过程包括：

1）在路径集合 $X$ 中随机选择一个路径作为中心；

2）计算每个路径与当前聚类中心之间的最短距离(即与最近一个聚类中心的距离)，用 $D(x)$ 表示；

3）计算每个路径被选中为下一个聚类中心的概率为 $D{(x)^2}\Big/\displaystyle\sum {_{x \in X}D{{(x)}^2}}$ ，采用轮盘赌的方法选择下一个聚类中心；

4）重复2）和3），直到选择 $K$ 个中心( $K$ 为人为预先设定)；

5）利用选择的初始中心采用K-Means聚类算法。

2.3   启发式自适应路径优化策略

启发式自适应路径优化策略包括3部分：1)适应度选择函数；2)单条路径优化；3)两条路径间的组合优化。其中，适应度选择函数是通过设计与迭代次数相关的函数以调节被选择概率；单条路径优化是指对某条路径中的一个位置或几个位置进行操作；两条路径间的组合优化是指对不同组中的路径进行双向启发式交叉算子操作。

2.3.1   适应度选择函数

由于算法对多样性和收敛速度随迭代次数的变化的需求符合 $\partial = \dfrac{{{\text{gen}}}}{{{G_{\max }}}}$ 的变化曲线，为降低人为设置固定参数或分段设置参数方式带来的调试难度，本文设计和迭代次数相关的适应度选择函数，使得优化算法在迭代前期通过提高两个路径间优化的操作概率，加快算法的收敛速度。此外，随着迭代次数的增加，通过提高单条路径优化的操作概率，从而增加路径多样性。为避免当迭代次数较少时计算出的 $ \partial $ 过小，以及迭代后期 $ \partial $ 无限接近1的不合理曲线变化，本文设计 $ \beta $ 和 $\gamma $ 参数，保证算法在前期的多样性，以及后期的收敛速度。适应度选择函数 $ p $ 构造如下:

式中： $ \beta $ 为最小单条路径优化概率； ${\text{gen}}$ 为当前迭代次数； ${G_{\max }}$ 为最大迭代次数； $\gamma $ 为控制最大单条路径优化概率的系数。

本文中单条路径优化概率为 $ p $ ，两条路径间的组合优化概率为 $ 1 - p $ 。算法迭代前期 $ p $ 值较小，两条路径间的组合优化概率高，收敛速度快；当迭代次数增加， $ {\text{gen}} $ 值变大，使得式（2）中 $ p $ 值增大，此时单条路径优化概率增大，多样性提高，算法跳出局部最优的可能变大。

2.3.2   单条路径优化

为增加路径的多样性，在迭代过程中对一个路径进行交换、插入操作^[22]。解 ${S_i} = \{ {s_{i,1}},{s_{i,2}}, \cdots , {s_{i,n}}\}$ 优化的具体规则如下：

交换操作（如图2所示）：在1~n区间内随机产生不同的整数，并将对应位置的元素交换。以8个目标点为例来具体说明交换操作原理：其中， ${{{S}}_{{\text{old}}}}$ 为当前 $ {S_i} $ 路径的子代路径， $ {{{S}}_{{\text{new}}}} $ 为当前 $ {S_i} $ 路径更新后的子代路径，选取一个路径如图2(a)所示，从1~8中随机产生不同的整数2和5后交换 ${{{S}}_{{\text{old}}}}$ 对应位置的元素，更新后的子代 ${{{S}}_{{\text{new}}}}$ 如图2(b)所示。

图  2  交换操作

Fig.  2  Swap operation

下载: 全尺寸图片

插入操作（如图3所示）：在1~n区间内随机产生不同的整数 $a$ 、 $b$ ( $a \ne b$ )然后将这第1个位置上的元素插入到第2个元素后。为说明插入操作的原理，同样以8个目标点为例，选取一个路径如图3(a)，随机从 $1\~8$ 产生不同的整数2和5，后将位置5的元素插入位置2后，更新后的子代 $ {{{S}}_{{\text{new}}}} $ 如图3(b)所示。

图  3  插入操作

Fig.  3  Insert operation

下载: 全尺寸图片

2.3.3   两条路径间的组合优化

启发式交叉算子以继承初代路径中的元素为基础重构可行解，具有收敛速度快的特点^[23]。由于搜索方向固定，当可行解与最优解的部分片段一致，子代路径按照同一方向搜索会产生无效搜索并可能陷入局部最优。为克服这一缺陷，本文提出一种改进搜索策略，其主体思想是：子代开始搜索方向变为双向搜索，扩大搜索范围，有利于提高算法的收敛速度。选取不同组的路径作为初代路径 ${S_1} = \{ {s_{1,1}},{s_{1,2}}, \cdots ,{s_{1,n}}\} $ 和 ${S_2} = \{ {s_{2,1}},{s_{2,2}}, \cdots ,{s_{2,n}}\}$ ，利用改进的启发式交叉算子产生子代路径的基本步骤如下：

1）随机在1~n中选取一个点作为当前点 $ {s_j} $ ，标记为 ${\rm{L}}$ ，将其作为子代路径的第一个位置；

2）分别找出 ${s_j}$ 在 ${{{S}}_{\text{1}}}$ 和 ${{{S}}_{\text{2}}}$ 的位置，若 ${s_j}$ 在初代路径的首位，则其上一位为最后一位；若 ${s_j}$ 在初代路径的最末位，则其下一位为第一位。在 ${{{S}}_{\text{1}}}$ 和 ${{{S}}_{\text{2}}}$ 中分别找到相对于 ${s_j}$ 前后位置的 ${s_{1,j - 1}}$ ， ${s_{1,j + 1}}$ ， ${s_{2,j - 1}}$ ， ${s_{2,j + 1}}$ ，并计算他们的距离 ${d_1}({s_{1,j}},{s_{1,j - 1}})$ ， $ {d_2}({s_{1,j}},{s_{1,j + 1}}) $ ， $ {d_3}({s_{2,j}},{s_{2,j - 1}}) $ ， ${d_4}({s_{2,j}},{s_{2,j + 1}})$ ；比较 $ {d_1},{d_2},{d_3},{d_4} $ 大小并将距离最小值对应的位置元素加入到子代 ${{{S}}_{{\text{new}}}}$ 中 ${s_j}$ 的后一位中；

3）删除在 ${{{S}}_{\text{1}}}$ 和 ${{{S}}_{\text{2}}}$ 中的 ${s_j}$ ，更新 ${{{S}}_{\text{1}}}$ 和 ${{{S}}_{\text{2}}}$ ；

4）重复2）和3），直到 ${{{S}}_{\text{1}}}$ 和 ${{{S}}_{\text{2}}}$ 中元素只有两个，非 ${\text{L}}$ 元素为最后一位，输出路径。

本文以8个目标点为例，说明双向启发式算子的实现过程：产生的初代个体如图4(a)所示；随机选3作为 ${{{S}}_{{\text{new}}}}$ 的第一位，设目标点3到目标点1的距离最短，经过一次2）的操作，得到图4(b)；后执行3），更新后的 ${{{S}}_{\text{1}}}$ 和 ${{{S}}_{\text{2}}}$ 如图4(c)所示；重复2）~3），直至 ${{{S}}_{\text{1}}}$ 和 ${{{S}}_{\text{2}}}$ 元素中的元素都只有被标记为 ${\text{L}}$ 的元素，循环结束，输出更新后的 ${{{S}}_{{\text{new}}}}$ ，如图4(d)所示。

图  4  改进的启发式交叉操作

Fig.  4  Improved heuristic crossover operation

下载: 全尺寸图片

2.4   最短路径规划

本文在规划过程中考虑到移动机器人在障碍环境下的不可穿越障碍的移动约束，采用A*算法^[24]规划出的最短避障距离替换无视障碍物的欧式距离，使得移动机器人在有障碍环境下规划出的路线与实际最优路线一致。

3.   仿真结果及分析

为验证本文算法的优越性及实用性，在AMD Ryzen5-4600U with Radeon Graphics、Window11、64位操作系统和MATLAB 2020b的环境下，在相同地图环境下对蚁群(ant colony optimization, ACO)算法^[25]、传统DBSO算法^[26]、蚁群算法-粒子群(ant colony optimization-improved particle swarm optimization, ACO-IPSO)算法^[9]、以及本文算法进行对比仿真。为了衡量算法的性能，文中使用了多个评价指标，其含义如表1所示。本文算法参数设置如下：最大迭代次数为 ${G_{\max }} = 500$ ，本文DBSO算法：聚类组数 $K = 5$ ，选择中心路径的概率为 $p\_c = 0.2$ ，最小单条路径优化概率 $ \beta = 0.1 $ 以及最大单条路径优化概率 $\gamma = 0.8$ 。为避免算法的偶然性，每组仿真分别进行20次，其结果如表2和表3所示。

在80×170的二维栅格地图内对各算法进行测试，设置如图5所示的简单障碍环境地图和复杂障碍环境地图。

图  5  环境地图

Fig.  5  Environmental map

下载: 全尺寸图片

3.1   简单障碍环境下各算法对比

为验证本文算法在简单障碍环境下多目标路径规划的性能，在环境中选取42个目标点进行规划，算法中的距离评估依据为目标点间的欧式距离，规划结果如图6和图7所示。图6中，黑色区域为障碍，绿色区域为目标点，白色区域为可行区域，红色区域为机器人实际行驶路径，黑线连成的回路为机器人的理想行驶路径。图6为各算法在20次仿真中最好的规划结果，其中图6(a)描述了传统ACO的规划结果，可以看出路径产生大量交叉，路径总距离较长；图6(b)和(c)分别是传统DBSO算法和ACO-IPSO算法，图中可以看出在深蓝色虚线框内S1，S2，S3的区域，由于陷入局部最优导致路径交叉，路径总距离变长。图6(d)为本文算法规划出的结果，规划出的路径无交叉，且路径总距离相较其他算法较短，同时经验证也是最短路径。由图7可以看出，在相同条件下，本文提出的DBSO算法在全局最优以及收敛速度方面上优于其他算法其中蓝色曲线为ACO，黑色为DBSO，粉色为传统ACO-IPSO，绿色为本文算法。

图  6  简单障碍环境下各算法路径规划结果

Fig.  6  Path planning results of each algorithm in simple obstacle environment

下载: 全尺寸图片

图  7  各算法在500代内的收敛曲线

Fig.  7  Convergence curves of each algorithm within 500 generations

下载: 全尺寸图片

3.2   复杂障碍环境下各算法对比

为进一步验证本文算法在复杂障碍环境下多目标路径规划的优势，采用与简单障碍环境相同的目标点进行仿真测试。与简单障碍环境不同，在复杂障碍环境下本文所提算法中采用两目标点之间的最短避障距离作为距离评估依据，规划结果如下图8所示。图8为各算法在复杂障碍环境下20次仿真中最好的规划结果，从图8(a)、(b)和(c)可以看出，在相应深蓝虚线框S4，S5，S6位置处，由于移动机器人的移动规则限制，采用传统的欧氏距离作为评估依据，在规划时算法会认为两点直线最近的点为最优解，进而导致了与实际不相符合规划顺序。由图8(d)可知，由于采用了最短避障距离作为评估依据，避免了因为距离评估问题造成的误判而增加多余的行驶距离。

图  8  复杂障碍环境下各算法路径规划结果

Fig.  8  Path planning results of each algorithm in complex obstacle environment

下载: 全尺寸图片

由表4和表5可知，当目标点数为42时，在简单障碍环境下20次仿真中，本文算法所求的距离最优解与ACO，ACO-IPSO和传统DBSO相比，分别减少了19.73%、2.64%、1.07%；而在复杂障碍环境下，本文算法所求距离最优解与ACO，传统DBSO和ACO-IPSO相比，分别减少了18.19%、7.34%、6.75%。且无论在简单障碍还是复杂障碍环境下，所提算法得到的平均解和标准差均优于其他算法。由图9可以看出，在相同环境下，本文提出的DBSO算法在全局最优以及收敛速度方面上优于其他算法，其中蓝色曲线为ACO，黑色为DBSO，粉色为传统ACO-IPSO，绿色为本文算法。此外，分析标准差数据可知，多次试验中本文算法计算出的距离变化幅度较小，因而较其他算法，所提方法具有较好的鲁棒性。综上，可以看出在不同环境下本文所提算法均可以规划出令人满意的效果。

图  9  各算法在500代内的收敛曲线图

Fig.  9  Convergence curves of each algorithm within 500 generations

下载: 全尺寸图片

4.   结束语

本文针对移动机器人多目标点路径规划问题提出了一种有效的解决方案。考虑传统DBSO算法在处理多目标点路径规划问题上的局限性，提出了改进的启发式路径优化策略，进而增加了算法的收敛速度。通过设计与迭代次数相关的适应度函数，降低了陷入局部最优的概率。将欧氏距离更换为更加实际的最短避障距离，提高了算法的实用性。仿真结果表明，本文所提启发式自适应DBSO算法可以缩短移动机器人往返目标点之间的路程，从而有效解决移动机器人多目标点路径规划问题。将本文提出的新方法应用到动态环境下的移动机器人的多目标点路径规划是下一步的研究内容。