基于选择交叉烟花算法的无人车路径规划

高万博，朱俊武，章永龙，章小卫

（扬州大学 信息工程学院，江苏 扬州 225000）

0 概述

移动机器人路径规划是机器人研究领域中的重要分支，无人车是一种可以远程控制与自主导航的移动机器人。无人车路径规划问题［1］是指无人车在给定环境下，寻找一条满足一定约束条件的无碰撞路径［2］。目前，群智能算法是解决移动机器人路径规划问题的主要方法［3］，通过迭代生成新的可行解，在搜索空间中不断探索与改进，最终寻找到满足约束条件的最佳可行解。群智能算法主要包括粒子群算法［4］、蚁群算法［5］、遗传算法［6］、烟花算法［7］等。

文献［8］提出一种新型启发式算法，称为烟花算法，其具有随机性、局部性、爆发性、隐式并行性、多样性、瞬时性等特点，通过烟花在空中爆炸产生火花的过程来模拟算法在搜索空间中求解问题的过程，具有较优的优化求解能力。

在路径规划问题中，因算法搜索空间较大，规划环境较复杂，导致烟花算法难以寻找到全局最优路径，甚至寻找到的路径会穿越障碍物。针对上述问题，研究人员对烟花算法进行改进。文献［9］结合烟花算法与蚁群算法提出一种混合算法，用于解决智能移动体避障的问题，通过加入先锋火花操作提高搜索效率，并使用蚁群算法来实现避障的目的。文献［10］在基本烟花算法的基础上增加量子行为作为新的爆炸策略，使得烟花算法对全局和局部最优解都具有较优的搜索能力。文献［11］通过可视图法构建士兵视觉场景，利用插入和删除节点操作解决路径不连续的问题。一些研究人员采用基于深度学习的方法来解决该类问题。文献［12］对卷积神经网络进行训练，构建图像与动作的映射关系，实现移动机器人路径规划。文献［13-15］将图像作为唯一输入，训练强化学习网络实现移动机器人在未知环境下自主完成避障和区域覆盖的任务。文献［16］通过改进的深度Q 网络（DQN）训练多个机器人进行路径规划，以完成无人仓库调度任务。文献［17］通过深度强化学习模型学习改进启发式方法，从而解决旅行商问题。文献［18-20］通过改进的深度强化学习模型解决车辆路径优化及其变体问题。

基本烟花算法在三维地形环境下进行路径规划时，因部分路径节点经过爆炸操作会远离原始路径且种群的路径片段间缺乏信息交互，导致收敛速度和探索最优解的能力降低。针对上述问题，本文提出选择交叉烟花算法。通过路径节点的轮盘选择操作，根据路径节点的适应度函数进行轮盘赌，以解决部分路径节点偏离轨迹的问题。借鉴遗传算法中的交叉变异操作，引入选择交叉变异操作，将筛选出的路径片段与其他路径片段进行交换，从而提高烟花之间的信息交互性。

1 问题描述

1.1 地形环境

无人车根据全局三维地形环境［21］建立三维空间直角坐标系O-xyz，沿x轴、y轴将空间分割为m×n个栅格，将栅格地形环境的最大高度值z作为该栅格的内容值。通过该方式将地形环境表示为zi=Map(xi，yi)的栅格矩阵，其中xi、yi表示栅格矩阵的行列坐标位置，zi表示栅格值，即此栅格所在区域的地形高度。在地图中的威胁区域主要是指无人车不能进入的区域，如沼泽、湖泊等，由一个矩阵G表示，如式（1）所示：

图1 栅格法构建的地形矩阵Fig.1 Terrain matrix constructed by grid method

1.2 适应度函数

本文从燃耗代价、威胁代价和平滑代价3 个角度衡量路径优劣，适应度函数如式（2）所示：

其中：w1、w2、w3为平衡各指标的权重系数，且1；Cf为无人车行驶时产生的路程燃耗代价；Cd为无人车经过威胁区域时产生的威胁代价；Cs为无人车转弯行驶时产生的转角平滑代价。

1.2.1 燃耗代价

其中：kl＜1 ＜kh；Xi＝(xi，yj，zi，j)表示xi列yj行，值 为zi，j的栅格块。

路径的燃耗代价为各路径节点燃耗代价之和，如式（5）所示：

1.2.2 威胁代价

无人车规划的路径需远离威胁区域，保证路径的安全性。路径点的威胁代价通过路径点与威胁区域的圆心距离来描述，距离越远则路径点越安全。路径点Xi的威胁代价如式（6）所示：

其中：R为威胁区域的半径；为威胁区域中心点的坐标和高度值。当路径节点的距离小于最小威胁区域半径时，Cplot_d大于1，则该点不符合构成路径的要求。

