范江波，王 彧，郑 昆，李 锐，刘志坚，段 朋

(1.云南电网有限责任公司 昭通供电局，云南 昭通 657000；2.昆明理工大学 电力工程学院，云南 昆明 650093；3.聊城大学 计算机学院，山东 聊城 252000)

在复杂作业环境中，路径规划是移动机器人完成作业任务的重要保障[1]。当前，移动机器人的路径规划方法主要有基于模板匹配的路径规划方法、基于人工势场的路径规划方法、基于地图构建的路径规划方法和基于人工智能的路径规划方法等，文献[2]中综述了这些方法的研究进展。尽管相关方法研究已取得了重要成果，但在实际应用中仍存在一定的局限性，多数的路径规划方法通常仅仅追求单项性能指标的最优，例如路径长度最短，所获得的路径难以满足复杂动态环境的需求。考虑到多数作业环境具有较强的动态性、异质性和复杂性等特点，移动机器人的路径规划通常需要考虑多项性能指标，如路径长度、运行时间、路径的安全性、路径的平滑程度、机器人能耗等。研究[3]表明，路径规划所涉及的多数指标之间是相互冲突的，采用单一的目标函数难以充分描述路径特性，有必要基于多个目标函数分别表达且同时优化。已有的多目标路径优化方案可以分为2类：一类是基于先验知识的优化决策，比如加权求和法[4]、加权乘积法[5]和目标规划法[6]等。通常这类方法规划出的最优路径直接取决于各目标函数权值的分配，不符合多目标优化问题的本质特征，也不能真实地反映系统运动意图和应用需求。另一类方法是基于后验需求的优化决策，即求得Pareto解集后，根据实际应用需求选择优化解，相关研究取得了良好的应用效果，此类方法主要有多目标遗传算法[7]、多目标模拟退火算法[8]、多目标混合蛙跳算法[9]、带有精英策略的非支配排序遗传算法[10]以及多目标粒子群算法[11-12]等。

萤火虫算法[13]通过模拟萤火虫个体的发光机制实现信息共享，亮度大的个体吸引亮度小的个体向它移动，进一步引导整个种群持续不断地向更好的区域移动，从而有效地实现寻优过程。该算法中需要调整的参数少，在全局寻优能力和收敛性上展现出较高的效率和稳定性，已广泛应用于求解旅行商问题[14]、装配序列规划[15]、无人战斗机导航[16]、求解置换流水线[17]、地面自主车辆导航[18]以及机器人路径规划[19-20]等方面。

在单目标萤火虫进化算法中，可依据目标函数值描述萤火虫个体的发光强度，亮度值的大小只表征个体所代表解的优劣。由于原始的萤火虫算法只能用于单目标求解问题，无法同时优化多个相互冲突的目标函数，因此，迫切需要设计一种面向多目标同时优化的萤火虫进化算法。为此，需要解决2个问题，一是如何描述、评价萤火虫个体的发光强度，二是如何保留、更新优化过程中的非支配解集。本文中针对萤火虫算法应用过程中的2个问题进行了改进，以适应多目标同时优化，即：基于目标函数多元向量综合计算萤火虫个体的发光强度，将Pareto支配关系引入种群个体亮度的评价过程，借助支配关系评价种群个体的优劣程度；建立精英库保留迭代过程中Pareto非支配解，设计萤火虫个体的进化策略与更新机制，并采用自适应网格划分策略维持非支配解集的分布性，删除连续迭代多次仍受支配的个体，适时增加新生个体，保持种群的多样性，最终通过仿真实验验证改进算法的有效性。

1 环境建模与问题描述

1.1 环境建模

环境建模是移动机器人执行各类作业任务的前提。目前，机器人作业环境信息的描述方式主要有几何地图、拓扑地图、栅格地图、三维(3D)地图和混合地图等[2]。栅格地图将机器人的作业空间划分为一系列大小相同的栅格区域，若某栅格区域内包含障碍物，采用1%～100%的数值表达该栅格被障碍物占据的程度，称该数值为占有概率，所对应栅格称为障碍栅格，否则称为自由栅格。该方法通过设置栅格的占有概率属性来表达环境信息，具有较强的可计算性；但是，在实际应用中，由于机器人本体占据一定的物理空间，比如半径为20～30 cm，若栅格分辨率较高(10 cm×10 cm(长度×宽度，以下同))，为了保证机器人平台的安全性，靠近墙体或硬质障碍物附近的若干层栅格区域不建议使用[2]。

