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

向浩 李哲文 张婷

摘   要：在移动机器人研究领域中，路径规划问题是一项非常值得研究的问题，一般是指在规划路径中使得移动机器人不会碰到任何障碍物。本文针对机器人的路径规划问题进行了分析研究，主要分析在静态环境下，采取网格法对机器人工作空间进行划分，运用遗传算法对路径寻优，引入间断无障碍路径概念以简化初始种群产生，最终通过改进操作算子。合理选择交叉率、变异率以及分析调整适应度函数中的加权系数获得最佳路径。

关键词：机器人路径规划  遗传算法  网格法  路径优化

中图分类号：TP24                                  文献标识码：A                        文章编号：1674-098X（2019）08（c）-0119-02

路径规划是智能机器人领域的核心问题之一，也是机器人人工智能研究的重要方面。典型的机器人路径规划是指为机器人在其工作空间中完成给定任务提供安全且有效的运动路径。通常，机器人可以选择许多路径来完成给定任务，常用的准则有：最短路径、最少能耗或最短使用时间。

1  遗传算法与路径规划

遗传算法的基本运算过程如下。

（1）初始化：首先设置进化计数器，使得初始进化计数t=0，最大进化计数为T，初始群体P（0）中随机生成M个个体。

（2）个体评价：在群体P（t）中，计算各个个体的适应度。

（3）选择运算：选择运算能够把优化的个体直接遗传或配对交叉遗传到下一代。在群体中个体的适应度评估基础上，将选择算子作用于群体。

（4）交叉运算：交叉运算是遗传算法中关键的一步，其交叉算子在遗传算法中起到核心作用，交叉运算是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。

（5）变异运算：变异运算是指对群体中的个体串的某些基因座上的基因值作变动。

（6）终止条件判断：如果t=T，则在演化过程中获得的具有最大适应度的个体被用作最优解决方案输出，并且计算终止。

路径规划中通过第二遗传算法机制能够解决机器人在处理过程中出现动态障碍物时，只根据获得的最优路径到达目的地的情况进行规划的问题。

2  机器人工作空间划分

遗传算法参数设定方法为：群体中的个体数量是s=30，并且交叉概率为pc=0.6。根据模型的不同表达方法，机器人所处的环境有三种典型的环境建模方法：网格方法，网格解耦方法，多面模型表示等，这里仅介绍网格方法建模。

机器人工作空间由网格方法划分，网格由序列号标识，序列号用作机器人路径规划参数代码。如下面的图1所示，机器人路径空间是二維平面空间，障碍物的位置是已知的，并且障碍物的位置在机器人的运动期间不会改变。

通常遗传算法中的初始种群设置可以采用以下策略：

（1）根据问题的内在知识，尝试掌握整个问题空间中最优解所占空间的分布，然后在分布范围内设置初始群。

（2）随机生成一定数量的个体，然后从中挑选最佳个体以添加到初始种群中。该过程是迭代的，直到初始群体中的个体数量达到预定规模。本文主要采用第二种方法对初始种群进行编程。

3  适应度函数设置

在遗传算法中，适应度用来衡量个体利弊的指标。 个体复制的数量根据适合度是否存在来确定，适应度是驱动遗传算法的动力。在特定的应用中，适应度函数的设计应该与解决问题本身的要求相结合。评估函数值与总路径长度值成比例，即最短路径长度用作单独评估函数。路径长度越短，路径长度的适应值越高，因此还需要在个体评估函数和适应度函数之间进行映射。假设两个相邻网格的中心之间的距离是A并且单个路径中包括的网格的数量是n，则单独的评估函数可以取为f ＼u003d nA。 相应的适应度函数可取为g=fmax-f，其中fmax=18，令A=1可便于计算，适应度函数可最终写为g=19-n。

以上个体的适应度为个体hn（n=1，2，3… …）表示机器人在其空间中的运动路径，个体评估函数为 f＼ u003 d nA，适应度函数 g=19- n，个体 hn（ n=1，2，3…）表示机器人在其空间中的运动路径，个体评估函数为 f，并且适应度函数为18-n，该程序随机生成100个单独的种群，并分别使用网格数来表示以下模拟部分。以下10组结果可以解释如何使用遗传算法来优化机器人路径。

h1={0，1，11，21，22，23，24，35，45，55，65，66，67，68，78，88，99}   f1=16  g1=2     2/50

h2={0，1，11，21，22，23，24，35，36，37，47，57，67，78，89，99 }     f2=15   g2=3    3/50

h3={0，11，21，22，33，44，55，65，66，67，78，89，99}            f3=12   g3=6    6/50

h4={0，11，21，22，23，34，45，46，57，68，78，88，99}            f4=12   g4=6    6/50

h5={0，11，22，33，44，55，65，66，67，68，79，89，99}            f5=12   g5=6    6/50

h6={0，1，11，22，33，44，55，66，67，78，79，88，99}             f6=12   g6=6    6/50

h7={0，11，21，22，23，33，43，54，65，66，67，68，78，88，99}       f7=14   g7=4    4/50

h8={0，11，21，22，23，34，45，46，57，68，79，89，99}            f8=12   g8=6    6/50

h9={0，11，21，22，23，34，45，46，47，57，67，78，89，99}          f9=13   g9=5   5/50

h10={0，11，21，22，33，44，55，66，67，68，78，88，89}           f10=12  g10=6   6/50

4  交叉仿真

本文通過选择pc ＼u003d 0.9以随机生成[0～1]之间的数字，产生子代个体h11和h12后，h5和h6交叉产生h13和 h14，h8和h10交叉产生h15和h16。这里用标志位判断，能走就是0，不能走就是1，并且标志位被加起来由Sn表示，且所有位中的最小位是最佳解决方案。以这种方式，保留六个位，分成三组，选择不同的交叉点用于单点交叉，并且消除具有大的附加标志的个体。然后继续添加一些和新生成的个体组成一组继续交叉，具有最小数量的标志的个体是最佳路径。 仿真之后会发现个体{0，11，22，33，44，55，66，67，78，89，99}是最优解。

当最优个体的适应度和群体适应度不再上升或者适应度达到给定阈值时（本文给定的阈值为g），或者当迭代次数达到预设代数时，算法终止，并且预设代数被设置为100代。

5  结语

如何选择遗传算法的参数以及如何对其进行编码是其应用中的一个重要问题。本文针对机器人的路径规划问题进行了分析研究，主要分析在静态环境下，采取网格法对机器人工作空间进行划分，运用遗传算法对路径寻优，引入间断无障碍路径概念以简化初始种群产生，最终通过改进操作算子。合理选择交叉率、变异率以及分析调整适应度函数中的加权系数获得最佳路径。

参考文献

[1] 刘国栋，谢宏斌，李春光.动态环境中基于遗传算法的移动机器人路径规划的仿真[J].西安石油学院学报：自然科学版，2004（3）.

[2] 张捍东，郑睿，岑豫皖.移动机器人路径规划技术的现状与展望[J].系统仿真学报，2005，16（2）：439-443.

[3] 蔡自兴，彭志红.一种新的路径编码机制在移动机器人路径规划中的应用[J].机器人，2001，23（3）：230-233.

[4] 周明，孙树持.彭曼午.基于遗传算法的多机器人系统集中协调式路径规划[J].航空学报，2009，21（2）：146-49.