威胁区域信息表示如图2 所示。

图2 威胁区域坐标图Fig.2 Coordinate diagram of the threat region

路径节点A、B、C距圆心的长度分别为d1、d2、d3，其 中d1＜R＜d2＜d3，因 此Cplot_d(A) ＜1 ＜Cplot_d(B) ＜Cplot_d(C)。路径节点A不符合路径构成要求将被舍弃，节点C的威胁代价比节点B更低。

路径的威胁代价为各路径节点威胁代价之和，如式（7）所示：

1.2.3 平滑代价

无人车需满足自身的动力学要求，避免转弯时角度太小。路径点平滑代价用路径点与其前后节点形成的夹角来描述。夹角越小，无人车的转角越大，路径越不平滑。路径节点Xi的平滑代价如式（8）所示：

其中：α为无人车的最小转角；θi为行驶过程中路径节点Xi的夹角。当θi小于无人车的最小转角α时，Cplot_s大于1，则该路径节点不符合路径构成要求，应当舍去。平滑代价信息表示如图3所示，无人车沿着∠OAB方向进行转角，最小转角角度为∠OAA'即α。路径节点A的夹角θ大于最小转角α，则保留该节点。

图3 平滑代价坐标图Fig.3 Coordinate diagram of the smooth cost

路径的平滑代价为各路径节点的平滑代价之和，如式（9）所示：

2 基本烟花算法

基本烟花算法将烟花看作空间中的一个解，通过对烟花进行爆炸操作，选择不同的火花对邻域进行搜索。其基本原理是烟花对应的适应度值越小，则该烟花爆炸产生的火花数量越多，爆炸幅度越小；相反，若烟花对应的适应度值越大，则该烟花爆炸产生的火花数量越少，且爆炸幅度越大。

在基本烟花算法中，第i个烟花的爆炸强度如式（10）所示：

第i个烟花的爆炸幅度如式（11）所示：

其中：fmin为当前种群中的最小适应度值为控制烟花爆炸幅度的常数。

为了增加种群中烟花的多样性，基本烟花算法随机选择j个维度对烟花进行高斯变异，如式（12）所示：

其中：g表示均值为1、方差为1且满足高斯分布的随机数。

在烟花爆炸后产生的变异火花和爆炸火花可能会超出可行域范围，根据映射规则重新映射回可行域内，如式（13）所示：

其中：为三维地形环境中第k维的上边界；为三维地形环境中第k维的下边界；为 第i号烟花的第m个路径节点在第k维的位置。

烟花算法通过选择操作对产生的新火花进行筛选，并选择部分火花作为下一代烟花，如式（14）和式（15）所示：

其中：R(pi)为火花pi与其他火花之间的距离求和；K为当前种群中所有火花的个数；Pr(pi)为烟花pi被选中的概率。

3 本文算法

3.1 轮盘选择操作

本文通过分析基本烟花算法迭代生成的路径，发现路径中可能存在部分路径节点偏离轨迹的问题。烟花算法的爆炸操作示意图如图4 所示。

图4 烟花算法爆炸操作示意图Fig.4 Schematic diagram of explosion operation of fireworks algotithm

路径节点Xi、Xj的适应度值远大于路径中的其他节点。因此，本文提出针对路径节点的轮盘选择操作，提升具有高适应度值的路径节点被选择并进行变异的概率。图4 中为经过轮盘选择后再变异操作得到的新路径节点。本文轮盘选择操作分为以下3 个步骤：

1）计算路径节点Xi的适应度值，如式（16）所示：

2）通过轮盘赌［22］的方法对需要爆炸的节点进行选择，路径节点Xi被选择进行爆炸的概率如式（17）所示：

其中：Q(i)为P(i)的累计概率；select(k)为用于保存k个被选中的路径维度；rand 为生成均匀分布的0～1随机数，若rand 在[Q(i)，Q(i+1)]区间内，则将i存入select 中。

3）对被选择的路径节点进行位移操作，如式（18）所示：

因此，本文通过爆炸位移使路径节点在爆炸幅度内进行一次位置变化。

3.2 选择交叉变异

基本烟花算法通过高斯变异和爆炸操作对烟花的节点进行单点变异，并未考虑烟花之间路径片段的交互变异。例如，在一次迭代过程中，一个烟花Pi=，会在某一段路径片段中出现较高的适应度值，假设为P'=，而单一路径节点的变异方式并不能显著提高烟花适应度值。

