基于混沌求偶萤火虫算法的移动机器人路径规划

侯志祥，成威，李凤玲

(长沙理工大学汽车与机械工程学院，湖南长沙410114)

0 前言

移动机器人是集环境感知、动态决策与规划、行为控制与执行等多功能于一体的智能化机器。近年来，随着现代高科技产业的快速发展，移动机器人在工业、农业、医学、生活服务、军事等领域不断地被开发和完善[1]。

路径规划作为移动机器人的核心研究内容，是实现移动机器人自主导航的必要条件[2-3]。路径规划实质是一个优化的问题，优化目标通常为路径长度、时间、能耗、路径平滑度或多个约束条件的加权等。目前，路径规划方法可分为两类[4]：传统经典算法和智能仿生算法。传统经典算法具有实时性好、计算效率高的特点，但路径规划质量较差、使用场景有限，一般被用于实时性较高的动态路径规划，如A*算法、快速探索随机树RRT、人工势场法等[5]。智能仿生算法具有规划结果较优的特点，但算法存在易陷入局部最优、收敛速度慢等问题，一般被用于静态或全局路径规划中，如蚁群算法、麻雀搜索算法、狼群算法、萤火虫算法[6-7]等。

智能仿生算法比传统经典算法具有更广泛的适用场景。国内外学者为了得到更优的规划结果，提出了各种改进的智能仿生算法。如ZHANG等[8]提出一种改进的麻雀搜索算法，该算法采用一种线性路径策略和邻域搜索策略，解决了算法收敛速度慢和精度低的问题，但算法在寻优效率和路径安全上没有明显提升。LIU、LI[9]提出一种改进灰狼优化算法，该算法通过logistic混沌映射和自适应调整策略实现种群搜索与开发能力的平衡，提高算法的优化精度，有效地缩短路径长度，但该算法中并未考虑时间因素。LI等[10]提出一种自适应种群萤火虫算法，该算法采用自适应种群策略，平衡算法在迭代过程中种群与障碍物个数的匹配关系，提高了算法的探索能力和计算效率，但该算法中并未考虑时间稳定性和三维环境。

针对智能仿生算法在机器人路径规划中容易陷入局部最优和搜索精度低问题，本文作者提出一种混沌求偶萤火虫算法(Chaotic Courtship Firefly Algorithm，CCFA)，用于移动机器人路径规划。在标准萤火虫基础上，通过采用Tent映射初始化种群，优化种群分布不均和搜索范围不足的问题；同时，将种群分为雌性和雄性两种种群，利用求偶学习策略使雄性萤火虫向雌性萤火虫学习，提高算法的收敛速度和求解精度；在每次寻优结束后，对最优个体萤火虫进行高斯扰动，引导种群跳出局部极值点；最后，应用混沌求偶萤火虫算法进行移动机器人路径规划仿真，验证算法的可行性和有效性。

1 标准萤火虫算法数学描述

标准萤火虫算法是一种机制简单的智能仿生算法，其特点主要有以下3点[11]：(1)萤火虫之间通过亮度相互吸引，没有性别差异；(2)萤火虫吸引力的大小与它的亮度成正比；(3)萤火虫的亮度或吸引度是由目标函数决定的。

标准萤火虫算法的亮度和吸引度公式分别如式(1)和(2)所示：

(1)

(2)

式中：I和β分别为萤火虫的亮度和吸引度；I0和β0分别为萤火虫初始亮度和初始吸引度；γ为光吸收系数，一般取常数；rij为萤火虫i和萤火虫j的相对距离。

标准萤火虫位置更新公式如式(3)所示：

(3)

式中：t为迭代次数；xi和xj分别表示第i只萤火虫和第j只萤火虫所处的位置；α为步长，取α∈[0，1]；ε为随机数，取ε∈[-0.5，0.5]。

自FA算法被提出以来，研究人员开发了许多改进的FA算法。如ZHANG等[12]提出一种基于遗传算法和萤火虫算法的混合算法，该算法将局部最优的粒子进行交叉变异，解决算法陷入局部最优的问题，有效缩短了路径长度，但该算法计算时间较长。FAN等[13]提出一种基于档案学习的多目标萤火虫算法，该算法将每一代最优粒子保存在外部存档中，通过从外部档案中随机选取一个粒子作为萤火虫的学习对象，提高了算法收敛速度和寻优精度；但该算法应用在路径规划中，路线较为曲折。为了解决标准FA算法存在的寻优精度低、收敛速度慢和易陷入局部最优等问题，本文作者提出一种混沌求偶萤火虫算法。

2 混沌求偶萤火虫算法

2.1 混沌映射策略