针对上述问题，有必要将障碍区域中的外围障碍栅格向外扩展，并设置扩展栅格的梯度占有概率，以增强规划路径的实用性。约定如下：在栅格地图中，若某栅格g为障碍栅格，且其周围存在自由栅格，称g为边沿栅格，因此，边沿栅格向外扩展已成为提高机器人运动安全性的有效方式[2]。表1所示为原始栅格地图中边沿栅格的扩展方式及扩展栅格梯度占有概率设定的具体实现。若边沿栅格g的占有概率pg大于80%，以栅格g为中心向外扩展3层，由内至外，扩展栅格的占有概率依次设定为0.9pg、0.7pg、0.3pg；若边沿栅格g的占有概率pg介于35%和80%之间，向外扩展2层，扩展栅格的占有概率依次设定为0.8pg、0.4pg；若边沿栅格g的占有概率pg介于10%和35%之间，向外扩展1层，扩展栅格的占有概率设定为0.5pg；占有概率低于10%的边沿栅格，不作扩展。对于某扩展栅格ge来说，若其扩展后的占有概率大于原占有概率，则采用扩展后的占有概率替换原占有概率；否则维持原占有概率不变。图1所示为某作业环境向栅格地图转换并进行障碍扩展的示例效果。

表1 原始栅格地图中边沿栅格g的扩展方式及扩展栅格梯度占有概率设定的具体实现

(a)移动机器人某作业环境地图

1.2 问题描述

多目标优化问题可描述为[3]

minF(X)=(f1(X),f2(X), …,fn(X))

s.t.gi(X)≤0,i=1, 2, …,k,

hj(X)=0,j=1, 2, …,l,

(1)

式中：X=(xvar1,xvar2,…,xvarm)为决策向量，m为决策变量的个数；n为目标函数的个数；F(X)=(f1(X),f2(X), …,fn(X))为目标向量；gi(X)≤0,i=1, 2,…,k为不等式约束；hj(X)=0,j=1, 2,…,l为等式约束。

在多目标优化中，很难找到使所有目标函数均达到最优的解，通常需要协调各目标函数的取值，这样的解会有多个，并有如下相关概念。

1)Pareto支配。若决策空间中存在解Xa和Xb，且满足[3]

(2)

则称解XaPareto支配Xb。

2)Pareto最优解[3]。当且仅当不存在X∈Ω(Ω为决策空间)使得XPareto支配X*成立时，X*称为Pareto最优解。

3)Pareto最优解集[3]。多目标优化问题中，所有的Pareto最优解构成的集合称为该问题的Pareto最优解集。

1.2.1 路径编码

栅格法将机器人的作业环境划分成若干大小相等的栅格，则一条可达性路径即可表达为从起始点到目标点之间一系列离散的可通行栅格，它们均具有横坐标和列坐标，因此，机器人的规划路径可编码为一个可变长度有序点集。表2所示为规划路径的编码结构。

表2 规划路径的编码结构

1.2.2 优化目标

在路径搜索与优化的过程中，本文中以路径长度、路径安全性、路径平滑度为目标，旨在通过改进算法搜索获得路径更短、安全性更好、更为平滑可达性路径，各优化目标的数学模型如下。

1)路径长度f1(L)。路径编码将一条可达路径描述为若干有序点组成的集合，即Sp=(Ps,…,Pi,…,Pt)，其中Ps为起始点，Pt为目标点，则路径长度可表达为该有序点集组成的各路径线段之和，即

(3)

式中d(Pi,Pi+1)为有序点Pi与Pi+1之间的欧式距离。

2)路径安全性f2(S)。所规划路径上是否存在障碍物决定了机器人在此路径上运动的安全性，因此，统计路径所穿过栅格的占有概率可用来描述路径的安全性，即

(4)

式中p(Pi,Pi+1)为路径段Pi—Pi+1所穿过栅格的占有概率之和。

3)路径平滑度f3(α)。为了计算路径的弯曲程度，对于路径上某有序点Pi=(xi,yi)而言，计算交汇于该点的2条路径段之间的夹角αi，若夹角值等于π可视为完全平滑。本文中采用2个路径段之间的夹角衡量路径的平滑程度，参照最小化目标函数，故路径的平滑度可表达为

(5)

