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

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

1 问题描述

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

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

图1 环境模型

文中采用序号编码和坐标编码相结合的编码方式，用A~K 分别表示10~20。设栅格序号用i表示，则i与其对所对应栅格坐标(x_i，y_i)，的关系如式（1）。

   （1）

编码后的移动机器人环境模型如图2所示。

图2 编码的环境模型

2 改进遗传算法在移动机器人路径规划中的应用

2.1 种群初始化算法的改进

种群初始化最常用的方法为随机法，此方法虽然简便，但产生的初始种群中不可行路径所占比例较多，初始种群质量低。针对此问题，文中采用基于Cost-Gain算法的避障策略产生初始种群。

设定种群数目为M, 个体长度为len，机器人出发点为(x₁，y₁) ，目标点为(x_n，y_n) ，初始种群产生的具体步骤如下：

步骤1：在起点S 和目标点T 之间随机生成n-2 个非障碍栅格，组成一条初始路径。

步骤2：判断路径是否为连续路径。当两个相邻路径点的横坐标与纵坐标之差最大为1 时，则说明路径为连续可行路径，否则需要采用平均值插入法填补间断路径，候补栅格坐标计算如式（2）。

   （2）

若候补栅格为自由栅格，则直接进行插入，否则需要根据基于Cost-Gain 算法在障碍物周围的八个自由栅格中确定候补栅格。

Cost-Gain算法是用效用来表示收益G(x，y)与代价 C(x，y) 之间关系的一种算法 , 它们之间的关系如式(3)。

（3）

用路径点(x_i-1,y_i-1) ， (x_i,y_i) 所组成的路径与路径点(x_i,y_i) ，所组成的路径间的平滑度作为收益函数 G( x，y)，用路径点 (x_i,y_i) 与所组成路径的距离作为代价函数C( x，y )，平滑度越大，路径越短，说明效用越大，栅格被选作候补栅格的优先级越高。

步骤3：保存当前所生成的路径作为初始路径。

步骤4：检查生成的路径数目是否为M，若是，终止初始化，否则重复执行以上步骤。

2.2 适应度函数

适应度值是衡量个体质量好坏的重要指标，个体的适应度值越大，个体保存下来的几率越大。文中采用路径总长度L 和路径平滑度H 构造适应度函数。

路径距离计算公式如式(4)。

   （4）

式中：

d_i为第i 个路径点与第i＋1个路径点之间的距离（m）；L为路径的总长度（m）。

路径平滑度计算如式(5)(6)。

   （5）

   （6）

式中：

H为路径平滑度；

A₁为第 i 个路径点与第 i＋1个路径点的横坐标之差。

B₁为第 i 个路径点与第 i＋1个路径点的纵坐标之差。

A₂为第i＋1个路径点与第i＋2个路径点的横坐标之差。

B₂为第i＋1个路径点与第i＋2个路径点的纵坐标之差。

C_i为第 i段路径与第i＋1段路径的夹角。

第x 条路径的适应度函数如式(7)。

   （7）

式中：

e 为路径长度系数；

c 为路径平滑度系数；

D 为起点与目标点之间的距离（m）。

2.3 选择算子

本文采用轮盘赌对路径进行选择，具体步骤如下：

步骤1：计算每条路径的适应度f_x 。

步骤2：求出第x 条路径的被选择概率p_x ，并得出累计选择概率P_X ，在区间（0,1）生成1 个随机数u，当第一次出现P_X 满足μ ≤ P_X 时，则选择第x 条路径。

步骤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分别为采用改进后遗传算法进行路径规划的仿真图和适应度变化曲线图。

图3 传统遗传算法路径仿真图

图4 改进遗传算法路径仿真图

图5 传统遗传算法适应度曲线图

图6 改进遗传算法适应度曲线图

仿真数据对比如表1。

表1 数据对比表

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

4 结束语

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

参考文献：

[1] 杨博,刘树东,鲁维佳,潘玉恒.改进遗传算法在机器人路径规划中的应用[J].现代制造工程,2022(6):9-16.

[2] 魏彤,龙琛.基于改进遗传算法的移动机器人路径规划[J].北京航空航天大学学报,2020,46(4):703-711.

[3] 李培英.基于改进遗传算法的移动机器人路径规划[J].国外电子测量技术,2022,41(6):38-44.

[4] 石志刚,梅松,邵毅帆,等.基于人工势场法的移动机器人路径规划研究现状与展望[J].中国农机化学报,2021,42(12):182-188.

[5] 胡杰,张华,傅海涛,等.改进人工势场法在移动机器人路径规划中的应用[J].机床与液压,2021,49(3):6-10.

[6] 杨会敏.基于粒子群优化算法的移动机器人路径规划[D].鞍山:辽宁科技大学,2022.

[7] 郭世凯,孙鑫.基于改进粒子群算法的移动机器人路径规划[J].电子测量技术,2019,42(3):54-58.

[8] 宋宇,王志明.基于改进遗传算法的移动机器人路径规划[J].现代电子技术,2019,42(24):172-175.

[9] 焦合军,周万春,李渊博.基于混合遗传算法的机器人路径规划研究[J].中州大学学报,2020,37(6):125-128.

（本文来源于威廉希尔 官网app 杂志2023年8月期）