本文借鉴遗传算法中的交叉变异因子［23］思想，提出选择交叉变异，并将其作为新的火花变异方式，通过3.1 节轮盘选择的方式选择其中两个节点作为路径片段，并将其与另一个烟花之间的路径片段进行交换，通过该方式增大最优解出现的概率［24］，以加强种群中烟花之间的信息交互。随机选择的两个父代烟花par1、par2通过轮盘选择操作产生路径节点，对选中的路径节点进行路径片段交叉，以得到选择交叉火花child1、child2，如式（19）所示：

图5 选择交叉火花的产生流程Fig.5 Generation procedure of selection crossover spark

3.3 算法流程

选择交叉烟花算法的具体流程如算法1 所示。

算法1选择交叉烟花算法（SC-FWA）

输入地形Map，威胁区域矩阵G，最大迭代次数maxgen

输出最优路径pb

1.随机初始烟花种群路径P={p1，p2，…，pN}

2.for i=1，i ≤maxgen，i++

3.通过式（2）计算种群中每个烟花适应度值fcost

4.通过式（10）和式（11）计算烟花的爆炸幅度和火花个数

5.通过轮盘选择操作式（17）筛选出需要位移的路径节点Xselect

6.依据式（18）在爆炸幅度内对Xselect进行爆炸位移

7.随机选取路径节点Xj依据式（12）进行高斯变异

8.通过式（19）将被选择的路径par1、par2进行交叉变换，产生选择交叉火花

9.通过式（13）对变异后超出可行域的路径节点映射回可行域内

10.保留最优烟花，将其余爆炸火花、高斯变异火花、选择交叉火花通过式（14）选择下一代烟花。

步骤1 在搜索空间中通过随机选择符合适应度值要求的n个路径节点作为初始路径，并构建N条初始路径以构成烟花种群。步骤2～步骤10 在给定的最大迭代次数内循环使用选择交叉烟花算法，其中步骤3 和步骤4 计算适应度函数，得到爆炸幅度与爆炸强度，步骤5～步骤8 产生爆炸火花、高斯变异火花和选择交叉火花，步骤9 对超出可行域的路径节点进行映射，步骤10 通过选择操作对火花进行筛选，形成下一代烟花。当达到最大迭代次数后，算法输出最优烟花，并作为无人车的规划路径。

4 实验与结果分析

4.1 实验环境与参数设置

本文在MATLAB 2018b 上进行仿真实验，计算机配置为2.60 GHz CPU，16 GB RAM、64 位操作系统。

本文将蚁群算法（ACO）［25］、基本烟花算法（FWA）、改进烟花算法（IFWA）［11］、选择寻优烟花算法（SC-FWA）进行对比实验。SC-FWA 的实验参数：最大迭代次数max_gen=300，初始烟花个数N=10，最小转角α=π/2，最大爆炸幅度=10，最大爆炸强度=10，威胁代价C1=0.2，平滑代价C2=0.2，燃耗代价C3=0.6，上坡燃耗系数kh=0.2，下坡燃耗系数kl=0.5，搜索空间上界=100，搜索空间下界=1，简单地形环境适应度函数阈值Fs=270，复杂地形环境适应度函数阈值Fc=750。

4.2 结果分析

为验证选择交叉烟花算法的收敛性和高效性，本文将选择交叉烟花算法的两类改进操作分开进行对比分析。其中加入轮盘选择操作的烟花算法（S-FWA）是在基本烟花算法的基础上对不同适应度值的路径节点进行轮盘赌操作；加入选择交叉变异的烟花算法（C-FWA）是在基本烟花算法的基础上随机选择不同的路径片段进行交换。本文将ACO、FWA、IFWA、S-FWA、C-FWA、SC-FWA 在简单地形和复杂地形下进行实验对比。当执行完给定的最大迭代次数后，不同算法在简单地形和复杂地形下的路径适应度值如表1 所示。

表1 不同算法的路径适应度值对比Table 1 Path fitness values comparison among different algorithms

FWA、IFWA、S-FWA、C-FWA、SC-FWA 均找到了低于ACO 适应度值的路径，说明烟花算法具有较优的空间探索能力，其中C-FWA 相较于IFWA、S-FWA、FWA 适应度值更低。因此，C-FWA 通过选择交叉变异进行烟花间的片段交换，以增强烟花算法中烟花间的交互性，从而有效提升探索最优解的能力，但其不足是加入了新的交叉操作会导致运行时间较高于其他基本烟花算法。

在简单地形和复杂地形中，若算法探索到低于适应度函数阈值的路径时，则终止程序并记录运行时间，不同算法在简单地形和复杂地形下的运行时间如表2 所示。

表2 不同算法的运行时间对比Table 2 Running time comparison among different algorithms

