基于改进变色龙算法的移动机器人避障研究*

季 云，曹 弋

(1.常州信息职业技术学院，常州 213164；2.大连交通大学交通运输工程学院，大连 116028)

0 引言

移动机器人广泛应用于工农业、医药、军事等领域，可以辅助或替代人类工作。机器人还可以提高工作效率，降低成本。目前，机器人技术正逐渐普及并应用在生活的方方面面。避障是机器人导航的重要研究课题，是移动机器人的前提和基础[1-3]。为了保证机器人可以安全躲避障碍物并更快地抵达目标地点，有必要对算法进行更详细的研究。

路径规划算法是避障技术的核心,许多算法用于解决避障问题，也取得了良好的表现。如WEI等[4]针对现行的RRT算法在动态非结构环境下的路径规划中存在一定的局限性，提出了一种以定向节点为目标且融合最大曲率约束优化策略的S-RRT路径规划算法。LI等[5]使用改进的人工势场法，使机器人躲避固定障碍物，以最优路径到达目标，通过改进代价函数和约束使得算法不会陷入局部最小值。其他还有蚁群算法[6]、遗传算法[7]、粒子群算法[8]和萤火虫算法[9]等，这些算法主要是在定义的问题空间中搜索最优解。

变色龙算法(CSA)是一种仿生算法[10]，在数学上模拟并实现了变色龙狩猎的行为步骤，包括搜索食物，眼睛360°旋转追踪食物及使用自身舌头定位并抓住猎物的行为。变色龙算法可以很好的运用在实际问题当中并取得好的表现。SAID等[11]将CSA用于经济负荷调度问题的优化，并与其他算法进行了比较，仿真显示CSA计算结果更优。RIZK等[12]设计了一种改进变色龙群算法，从而提取SOFC模型的可靠和精确参数。

CSA对各类问题具有很强的计算能力和适应力，因此尝试将CSA算法引入移动机器人避障领域，帮助机器人寻得一条可靠的通行路径，从而实现高效作业。同时针对在避障过程中CSA出现的寻路效率慢、易陷入局部最优的问题，提出一种改进的变色龙算法。改进标准CSA中的初始化方法，在迭代阶段引入记忆机制，从而提升算法寻优性能。

1 标准变色龙算法

变色龙算法(CSA)是最新的元启发式算法之一，模仿了变色龙的狩猎行为。狩猎过程主要包括搜寻猎物、视线追踪猎物和捕获猎物。该算法的数学模型和步骤如下：

步骤1：种群初始化。假设初始种群共有n条变色龙，其中种群中的每条变色龙都是使用均匀随机分布在D维搜索空间中创建的。其具体表达式为：

zi=Lj+r(Lj-Uj),∀i∈n,j∈D

(1)

式中，zi为第i个变色龙的初始位置向量；Lj和Uj分别为第j维中搜索空间的下界和上界；r为[0，1]范围内的随机数。

步骤2：搜寻猎物。变色龙觅食过程的移动行为可以描述为：

(2)

μ=γe(-αt/T)β

(3)

式中，T和t分别为最大迭代数和当前迭代数；γ、α和β为用于控制探索和开发能力的常数值。

步骤3：眼睛转动追踪。变色龙通过眼睛的旋转在360°范围内识别猎物。变色龙会根据猎物的位置通过眼睛的旋转和移动来更新它们的位置。具体更新表达式为：

(4)

步骤4：捕获猎物。在此阶段，变色龙通过攻击猎物来完成捕获，当它离猎物较近时，变色龙可以用舌头捕获猎物，离猎物最近的变色龙被称为最优解。而捕捉猎物与变色龙吐出舌头的速度有关，该速度表达式为：

(5)

吐舌过程中变色龙的位置更新为：

(6)

2 改进变色龙算法

2.1 Bernoulli混沌映射初始化

在标准变色龙算法中，变色龙初始种群为均匀随机分布产生。由于混沌过程同时具备遍历性、随机性、非线性等优势，因此与原始的种群初始化方法相比，混沌映射可以提升群体的丰富性，使得解空间更加的均匀，防止算法过早收敛。Bernoulli混沌映射作为一种混沌映射的代表性方法，有着优良的特性，其具体表达式为：

(7)

式中，k=0,1,2,…,n为空间维数，其迭代100 000次时的分布直方图如图1所示。

图1 Bernoulli映射直方图

2.2 邻域搜索策略

为了丰富和回溯搜索空间内的相邻区域，可以在全局最佳变色龙(G)中采用一种新颖的搜索策略，其中从总体中随机选择两个解决方案，并使用适应度确定潜在搜索方向。其具体原理描述如下：

(8)

式中，zr和zl为从种群中随机选择的两只变色龙；C为1～0线性减小的比例因子，目的是控制两变色龙之间的差异。在探索阶段C值较大，而开发阶段C值较小。

