基于混合混沌序列与遗传算法的排爆机器人路径规划

殷新凯 茅健 周玉凤 陈晓平

摘  要： 描绘了排爆机器人路径规划问题，提出了混合混沌序列与遗传算法的排爆机器人路径规划算法。针对遗传算法易于陷入局部收敛，在寻优过程中易于出现抖振，算法收敛精度不高等问题，在遗传算法中引入Logistic混沌序列，生成与机器人路径选择更加匹配的优化算法。运用MATLAB进行算法仿真，分析比较经典遗传算法和优化后的算法。仿真结果显示，算法优化后机器人行走路径更加合理，算法的收敛精度提高。

关键词： 排爆机器人; 遗传算法; Logistic混沌序列; 路径规划

中图分类号：TP242.3          文献标志码：A     文章编号：1006-8228（2019）07-05-04

Abstract： This paper describes the path planning problem of explosive disposal（EOD） robot， and proposes the path planning algorithm with hybrid chaotic sequence and genetic algorithm. Aiming at the problem that genetic algorithm is easy to fall into local convergence， it is prone to chattering in the optimization process， and the convergence accuracy of the algorithm is not high. Logistic chaotic sequences are introduced into the genetic algorithm to generate an optimized algorithm which is more suitable for robot path selection. MATLAB is used to simulate the algorithm， analyze and compare the classical genetic algorithm and the optimized algorithm， the simulation results show that the walking path of the robot with optimized algorithm is more reasonable and the convergence accuracy of the algorithm is improved.

Key words： explosive disposal robot; genetic algorithm; Logistic chaotic sequence; path planning

0 引言

隨着机器人技术的发展，以排爆为目标的特种机器人的应用日益广泛。排爆机器人大大保护了排爆人员的安全，减少了排爆工作的危险程度。在排爆机器人从远程控制到智能化的过程中，排爆机器人的路径规划是排爆机器人系统设计的重要问题之一。路径规划是指空间内，机器人躲避障碍物，完成指定任务的合理路径的选择（合理一般是指时间最少或者能量损耗最小）[1]。因为工作环境的限制，要求排爆机器人能实现智能化路径规划，高效安全地完成自主避障路径规划的任务。

针对多机器人路径规划问题，孙树栋等采用链接图法标识多机器人，简化了机器人的工作环境，同时在遗传算法基础上引入适应度值调整矩阵，对适应度函数进行合理优化，实现对多机器人运动路径的优化调整[2]。李庆中等将遗传算法初始二维编码问题简化为一维编码问题，针对传统算法中适应度函数评价标准过于复杂，简化了评价指标，优化后的遗传算法具有良好的动态避障功能[3]。陈曦等以具有精英保留的免疫遗传算法和栅格法为基础，引入删除和插入算子，有效地优化了算法精度[4]。Castillo等把长度和困难程度归为对机器人路径评价的标准，并在传统遗传算法基础上扩展成多个目标的遗传算法，完成对两种算法的性能测量和模拟结果[5]。Cai等采用新型协调进化自适应遗传算法，提出了一种新的固定长度十进制编码机制，同时讨论了多机器人系统的路径规划，验证了算法的鲁棒性[6]。

本文提出了混合Logistic混沌序列与遗传算法的排爆机器人路径规划算法，在遗传算法的交叉、变异操作中引入Logistic混沌序列，减少算法在寻优过程中出现的抖振，提高算法收敛精度。

1 算法介绍

1.1 经典遗传算法

遗传算法是一种基于自然选择原理和遗传机制的搜索算法，它通过模拟自然界生物的进化衍变，从而在人工系统中实现指定目标的优化过程[7]。

遗传算法是移动机器人路径规划过程中使用较广泛的一种算法。与其他常用算法如蚁群算法、粒子群算法和模拟退火算法相比较，遗传算法优点在易于找到最优解，处理大数据上效率更高，缺点在于容易局部收敛和早熟的情况，同时还会出现寻优抖振问题。

1.2 Logistic混沌序列

混沌是非线性科学的重要概念，它是确定性系统的一种类随机现象[8]。混沌这一概念，应用的最为广泛的定义为Li-Yorke定义。具体的定义为：闭区间I上的连续自映射f（x）如果满足以下三个条件，那么这个映射即为混沌的[9]。

⑴ f（x）的周期没有上界;

⑵ 闭区间I上存在不可数子集S，S中无周期点;

⑶ ，有，其中，表示n重函数，Per（f）是f（x）的周期点的集合。

在以上定义的基础上，一个混沌系统应该具有三大性质：一是存在所有阶的周期轨道;二是存在一个不可数的集合，该集合不存在渐进周期轨道;三是混沌轨道高度不稳定[9]。混沌系统存在着许多典型的混沌映射，其中，Logistic混沌序列是其中一种具有代表性的混沌映射。通过Logistic混沌序列描述种群的变化过程，其数学形式非常简单但却是具有重要意义的一维非线性迭代方程，其定义为：