FWA、IFWA、S-FWA、C-FWA、SC-FWA 运行时间均低于ACO，说明烟花算法具有高效性。其中S-FWA 相较于IFWA、C-FWA、FWA 运行时间更短，由此可见，通过轮盘选择操作提高偏离路径节点的变异概率，从而加快烟花算法的收敛速度。但由于S-FWA 减弱了烟花种群中烟花的多样性，因此探索最优解的能力降低，当完成所有迭代次数后，路径适应度值较高。

SC-FWA 通过轮盘选择操作和选择交叉变异操作，结合S-FWA 中收敛速度快和C-FWA 中搜索全局最优解能力强的特点，在简单和复杂地形中，运行时间和路径适应度值均优于IFWA、FWA、ACO。因此，SC-FWA 具有一定的收敛性和高效性，规划的路径适应度值更低，运行时间更短。

在100 km×100 km的仿真简单和复杂地形环境下，ACO、FWA、IFWA、SC-FWA算法的路径对比分别如图6和图7所示（彩色效果见《计算机工程》官网HTML版）。其中，（0，0）为起始点，（100，100）为目标点。不同颜色代表区块的高度值（如山丘、山峰等），蓝色区域为平原区，黄色区域为山峰，圆圈标识的圆形区域为威胁区域。

图6 在简单地形下不同算法的路径规划对比Fig.6 Path planning comparison among different algorithms in simple terrain

图7 在复杂地形下不同算法的路径规划对比Fig.7 Path planning comparison among different algorithms in complex terrain

简单地形较为单一，大部分为平原地区。从图6可以看出，4 种算法均找到了近似全局最优解，威胁代价与转角代价均相近。但SC-FWA 路径长度更短，燃耗更低。而ACO 经过部分山地区域，导致燃耗增加。从图7 可以看出，在复杂地形下，由于加入了燃耗代价，将转角代价和威胁代价作为适应度函数，SC-FWA 规划的路径远离了威胁区域，并且路径更加平滑，无人车选择行驶的路径地形更加平坦，减少了上坡下坡的燃耗，因此规划的路径适应度值更低。IFWA 找到了与SC-FWA 相近的路径，但是生成的路径经过山地地形，增加了燃耗消耗。而FWA 和ACO 陷入了局部最优解，没有找到最合理的路径。FWA 相对ACO 产生的路径更加平滑，但是规划的路径经过了山地，导致燃耗代价升高。相对于SC-FWA和IFWA，FWA 规划的路径距离威胁区域更近，ACO虽然绕过了山地地形，但是规划的路径不平滑，转角过多，距离威胁区域较近。

在简单地形和复杂地形下FWA、IFWA、ACO 和SC-FWA 算法的收敛曲线分别如图8 和图9 所示。

图8 在简单地形下不同算法的收敛曲线对比Fig.8 Convergence curves comparison among different algorithms in simple terrain

图9 在复杂地形下不同算法的收敛曲线对比Fig.9 Convergence curves comparison among different algorithms in complex terrain

烟花适应度值越低则表示生成的路径代价越小、产生的路径更加远离威胁区域、路径更加平滑且燃耗更低。在简单地形下，SC-FWA 各个时期的适应度值均优于FWA、ACO、IFWA，并且在迭代第65 次时，SC-FWA 算法已基本收敛。FWA、ACO、IFWA 算法适应度函数变化不大，说明产生的解均靠近全局最优解。在复杂地形下，SC-FWA 的适应度值在前期下降更快，当迭代次数为150～200 时，陷入了与IFWA 同样的局部最优解，通过选择交叉操作，在迭代200 次后跳出局部最优解，以搜寻到适应度值更小的路径。在迭代后期，SC-FWA 找到了相比于FWA、ACO、IFWA更优的路径。

实验结果表明，通过构建适应度函数，使得SC-FWA 规划的路径更加平滑且远离威胁区域。在FWA 的基础上加入了轮盘选择操作和选择交叉变异，提高了低适应度节点被选择进行变异的概率，并使得烟花之间可以进行信息交互。因此，SC-FWA在保证烟花多样性的同时提高了算法的搜索效率，使算法在不同的地形环境下都具有良好的适应性，不易陷入局部最优解，使其具有更快的收敛速度，规划出更安全、高效的路径。

5 结束语

本文将三维地形环境下无人车路径规划问题转化为多约束条件的优化问题［26］，提出选择交叉烟花算法。为了更真实地模拟无人车在三维地形环境下的行驶过程，引入燃耗代价、威胁代价和平滑代价作为适应度函数对路径进行评价，使产生的路径更加平滑且远离威胁区域。仿真实验结果表明，相比ACO、FWA、IFWA等算法，本文算法具有较优的求解性能和较快的收敛速度，使无人车在较短的时间内规划出更优的路径。下一步将考虑在三维地形环境下融合改进的烟花算法与强化学习模型，使多个无人车可以学习合作避障策略，以有效规避动态障碍物。