标准FA算法中，随机生成的萤火虫初始位置分布不均匀，导致算法寻优不佳、收敛速度较慢。因此，本文作者提出一种混沌映射策略。该策略利用混沌算子具有不重复遍历性、随机性和规律性的特点，使算法保持种群多样性，提高算法全局搜索性能。混沌映射种类较多，并且不同的混沌算子对算法寻优有很大的影响。文献[14]指出Tent映射比常用的Logistic映射具有较优的解。因此，本文作者采用Tent映射初始化种群。Tent映射迭代公式如式(4)所示：

(4)

式中：zt为第t代混沌序列当前值；ρ为控制参数，取ρ=0.5；初始值z0设为(0，1)区间的随机数。当遍历完整个二维空间后，混沌粒子被映射到环境模型搜索空间中，得到第一代萤火虫初始位置，其映射公式如式(5)所示：

(5)

为了避免算法在后期寻优过程中出现停滞、早熟或陷入局部最优的情况[15]，本文作者将每一代全局最优的个体萤火虫进行高斯扰动，引导种群跳出局部极值点。高斯扰动公式如式(6)和式(7)所示：

PGpos=PBpos·(1+Gaussian(δ))

(6)

(7)

2.2 求偶学习策略

为进一步优化混沌策略出现早熟或局部最优的问题，本文作者提出一种求偶学习策略。该策略的萤火虫有性别差异，分为雌性萤火虫和雄性萤火虫。

求偶学习模型如图1所示。A框表示雄性萤火虫，内部机制与标准FA算法相同，通过亮度大小相互吸引。其中蓝圈xi表示当前萤火虫，灰圈xj表示比当前亮度低的萤火虫，绿圈表示比当前亮度高的萤火虫。B框表示雌性萤火虫，内部采用存档机制，对应个体用xk表示。存档机制是将每一代最优个体保存在档案B中。其中，第一代雌性萤火虫种群Np通过混沌映射得到，随后每一次迭代用最优个体萤火虫取代最差雌性个体萤火虫。

图1 求偶学习模型图解

A框中雄性萤火虫位置更新时，假设被选中的萤火虫是绿圈，则当前萤火虫蓝圈xi可直接向绿圈移动。反之被选中的萤火虫是灰圈xj时，则在迭代过程中，由于灰圈xj亮度低于蓝圈xi的亮度，导致当前萤火虫蓝圈xi并没有移动，从而出现信息丢失的情况。因此，为了使雄性萤火虫xi向雌性萤火虫xk学习，通过概率的方式由档案B中的优秀雌性个体红圈xk引导当前雄性萤火虫蓝圈xi移动，进而达到信息利用的目的，提高算法搜索精度和逃逸局部最优的能力。

求偶学习策略主要表现在4个方面：(1)萤火虫之间存在性别差异，分为雌性和雄性；(2)雄性萤火虫通过亮度大小相互吸引。当被选定的雄性萤火虫亮度低于当前雄性萤火虫亮度时，雌性萤火虫将引导雄性萤火虫移动；(3)雌性萤火虫采用存档机制，并通过概率来选择一个优秀雌性个体作为当前雄性萤火虫的学习对象，参与种群进化和更新；(4)雌性和雄性萤火虫的亮度均由目标函数来确定。

求偶学习模型中，雌性个体选择方式尤为重要。首先计算档案B中每只雌性萤火虫的适应度值f(即亮度)，然后根据目标函数的优化目的(求最大值或最小值)来确定是否对每一只雌性萤火虫采取缩放机制。假设适应度值较低的雌性萤火虫是更好的选择，则档案B中每只雌性萤火虫的适应度值转化公式如式(8)所示：

(8)

式中：f(k)为第k只雌性萤火虫的适应度；Sk为第k只雌性萤火虫适应度的倒数；Np为雌性种群数。档案B中的雌性个体按比例变换后，雌性个体的选择概率公式如式(9)所示：

(9)

式中：P(k)表示第k只雌性个体的选择概率。这种概率方法确保适应度低的雌性个体更容易被选择到，也能避免算法陷入局部最优。如果采取索引排序的方式选取最优雌性个体，算法很难实现全局最优。

3 CCFA在移动机器人路径规划中的应用

3.1 环境建模

本文作者采用文献[16]的方法进行环境建模。环境模型如图2所示，设S为起始点、G为目标点。为简化模型设障碍物为圆形障碍物，障碍物用{Ok(oxk,oyk),rk|k=1,2,…,m}表示，其中：(oxk,oyk)为第k个障碍物的圆心坐标；rk为第k个障碍物的半径。

图2 环境模型

3.2 萤火虫编码和距离计算

假设每只萤火虫在解空间中有唯一候选路径，每条路径在平面上有n个主路径点，每个路径点都表示为pi=(xi，yi)。为了使路径平滑，通过三次B样条插值将路径点增加到N(N≫n)个，使路径成为一个离散点的集合。因此，对应每只萤火虫(path)编码公式如式(10)所示：

P={S1，p2(x2，y2)，…，pN-1(xN-1，yN-1)，GN}

(10)

式中：P为一只萤火虫的解；S1、GN分别为路径的起点和终点。