其中，;分支参数，当时序列进入混沌状态，迭代产生的序列值处于一种类随机分布的状态，由不同的初始x1所生成的序列具有随机性强的特点，且对初始值十分敏感[10-11]。

2 算法设计

遗传算法的特点是：对于非线性问题，在大规模参数与解下，能够迅速地找出局部最优解。基本遗传算子当中的交叉和变异是遗传算法实现上述功能的关键。为了保证算法收敛精度，削弱寻优过程中出现的抖振问题，本文对遗传算法优化，首先将交叉操作独立于选择、变异两大算子，然后在交叉操作中引入Logistic混沌序列，成功地将混沌序列与遗传算法联系在一起，再利用混沌序列随机性强的特点，确定交叉点，实现交叉操作，从而实现算法的优化设计。依据此设计思路，机器人路径规划主要分为以下几个步骤。

⑴ 实例设计

在长宽已知的平面上放置机器人、目标物（根据要求将上述分别放在平面上两个对角落）。同时在两者的直线路径上放置不同形状大小的障碍物，如图1所示。

⑵ 路径构造

将整个平面进行分块命名，并且把各块的边界线上的中点找出连接，设为各区域的最短路径。将出发点与目标位置之间所有可能经过的区域的最短路径一一相连，可得到整体的最短路径。如图2所示。

⑶ 编码设计

采用十进制的一维编码方法，用随机数列作为染色体，其中每一个随机序列都对应著各区域最短路径。编码i代表对应区域代号。

⑷ 种群产生

初始种群，即为各区域最短距离的组合，所有从出发点到目标位置的可能的总和。

⑸ 目标函数

目标函数为每条路径的优劣程度。本文中，适应度函数就是目标函数。适应度函数的评价指标是遗传算法的重要组成部分。与传统遗传算法不同的是，对于排爆机器人适应度评价指标指的是机器人行走的距离和时间长短。排爆式机器人行走距离和时间主要考虑机器人行走时拐角的数量和拐角大小，当拐角数越多，拐角越大时，机器人行走的时间也会随之增加，因此，适应度函数要求机器人行走距离和行走时间尽可能地减少。因此，适应度函数确定为：

3 仿真分析

运用MATLAB对优化后的算法进行仿真，并分析结果。

图4分别为使用遗传算法和优化后的遗传算法下机器人行走路径。通过两者对比，可以发现在使用改进后的算法后，机器人行走路径更加平缓，行走距离减少。仿真实验表明，优化后的算法能使排爆机器人更快找到最短路径。

图5为在优化遗传算法与经典遗传算法两种算法下，算法迭代次数与排爆机器人最短距离的关系图。从图5可以看出，改进后的算法，在初期，降低了算法有效解的范围，减少了算法的搜索时间，在后期，减少机器人的最短距离。本文提出的算法要优于传统算法。

4 结束语

本文针对传统遗传算法在解决排爆机器人路径规划问题中，收敛精度不高等问题，提出了将Logistic混沌序列引入到遗传算法中，实现对遗传算法的优化改进。该算法能够有效地实现排爆机器人路径规划，该算法仍有继续优化的空间。

参考文献（References）：

[1] 王仲民.移动机器人路径规划与轨迹跟踪[M].兵器工业出版社，2008.

[2] 孙树栋，林茂.基于遗传算法的多移动机器人协调路径规划[J].自动化学报，2000.5：672-676

[3] 李庆中，顾伟康，叶秀清.基于遗传算法的移动机器人动态避障路径规划方法[J].模式识别与人工智能，2002.15（2）：161-166

[4] 陈曦，谭冠政，江斌.基于免疫遗传算法的移动机器人实时最优路径规划[J].中南大学学报（自然科学版），2008.3：577-583

[5] Castillo O， Trujillo L， Melin P. Multiple Objective GeneticAlgorithms for Path-planning Optimization in Autonomous Mobile Robots[J]. Soft Computing，2007.11（3）：269-279

[6] Cai Z， Peng Z. Cooperative Coevolutionary AdaptiveGenetic Algorithm in Path Planning of Cooperative Multi-Mobile Robot Systems[J]. Journal of Intelligent and Robotic Systems：Theory and Applications，2002.33（1）：61-71

[7] 司守奎，孙玺菁.数学建模算法与应用[M].国防工业出版社，2017.

[8] 江六林.基于混沌映射和DNA编码的图像加密技术的研究与实现[D].南京邮电大学，2016.

[9] 刘金波.基于DSP的混沌图像加密系统的实现[D].大连理工大学，2008.

[10] 汤任君.Logistic混沌序列和DES算法的图像加密方法[J].计算机应用，2017.37（1）：89-92

[11] 刘睿.基于改进Logistic混沌映射的图像自适应加密算法[J].计算机与现代化，2016.7：13-17，23

[12] 王洲，张毅，杨锐敏.基于遗传算法的移动机器人路径规划[J].微计算机信息，2008.24（26）：187-189

[13] 王枫红，邓志燕，陈炽坤.基于传统遗传算法的改进排爆机器人路径规划研究[J].图学学报，2012.33（3）：41-45