基于混合算法的移动机器人路径规划研究❋

杨 勇

（西安航空学院，西安710077）

基于混合算法的移动机器人路径规划研究❋

杨 勇

（西安航空学院，西安710077）

路径规划技术是移动机器人导航技术的重要组成部分。针对静态已知环境的移动机器人进行路径规划，结合栅格法和遗传算法，并对传统的遗传算法进行改进，建立两种不同的环境，通过仿真实验显示其改进后的优越性。

移动机器人；路径规划；栅格法；遗传算法

1 引 言

路径规划技术是移动机器人导航技术的重要组成部分，也是当下研究的重要课题之一。常用的路径规划方法有可视图法、栅格法、神经网络法和遗传算法等，并且各有利弊［1］。将栅格法和遗传算法进行结合，并对遗传算法进行改进，来研究移动机器人处于静态环境下二维平面空间的路径规划。

2 栅格法建立环境信息

设计了两种不同环境，进行仿真对比，如图1所示。

图1 环境地图

3 遗传算法

遗传算法框图如图2所示。

3.1 染色体表示

用栅格序号表示一条染色体，采用基于栅格序号的、不定长十进制编码机制，以提高算法效率和灵活性［2］。

3.2 适应度函数

适应度函数衡量有两个标准：躲避障碍物和行进路径最短［3］。设计适应度函数如下：

图2 遗传算法框图

3.3 遗传操作

使用了复制、交叉、变异、插入、优化这五种遗传操作算子。

1）复制算子：采用轮盘赌（roulette wheel）方式，对种群进行选择，个体选择概率计算如下：

2）交叉算子：通过引入自适应交叉概率来对种群的染色体交叉进行调节。对于高于种群平均适应值的个体，采取较低的交叉概率；而低于平均值的个体则交叉概率的取值较高［4］。具体计算方法如下：

设种群中个体数目为s，个体的交叉概率为：

3）变异算子：变异概率通常取值很小，一般取0.0001～0.1。常用的有均匀性变异、非一致性变异和自适应变异这三种方法。

4）插入算子：执行变异操作可能产生间断路径，因此提出一种插入算子，使路径出现间断时，通过使用自由栅格的办法使其转变成连续路径。首先通过以下办法判断路径是否连续：

其中，xk，yk，xk＋1，yk＋1分别为该栅格对应的直角坐标；max表示取最大值；abs表示取绝对值操作。当D＝1时，则该路径为连续路径，否则为间断路径。当路径间断时，按照下式计算：

若pk为自由栅格，可直接执行插入算子；若pk存在障碍物，则需选择一个与其距离最近的自由栅格，作为替代插入点。如果没有新的替代插入点，则舍去该个体，进行新的插入计算。

5）优化算子：进行机器人路径规划的时候，可能在遗传操作过程中会出现子代中最优个体的适应度低于父代中最优个体适应度的情况［5］。为了防止丢失优良的父代个体，采用了保留最优个体的方法，即将父代和子代种群中个体适应度函数值进行比较，然后将最优个体保存的办法。

3.4 遗传操作的改进

为了防止遗传算法过程中出现早熟现象而陷入局部最优解，提出了一种改进方法－双层变异法，具体如下：

1）将父代和子代种群进行融合，形成新的种群［6］。

2）设置了两个变异算子p1，p2，其中p1表示在对种群进行遗传操作之前首先进行变异操作，取值为0.5；p2通过自适应进行调节，具体算法如下：

4 仿真结果

对两种环境分别进行仿真，具体仿真结果如表1和表2所示。

表1 环境1仿真运行结果

表2 环境2仿真运行结果

表中对改进前后的两种方法分别进行对比，可以看出改进后的遗传算法运行时间短并且行进路径短，体现出其优越性，如图3和图4所示。

图3 环境1和2仿真图

图4 环境1和2迭代过程图

可以看出，相比之下，两种算法对于小规模种群的仿真运行结果没有巨大差异，但随着种群规模的增大，改进后的算法具有明显优越性。

5 结束语

结合传统的栅格法和遗传算法进行移动机器人路径规划，并对遗传算法的操作算子进行了改进。通过对两种不同环境的仿真实验，显示出其优越性。

［1］ D TamilselvI，Sr.Od.Lecturer.Dynamic Programming Agent for Mobile Robot Navigation with Moving Obstacles［J］.lAMA 2009，7（21）：256－260.

［2］ 朱大奇，颜明重.移动机器人路径规划技术综述［J］.控制与决策，2010，6（5）：34－36.

［3］ 周明，孙树栋.遗传算法原理及应用［M］.北京：国防工业出版社，1999.

［4］ 邓志燕，陈炽坤.基于改进遗传算法的移动机器人路径规划研究［J］.机械设计与制造，2010，10（31）：221－225.

［5］ Clément Pêtrès，Yan Pailhas.Path Planning for Autonomous Underwater Vehicles［J］.IEEE Transaction on Robotics，2007，4（23）：41－45.

［6］ 李擎，冯金玲.自适应遗传算法在移动机器人路径规划中的应用［J］.北京科技大学学报2008，10（4）：121－124.

Research on Path Planning of Mobile Robot Based on Hybrid Algorithm

Yang Yong
（Xi’an Aeronautical University，Xi’an 710077，China）

The path planning technology is an important part of the mobile robot navigation technology.The mobile robot path planning in the static known environment，combined with the grid method and traditional genetic algorithm，is improved in the paper.Two different environments are set up，and simulation test results show that it has superiority after being improved.

Mobile robot；Path planning；Grid method；Genetic algorithm

10.3969/j.issn.1002－2279.2015.01.013

TP393

A

1002－2279（2015）01－0044－03

陕西省自然科学基金资助项目（2011K09－16）

杨勇（1964－），男，西安人，教授，硕士研究生，主研方向：电力电子自动化和系统控制仿真。

2014－04－22