基于改进遗传算法的移动机器人路径规划研究

吴梅花

关键词：移动机器人；改进遗传算法；Cost-Gain算法；路径规划；MATLAB

目前，移动机器人技术已在各领域中得到广泛应用，比如送餐机器人、导购机器人、医疗机器人和伴护机器人等，移动机器人的出现不仅节省了成本，也提高了人们的生活质量。路径规划的方法有很多，其中应用较广泛的有遗传算法[1-3]、人工势场法[4-5] 和粒子群法[6-7] 等。目前，前人已经针对相关算法提出各种改进策略，效果比较显著。在采用遗传算法进行路径规划时，有的学者提出采用RRT 算法产生初始路径，并引入一种新的插入算子[8]，通过实验证明了所提算法是有效的。另外针对在路径规划过程中收敛速度慢的问题，有的学者提出首先采用A* 算法产生初始种群，然后结合遗传算法进行路径优化[9]，也取得了较好的效果。但目前在采用遗传算法进行路径规划时仍存在较多问题，本文主要针对采用随机法产生初始种群时不可行路径所占比重较大的问题，提出基于Cost-Gain 算法的避障策略，然后分别对传统遗传算法和改进遗传算法在MATLAB 仿真平台上进行实验，结果证明了所提算法是有效的。

1 问题描述

移动机器人在进行路径规划时首先需要了解周围的环境。文中假设机器人的工作环境为二维空间，工作空间大小为20×20。在直角坐标系中，X 轴为横轴，Y 轴为纵轴，采用栅格法建立工作环境模型。考虑到障碍物的不规则性和机器人的外形，为提高移动机器人工作时的安全可靠性，将环境模型中静态障碍物的四周分别按照机器人半径的长度进行扩展，当障碍物未占满1 个栅格时按照1 個完整栅格进行填充。

移动机器人工作环境模型如图1 所示，其中黑色部分表示工作环境中的静态障碍物，空白栅格为可行区，S 所在的栅格为机器人的起点，T 所在的栅格为机器人的目标点，在整个运行过程中将机器人看作质点。

步骤3：重复步骤2，直到满足个体数达到设定的种群数目为止。

2.4 交叉算子

为避免进化过程中局部收敛问题的产生，需要对个体进行交叉操作。首先在种群中随机选择两个个体进行单点交叉，然后将交叉操作后的各路径点的x 坐标和y坐标进行升序排列，重新生成一条新路径。检查新路径是否为可行路径，否则，重新对路径进行交叉操作。

2.5 变异算子

文中选用相邻点替代法进行变异操作。首先随机选择除机器人起始点和终点外的一点作为变异点，然后随机在其相邻的八个栅格中选择一个栅格替代该点，将变异后各路径点的x 坐标和y 坐标进行升序排列，重新生成一条新路径。检查新路径是否为可行路径，否则，重新对路径进行变异操作。

2.6 终止条件

当满足提前设定好的进化代数M时终止遗传操作。

3 仿真实验

为验证文中所提算法的有效性，在MATLAB 仿真平台上分别对传统遗传算法和改进遗传算法进行实验。参数设置如下：种群的个体数目M = 800，个体长度len = 10，进化代数G = 100，仿真结果分别如图3 至图6 所示。

图3 和图5 分别为采用传统遗传算法进行路径规划的仿真图和适应度变化曲线图，图4 和图6 分别为采用改进后遗传算法进行路径规划的仿真图和适应度变化曲线图。

仿真数据对比如表1。

由表1 可以看出，采用改进后的遗传算法进行路径规划时，规划出的路径最优适应度值更大，长度更短，收敛速度更快，证明了所提算法是有效的。

4 结束语

文中主要针对采用传统遗传算法进行路径规划时随机产生初始种群中不可行路径所占比重较大的问题提出基于Cost-Gain 算法的避障策略，从仿真结果来看，采用改进遗传算法规划出的路径长度更短，收敛速度更快，充分证明了算法的有效性。