2.3 基于经验的交叉及贪婪选择策略

基于经验的交叉策略主要是通过合并变色龙获得的猎物信息和邻域解决方案来保持种群多样性，该交叉策略表示为：

(9)

式中，CR为采用的交叉概率；rand为(0,1)内均匀分布的随机数。在通过式(9)更新后，在两次连续迭代中进行贪婪选择策略以确定存活的或最佳变色龙。贪婪选择策略表达式为：

(10)

2.4 改进变色龙算法流程

本文改进变色龙算法的具体步骤如下：

步骤1：初始化运行环境及变色龙算法各项参数及需要人为设定的参数取值；

步骤2：利用Bernoulli混沌映射初始化变色龙种群，计算得出群体内各个个体的适应度；

步骤3：根据式(3)、式(6)和式(10)更新参数μ、惯性权重及a值；

步骤4：依据式(2)及式(8)搜索猎物；

步骤5：利用式(4)眼睛旋转特征更新变色龙的位置，根据式(5)和式(6)进行猎物的狩猎；

步骤6：利用变色龙的位置初始化记忆矩阵；

步骤7：通过式(8)执行邻域策略，根据式(9)和式(10)进行个体的交叉和选择，并评估新位置且记录全局最佳位置；

步骤8：判断是否达到最大迭代数，如果是，则输出最佳路径，否则转回步骤3。

算法流程图如图2所示。

图2 算法流程图

3 实例仿真及分析

3.1 参数设置

由上述小节可知，变色龙算法中存在许多参数需要人工设置，而这些参数取值一般根据大量的实验仿真获得，选取性能较优时的数值作为仿真时的取值。本文参考了文献[10]中的仿真实例，确定最终参数值，主要的算法参数值及环境设置如表1所示。

表1 参数取值表

3.2 仿真分析

为了验证本文改进算法的避障性能，基于MATLAB2018b平台搭建二维地图静态环境，环境尺寸为100×100，CSA算法改进前后的参数值设置如上节，图中黑色为障碍区域，白色区域可无限制通行。分别对标准变色龙算法、文献[3]算法、改进变色龙算法进行仿真实验。仿真结果如图3～图5所示，各项指标对比如表2所示。

图3 环境1仿真图

表2 指标对比

由图3～图4及表2可知，对比标准CSA算法和文献[3]算法，本文改进的CSA算法规划出的路径距离更短，寻路效率更高。在相对简易的环境1下，具体表现为相比于标准CSA算法和文献[3]算法，本文算法路径长度分别减少约5.6%和3.2%，搜索时间分别缩短约46.8%和18.2%，迭代次数分别减少约51.7%和12.5%。在更为复杂的环境2中，改进CSA算法相比于标准CSA算法和文献[3]算法，其中路径长度分别减少约8.1%和1.4%，搜索时间分别缩短约59.3%和33.9%，迭代次数分别减少约53.2%和29%。在环境3中，改进CSA算法相比于标准CSA算法和文献[3]算法，路径长度分别减少约26.2%和13.5%，搜索时间分别缩短约59.6%和33.3%，迭代次数分别减少约55.9%和31.2%。可以看出，本文改进的CSA算法在各类环境下有着良好的表现，优化效果明显，在保证安全性的前提下能够满足移动机器人的避障需求。

图4 环境2仿真图图5 环境3仿真图

4 实物实验

为了验证CSA算法实际性能，利用REVV-B22型履带式移动机器人进行实物实验，如图6所示。此类机器人既能够用于研究路径规划算法实验，还可用于计算机视觉、环境搭建等课题的研究。实物实验平台为ROS系统。

图6 型机器人图7 实验环境

如图7所示为实地场景，实验区域为矩形划线部分。图中右下角为起始位置，左上角为目标点，在环境中设置若干障碍物，参数设置保持与上节一致，使用改进的CSA算法进行实验，实验结果如图8和图9所示。

图8 实际环境1路径图 图9 实际环境2路径图

由以上两图可以看出，在实际的场地中，改进的CSA算法可以帮助移动机器人快速安全的到达目的地。验证了本文改进CSA算法的可行性及良好的性能。

5 结束语

针对移动机器人的避障问题，本文提出了一种改进的变色龙算法。在变色龙种群初始化阶段，采用Bernoulli混沌映射使得个体分布更加均匀，从而丰富了群体的多样性。同时，在迭代过程中引入邻域搜索策略、基于经验的交叉策略和贪婪选择策略。在3种环境下的仿真结果表明，本文改进的变色龙算法较对比的其他算法，在路径长度、搜索时间、迭代次数等方面有不同程度上的提升，能够帮助机器人在各种不同的环境下进行避障，并且基于实物实验验证了改进算法的有效性。