式中(xi,yi)为路径上编号为i的节点Pi所对应的坐标。

综上，多目标路径规划的数学模型可描述为

minF(Sp)=(f1(L),f2(S),f3(α))。

(6)

该式的约束条件为优化路径上任一路径段均不可穿越占有概率为100%的障碍栅格。

2 面向多目标优化的改进萤火虫算法

根据多目标优化和单目标求解问题的本质区别，本文中对萤火虫算法进行了改进，主要体现在以下2个方面：一是构建了萤火虫亮度描述与评价机制，基于目标函数多元向量综合计算萤火虫个体的发光强度，借助Pareto支配关系评价种群个体的优劣程度。同时优化路径长度、路径安全性和路径平滑度3个目标，其发光强度可用三元组(f1(L)，f2(S)，f3(α))表达，其中f1(L)、f2(S)、f3(α)分别为可达性路径的路径长度函数、路径安全性函数以及路径平滑度函数。二是设计了Pareto非支配解的保留与更新机制，并给出了路径节点的3种优化策略，即节点删除、节点替换和节点新增。图2所示为面向多目标优化求解的改进萤火虫算法流程，主要包括参数初始化、随机产生种群个体、优化计算等阶段。在初始化阶段，对种群规模、算法迭代次数、精英库与进化库容量、自适应窗格大小、连续迭代后仍受支配的最大次数阈值等参数进行初始化。随机产生萤火虫个体，并计算其发光强度。利用Pareto支配关系将种群个体向精英库和进化库分流，非支配个体随机进化，受支配个体趋向支配个体进化。优化计算阶段，遍历比较进化库个体与精英库个体之间的支配关系，利用非支配个体引导受支配个体趋向进化。基于自适应网格策略适时对精英库中群体密度较大个体进行替换，维持非支配解集分布性。删除连续迭代多次仍受支配的个体，并适时增加新生个体。

图2 面向多目标优化求解的改进萤火虫算法流程图

2.1 路径初始化

在种群个体初始化阶段，为了生成可达性初始路径，本文中设计了用于产生路径节点的环形选择窗口。图3为初始路径生成过程示意图。首先，以路径起始点A为中心，趋向目标点主方向，在环形选择窗口内参照一定概率分布产生节点Bi，其中新生节点Bi处于自由栅格。式(7)给出了某新生节点Zi偏离目标点主方向θ角度的概率分布。其次，以Bi为中心，趋向目标点方向，基于上述概率分布产生节点Ci，并依次产生路径上其他节点，直至目标点可直达或被环形选择窗口覆盖。

A为起始点；E为目标点；Bi为随机生成节点，i=1, 2,…,5；A—Bi—C—D—E为某条生成路径。

(7)

2.2 路径优化策略

路径编码将机器人运动路径描述成为一个可变长度有序点集，则路径优化的核心在于路径节点的增添、删除和替换策略。图4所示为多目标路径规划中路径节点的优化策略。图4(a)所示A—B—C—D—E为某条从起始点到目标点的初始化路径，其中B、C、D为路径的中间节点。为了缩短路径长度，可选择性删除若干中间节点。图4(b)所示为节点删除策略的一种实现，若删除节点B，且节点A、C之间可直达，可缩短路径长度；但是，由于路径段A—C更靠近障碍区域，因此路径安全性可能变差。若删除节点D，路径段C—E穿过不可逾越障碍区域，类似操作是非法的。为了增强路径的平滑性，可实施节点替换策略。图4(c)所示为替换策略的一种实现，若替换中间节点D，在路径段C—D和D—E之间分别随机新增节点F与G，构成路径段C—F—E和C—G—E，并计算二者的可通行性。若前者可通行，而后者穿过不可逾越障碍区域，取节点F替换节点D，可增大2条相邻路径段之间的夹角，从而增强路径平滑性，但路径的安全性可能变差。为了增加路径的安全性，图4(d)所示为节点增添策略的一种实现，即选择占有概率较大路径段，如路径段C—D，在其两侧随机新增节点H和I，分别构成路径段C—H—D和C—I—D，并计算二者的可通行性。若前者可通行，而后者穿过不可逾越障碍区域，增添节点H，新路径C—H—D可增强路径安全性，但路径长度变长，路径平滑性的变化需综合计算。

A为起始点；E为目标点；A—B—C—D—E为某条初始路径；F、G、H、I均为随机新增节点。