任意两只萤火虫之间的距离rij如式(11)所示：

rij=dis[P(i)，P(j)]

(11)

3.3 适应度函数

适应度函数是评价萤火虫生成路径质量的重要性能指标。针对移动机器的路径规划问题，需要综合考虑路径代价PL和避障代价PCollis来制定适应度函数。路径代价PL由三次B样条曲线拟合出的路径长度决定，如式(12)所示：

(12)

式中：d(pj，pj+1)是两个连续路径点pi和pi+1之间的距离。

避障代价PCollis如式(13)所示：

(13)

式中：mean为每条路径中各散点碰撞量的均值函数；dkj为路径中散点到障碍物中心距离；rk为障碍物的半径；max(1-dkj/rk,0)为障碍k与路径点pj的碰撞程度。只有当dkj

因此，文中总适应度函数如式(14)所示：

f(i)=PL(i)·(1+∂·PCollis(i))

(14)

式中：∂为碰撞系数，取∂=1 000。当路径与障碍物发生碰撞，PCollis≠0，导致适应度f变大而放弃该路径；当路径与障碍物无碰撞时，PCollis=0，适应度f才会变小变优。

3.4 CCFA算法路径规划流程

步骤1，建立环境模型，设置目标函数和路径规划的起点S、终点G；

步骤2，初始化参数γ、β0、α，种群Np，最大迭代次数nmax，主路径点n；

步骤3，采用Tent混沌映射初始化第一代雌雄种群，并由式(14)计算每只萤火虫的适应度f；

步骤4，根据适应度f比较萤火虫的亮度，如果f(j)

步骤5，根据式(6)(7)对全局最优个体进行扰动，引导种群跳出局部极值点；

步骤6，更新雄性种群A和雌性存档B；

步骤7，判断是否到达最大迭代次数，“是”则进入步骤8，“否”则返回步骤4；

步骤8，输出最终结果。

4 仿真验证和分析

为了验证混沌求偶萤火虫算法的有效性和优越性，本文作者对标准萤火虫算法(FA)、混沌求偶萤火虫算法(CCFA)和粒子群算法(PSO)进行30次仿真测试，并比较和分析实验结果。所有实验均在Win10系统、AMD R5-3600x处理器，主频3.8 GHz、MATLAB 2020a仿真平台下进行。

移动机器人起点S和终点G分别设为(0，0)和(100，5)，障碍物参数如表1所示。为简化模型，障碍物设为圆形障碍物。为保证测试的公平性，设CCFA和FA的参数相同。种群Np=30，吸引度β0=1，光吸收系数γ=1，步长α=1。PSO算法参数同文献[16]所述。3种算法统一设置最大迭代次数nmax=100，主路径点n=3。

表1 障碍物参数

3种算法路径规划结果如图3所示，分别为FA算法、CCFA算法、PSO算法的某次寻优结果。可见：3种算法均可以在避障的同时找到一条可行路径，使移动机器人安全到达终点。FA算法和PSO算法在不同程度上陷入局部最优，未能找到最优路径，而CCFA算法能够找到最优路径。

图3 三种算法路径规划结果

适应度迭代结果如图4所示，FA算法、CCFA算法、PSO算法最优适应度值分别为104.828 2、100.525 3、104.664 8 m，可见CCFA算法拥有更优寻优精度，且收敛速度比标准FA算法快。

3种算法30次仿真结果箱型图如图5所示。可见：CCFA算法最优适应度值波动较小；FA算法和PSO算法的最优适应度值波动较大，表明FA算法和PSO算法在求解路径规划问题中容易陷入局部最优，导致寻优结果产生较大的偏差。

为了更直观分析CCFA算法的性能，30次仿真结果统计结果如表2所示，可知：不论路径长度的最优值、均值还是标准差，CCFA算法均优于FA算法和PSO算法。CCFA算法比标准FA、PSO算法在路径均值长度上分别缩短了3.075%和2.428%，体现了CCFA算法在全局搜索能力和逃逸局部最优情况上的优越性和稳定性。

表2 仿真结果统计

5 结论

为提高移动机器人的路径规划效率，本文作者提出一种混沌求偶萤火虫算法。该算法主要有以下特点：(1)利用混沌映射初始化种群，使种群具有较优的初始解，提高算法全局搜索能力；(2)利用求偶学习策略，使雄性萤火虫向雌性萤火虫学习，提高算法搜索精度和逃逸局部最优的能力；(3)对每一代最优个体萤火虫进行高斯扰动，避免算法在迭代过程中出现停滞而陷入局部最优。应用混沌求偶萤火虫算法进行移动机器人路径规划仿真，仿真结果表明：CCFA算法比标准FA、PSO算法在路径长度上分别缩短了3.075%和2.428%，收敛速度比标准FA算法有明显的提升，能够有效地改进移动机器人路径规划效率。文中所提算法的运行时间较长，后续将对算法计算时间进行深入优化。