基于遗传算法的机器人在全局静态环境中路径规划研究

张涛+李继生+王凤萍

摘 要：随着智能控制的快速发展，移动机器人都被赋予了一定的智能自主能力。本文以静态环境路径规划为研究重点，通过对路径规划方法和遗传算法相关工作进行了研究，设计了一套基于遗传算法的静态全局路径规划算法，运用MATLAB对该路径规划算法进行了仿真研究，并分析了相关参数对路径规划效果的影响，以及参数合理调整的基本思路；最后也初步研究并仿真了动态环境下的路径规划算法。

关键词：移动机器人；路径规划；遗传算法； MATLAB仿真

DOI：10.16640/j.cnki.37-1222/t.2017.04.192

1 引言

遗传算法是国际上广泛应用的一种新型参数优化方法，传统的优化方法在解决路径规划这类复杂非线性问题中缺乏足够的鲁棒性，因此研究遗传算法对于移动机器人全局路径规划的发展也起到了推动作用。

根据对环境的了解情况，路径规划分为全局路径规划和局部路径规划，从静态或动态地获取障碍物信息角度看，全局路径规划属于静态规划，而局部路径规划则是动态规划，在移动机器人的应用中需要精确的位置信息，是机器人在执行任务时首先应具备导航和定位能力。

2 基于遗传算法的全局路径规划研究

遗传算法的各个部分是相互作用的，这些参数组合起来的情况非常多，通过手工调节找到最佳的参数组合很困难。如果能在演化过程中，使程序自行调节这些参数，就能使算法适用于更多类型的问题。

仿真运动环境为二维平面空间，已知静态障碍物信息，动态障碍物（数量为1个）可以进行探测。我们的目标是要在已知的静态环境里，让移动机器人自主找到一条从当前位置到目标位置的行动路线，要求这条路径不与障碍物发生冲突并尽可能短，且该路径应与障碍物保持一定的安全距离。

主要从以下几个方面描述：（1）环境及染色体的表示。因为是已知环境下的路径规划，因此机器人的运动环境用一个矩形的黑白二值位图表示，其中黑色区域表示障碍区域，而白色区域表示可自由通行的区域。（2）初始种群的生成。对于基本遗传算法来说，初始种群的产生是通过随机的方式产生的。在路径上随机选择n个节点构成一条路径作为一个染色体。这样形成的初始种群进化效率明显高于随机生成的方法，且不丧失遗传算法的全局搜索能力。（3）路径评估。对路径优劣程度的评估作为遗传算法中染色体的适应值。因此要将规划路径时的要求包含进去，并用数值的形式体现出来，以便进行比较和衡量。由于染色体是可行路径或不可行路径，因此对这两种情况分别进行处理：对于可行路径的适应值我们考虑安全性、路径长度、平滑性这三个因素。不可行路径的适应值计算需考虑不可行线段数与总线段数的比、不可行线段与障碍物的交叉深度和路径的总长度等因素。

（4）遗传操作。根据路径规划问题的实际情况，主要使用了3种遗传操作算子：选择、交叉、变异。由于选择方式采用排序选择，所以无需考虑个体适应度是否取正值或负值以及个体适应度之间的数值差异程度，这样可以避免因优秀个体充斥种群空间导致的早熟。本次采用单点交叉的方法，且首先作用在不可行路径片段上，再按随机方式选择交叉点。本文中采用的变异方式有增加一个点、减少一个点、移动一个点3种方式，在程序执行时随机选择任意一种作为某一父代个体的变异操作。将判断算法收敛的条件设为：若连续进化500次，最优解均未发生变化，且种群的平均适应值提高不足1%，则算法进化代数已达到了设定的最大值。本次實验通过定义一种简单又不影响遗传算法随机性的环境，在该环境下运行9次比较其结果。

3 静态（全局）环境仿真

本次对环境进行仿真的路径规划是寻找满足安全和路线平滑条件下的最短路径也就是求最小值，因此以下各图中适应值越小，则该路径越好。对于静态环境仿真，本次设定的任务，即：遍历N个已知节点，找到最优路径，最后返回起点，类似于旅行商问题。

（1）改变进化代数K（Pc=0.9，Pm=0.2），连续仿真9次，其数据分析表1如下。

图1（a）（b）对应进化代数为K=500，2000的仿真结果。

从仿真结果分析，当交叉和变异的概率都不变时，进化代数K越大，规划出来的路径越优。

（2）改变交叉概率Pc（K=500， Pm=0.2），连续仿真9次，其数据分析表2如下。

图2（a）（b）对应交叉概率为Pc =0.00009，0.9的仿真结果。表2是进化代数不同连续仿真9次对应的时间和路径长度。

（3）改变变异概率Pm（K=500，Pc=0.9）连续仿真9次，分析如表3所示。

图3（a）（b）对应变异概率Pm =0.00002，0.7的仿真结果。

从以上仿真结果分析，经过调整参数后，可以看到本搜索算法成功地找到了近似最优的可行路径。另外可以看到算法的计算时间稍长，还需要进一步优化，在以后的研究中将运用MATLAB对动态路径规划算法进一步仿真研究，并分析了相关参数对路径规划效果的影响，以及参数合理调整的基本思路。

参考文献：

[1]王小平，曹立明.遗传算法理论和应用与软件实现[M].西安交通大学出版社，2002.

[2]薛毅.最优化原理与方法[M].北京工业大学出版社，2001.

[3]吴晓涛，孙曾沂.用遗传算法进行路径规划[J].清华大学学报，1995：14-19.

[4]陈刚.复杂环境下路径规划问题的遗传路径规划方法.机器人[J]，2001：230-233.

[5]龚进峰.数字势场和遗传算法的机器人路径规划的方法[J].天津大学学报，2002：525-529.

[6] 孙树栋，曲严宾.遗传算法在机器人路径规划中的应用研究[J].西北工业大学学报，1998：79-82.

[7] 周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999.

作者简介：张涛（1987-），硕士研究生，天津职业技术师范大学国有资产管理处管理员，研究方向：智能控制、机电一体化。