2.3 Pareto非支配解更新机制

算法经过初次迭代后，不受任意萤火虫支配的个体分流至精英库，其余受支配个体归类于进化库，因此，在之后的每次迭代中该算法都会得到一组Pareto非支配解集。研究[10]表明：在多目标优化问题中，合理利用迭代过程中获得的非支配解集可有效改善多目标优化的性能。本文中对迭代过程中非支配解集进行了3个方面的处理：一是采用非支配个体引导受支配个体进化。以受支配子目标为切入点，分别独立实施节点删除、节点替换和节点新增等路径优化策略，加速个体的进化过程。二是对精英库和进化库实施协同更新。基于Pareto支配关系，比较精英库中的每个个体Fe与其他成员之间的支配关系，若Fe受某一成员支配，则将个体Fe移出精英库，加入进化库。当进化库中的某萤火虫个体Fc不受支配且不支配精英库中的任意成员时，则将Fc加入精英库中；当萤火虫Fc不受精英库中的任意成员支配，且Fc支配精英库中的某个或者若干成员时，则将Fc替换精英库中受支配的成员；当萤火虫Fc受精英库中的某个或者若干成员支配时，则该个体Fc向精英库中的支配成员进化；当萤火虫Fc连续迭代多次后，仍受精英库中的某个或者若干成员支配时，则将该个体Fc丢弃，并随机产生新的萤火虫个体加入进化库。三是为了维护精英库中萤火虫种群均匀分布性，同时考虑到群体进化的动态性和运算的复杂程度，基于自适应网格策略计算个体密度[21]，删除若干密度较大的非支配解。首先，统计当前精英库中成员个数是否已达预设的规模，若未达上限，则将非支配个体直接加入精英库中；若已达上限，将非支配解集所在的搜索空间划分为若干立体网格，计算网格内的种群密度，随机删除密度较大的个体。在每次迭代中，根据当前个体分布情况自适应调整网格边界。

3 仿真结果

为了验证本文中所提出的算法的有效性，在15.3 m×8.9 m(长度×宽度)的作业环境内进行实验，环境中分布着大小不一、形状各异的若干障碍物，如图1所示。将作业环境转化为栅格地图，并进行边沿栅格扩展，其中栅格分辨率为10 cm×10 cm。鉴于仿真场景的非规则性，需兼顾路径起始点和目标点多样性分布。不同方向上测试路径的参数配置见表3，其中坐标原点位于地图左上角，坐标单位为cm，路径R1沿地图主对角线方向，R2沿地图副对角线方向，路径R3为水平方向路径，R4为竖直方向路径。

表3 不同方向上测试路径的参数配置

改进萤火虫多目标路径规划算法的初始参数设置见表4。同时，对比基于文献[10]中所述的非支配排序遗传算法(NSGA-II)，同时优化路径长度、路径安全性和路径平滑性3项指标，其中种群大小、迭代次数均相同，同等条件下独立运行30次，并分析实验结果，其中2种方法的对比实验及其结果均是基于MATLAB R2014b软件完成的。

表4 面向多目标同时优化的改进萤火虫算法参数配置

为了直观展示所求路径Pareto最优解集的优劣，给出在路径R1、R2、R3、R4上某次实验中基于面向多目标同时优化的改进萤火虫算法(MO-IFA)和NSGA-II所得Pareto最优解集的空间分布情况，如图5—8所示，其中，黄色实心点为路径R1、R2、R3、R4的理想路径解。由图中可以看出，相比于NSGA-II，MO-IFA所得解集的空间分布距离各对应理想点更近，从分布性的角度来说，MO-IFA在3项指标上拥有一定优势。从2种方法所得解集在2项指标上的分布状况来看，就单独的1项或2项指标而言，确实存在NSGA-II所得部分解的指标优于MO-IFA，甚至存在NSGA-II所得少数路径解支配MO-IFA所得解集的若干个体，但是后续实验结果(解集覆盖率指标)表明：MO-IFA所得解集受NSGA-II所得解集支配比例较低；反之，MO-IFA所得解集Pareto支配NSGA-II所得解集比例较高。图9—12所示为MO-IFA与NSGA-II在路径R1、R2、R3、R4上分别求得距离理想参考点最近的路径解。

黄色实心点为路径R1的理想路径解。

黄色实心点为路径R2的理想路径解。

黄色实心点为路径R3的理想路径解。

黄色实心点为路径R4的理想路径解。

图9 面向多目标同时优化的改进萤火虫算法(MO-IFA)、非支配排序遗传算法(NSGA-II)在路径R1上所求得距离理想点最近的路径解比较

图10 面向多目标同时优化的改进萤火虫算法(MO-IFA)、非支配排序遗传算法(NSGA-II)在路径R2上所求得距离理想点最近的路径解比较

图11 面向多目标同时优化的改进萤火虫算法(MO-IFA)、非支配排序遗传算法(NSGA-II)在路径R3上所求得距离理想点最近的路径解比较

图12 面向多目标同时优化的改进萤火虫算法(MO-IFA)、非支配排序遗传算法(NSGA-II)在路径R4上所求得距离理想点最近的路径解比较

为了定量衡量2种方法所得Pareto解集的优越程度，采用超立方体Hv指标与解集覆盖率Sc指标计算分析。设M为非支配解集，Z为M中的非支配解，R=(r1,r2,…,rn)为参考点，n为目标函数的个数，则解集M的超立方体Hv定义[10]为

[fn(Z),rn]，

(8)

式中:Hv(M)解集M与参考点R在目标空间中所围成的超立方体的体积，其数值越大，表示该解集越优越；γLeb为解集M的Lebesgue测度；[f1(Z),r1]×[f2(Z),r2]×…×[fn(Z),rn]为被Z支配但不被R支配的所有点围成的超立方体。设M和N为2个非支配解集，Z、Y分别为解集M和N中的非支配解。Sc指标定义[10]为

(9)

由式(9)可见，Sc(M,N)表示解集N被解集M中至少一个解所支配的解占N中解个数的比例，若Sc(M,N)较大，而Sc(N,M)较小，从解集的支配关系上来说，M优于N。

各测试路径R1、R2、R3、R4所对应理想参考点和本文中选取的参考点见表5。以路径R1为例，理想路径为从起始点到目标点直达连线，且该路径不经过任何障碍区域，即(f1(L),f2(S),f3(α))=(dE, 0, 0)，其中dE为起始点与目标点的欧式距离。由于作业环境中不可避免存在障碍物，因此，所得路径的各项指标均劣于或等于理想参考目标。为了计算Hv参数，本文中所选参考点的路径长度为实验所得路径长度最大值的2.2倍，路径安全性为所得路径安全性最大值的3.8倍，路径平滑度为所得路径平滑度最大值的3倍。

表5 不同路径所对应的参考点

图13所示为实验中基于MO-IFA、NSGA-II所得Pareto非支配解集在超体积指标、解集覆盖率指标上的比较。从图13(a)中可以看出，MO-IFA所得非支配解集与选取参考点所围成的超立方体的体积更大(该结果为各目标函数值分别归一化后计算所得)，表明MO-IFA所得非支配解集距离真实的Pareto前沿更近，解集的稳定性更强。从图13(b)中可以看出，相比于NSGA-II，MO-IFA所得解集的覆盖比例更大。以路径R1为例，独立运行30次，MO-IFA所得解集支配NSGA-II所得解集的平均比例为72.9%，而NSGA-II所得解集支配MO-IFA所得解集的平均比例为6.02%。上述2项指标均表明MO-IFA所得Pareto非支配解集更优越。

Ri-MO-IFA为MO-IFA在测试路径Ri上所得结果，Ri-NSGA-II为NSGA-II在测试路径Ri上所得结果, i=1,2,3,4。(a)超体积指标

综上所述，运行一次多目标路径优化算法，机器人可得到若干条可达性路径，它们之间彼此互不支配，均侧重于1个或2个优化目标，平衡了目标之间同时寻优时彼此之间的冲突，为基于目标重要性的路径选择提供了多种方案。

4 结论

针对复杂室内环境下移动机器人的多目标路径规划求解问题，本文中提出一种基于改进萤火虫算法的多目标路径规划方法。利用栅格法构建环境模型，基于Pareto支配关系评价种群个体发光强度，构建精英库保留最优解，设计了解集的更新与进化策略，同时优化路径长度、路径安全性和路径平滑度3个目标，实现了运行一次算法，可得到多条互不支配的可达性路径解。机器人在复杂环境中执行作业任务时，可实时参照传感器感知周围环境信息，决策自身选择偏向哪类目标的最优路径。