基于进化算法和模糊控制的机器人路径规划

张俊溪，米国际，王 鑫，蒋江红

(1.西安航空学院 车辆工程学院，陕西 西安 710077；2.陕西师范大学 计算机科学学院，陕西 西安 710119)

0 引 言

机器人在军事领域及民用领域的应用凸显了重要的实用价值。随着应用的广泛，其活动空间环境也更加复杂，路径规划逐渐成为机器人研究的热点问题。移动机器人路径规划是路径规划问题的典型应用，根据机器人对环境信息的把握程度，可将其分为全局路径规划(静态规划)和局部路径规划(动态规划)两种类型。全局路径规划需要掌握全部的环境信息，局部路径规划则需要掌握部分环境信息或者对环境信息完全未知[1]。机器人在动态复杂环境下的局部路径规划是机器人和人工智能研究领域的一个重要课题[2-3]。环境信息完全未知的局部路径规划主要依靠传感器采集参数，通过传感器融合技术，判断机器人的行动信息[4]。总体上讲，提高机器人对当前环境感知信息的快速理解及识别，快速而准确地避开障碍物，提高自主性和智能性，是当前移动机器人研究的焦点。基于模糊逻辑技术的移动机器人避障问题，已经有较多的研究成果[5-8]，多数是将多传感器的信息直接作为模糊控制器的输入来实现环境认知，但该方案由于模糊控制器复杂的模糊规则导致运算速率下降。也有学者采用人工神经网络[9]、蚁群算法[10]等与模糊逻辑相结合实现对当前环境感知的理解和快速分类，或者通过人工势场法、单纯神经网络、蚁群算法、萤火虫算法等对机器人路径进行全局规划或全局与局部规划相结合[11-15]。基于以上分析，文中提出采用遗传规划算法对机器人传感器获得的环境感知信息进行识别和模式分类[16]，然后采用模糊控制算法建立模糊规则库，并通过解模糊产生精确的驱动命令使机器人正确识别障碍信息，顺利达到指定地点。

1 遗传规划模式分类

遗传规划(genetic programming,GP)是进化计算[17]的一个重要分支，又叫遗传程序设计。它能动态产生预测分析的最优非线性结构，而且不需要数据统计分布的预处理知识，就能自动发现某一类数据判别式的特征[18-19]。目前GP算法已经成功应用于预测分析[20]、数据挖掘[21]、机器人控制[22]、符号回归[23]等方面。

1.1 GP算法用于分类问题的个体描述方法

个体的描述方法包括终端集的选择、函数集的选择、适应度函数的定义、算法控制参数的确定和终止条件的选择等。程序树的叶节点由输入变量和常量构成，叶节点的选择也就是终端集的选择。文中通过对待分类对象的特征进行分析，提取出对象的特征值构成特征向量，作为GP算法的终端集。函数集包括了算术运算符、常见的数学函数以及逻辑判断等。

(1)适应度函数的确定。

适应度函数的确定直接影响着遗传规划算法的进化程度和运算效果。适应度函数是对个体目标函数的基本评价，其选择将会影响种群中个体的优良程度。适应度函数的算法控制参数包括种群的大小和遗传操作的概率。初始群体由众多独立的个体组成，用算法树表示。文中采用混合法生成初始随机树，部分个体采用生长法产生，部分采用完全法，生成方法随机。

(2)遗传操作。

文中采用竞技选择方法进行遗传操作，每次从群体中随机选择N个个体，复制所有个体中适应度值最大的个体，通过不断调整N的大小来改变种群的规模，N越大则被选中的较优个体越多。

文中的变异方法采用的是子树变异法，执行变异时，在随机选取的个体算法树中选择其函数点或者终止符点作为变异点，并将变异点及其以下的子树删除，用产生的新子树替换删除的旧子树。采用混合终止准则，即当超过最大容许进化代数或者当预先设定的问题求解成功后，进化过程立即停止。

1.2 GP算法用于解决分类问题的过程描述

GP算法用于解决分类问题，其过程描述分为8个步骤。设进化代数为G，个体数目为M，节点层数为N，种群中当前个体为x，第i个个体的输出值为Ti(x)。则GP算法在分类问题中的描述如图1所示。

图1 GP算法用于分类问题的过程描述

在过程描述的第二步进化代数G=1时，需要随机产生一个第一代个体，其产生的算法过程为初始化，根据N层节点的子节点数目判断N+1层的节点数，从函数集、变量集、常数集中选择N+1层所有节点并迭代，如果N层节点中的变量个数等于输入变量个数，则节点数M+1，否则循环，直至M达到规定的一代种群中的个体数目。其中，对于N层节点变量个数的判定，如果N大于规定层数，则转到初始化阶段，重新生成个体树；如果N小于规定层数，则继续根据N层节点的子节点数目之和判断N+1层的节点数目。

2 分类器的设计

遗传算法用于分类设计过程。首先初始化路径群体，然后进行遗传操作，如选择、交叉、复制、变异。经过若干代进化以后，停止进化，输出当前最优个体。文中通过遗传规划分类器进行分类后，将所得分类结果用于模糊控制器的规则库信息，遗传规划与模糊控制相结合的算法的计算过程如图2所示。

1.个体编码。

遗传规划的个体编码方式采用层次结构，以二叉树的形式存储，但随着迭代的增加，二叉树的深度会逐渐增加，因此可采用链表形式进行存储，便于下一步的选择交叉操作。

图2 算法流程

2.适应度函数。

适应度函数是遗传规划算法计算的核心内容，适应度函数选择的好坏直接影响算法的输出结果。文中采用特征向量法提取个体的数据信息，任意输入信息Pi的特征向量为Pi=[θi,Vi,Di]，其中θi为位置信息，Vi为速度信息，Di为距离信息，包含前、左、右三个方向的距离信息。选取Pi与Pi+1的距离信息最小值的倒数为适应度函数值，当两点距离最小时归为一类，其倒数为适应度函数值，取最大值作为算法运算终止的条件。适应度函数F(P)见式1：

(1)

3.操作算子。

(1)随机初始化群体P(0)，计算群体P(0)中个体的适应度；

(2)计算适应度函数F(P)，如果满足条件则转第三步，不满足则继续执行选择、交叉、变异操作；

(3)由p(t)通过遗传操作形成新的种群p(t+1)，计算p(t+1)中个体的适应度，如果满足条件则输出，不满足则继续执行遗传操作；

(4)输出。

3 模糊控制器设计

模糊控制器的一般设计步骤包括模糊推理、建立模糊规则库、解模糊以及输出控制变量。模糊控制器的输入是各传感器采集的距离信息，包括机器人所在位置与目标方向夹角θ、运动速度v以及机器人与物体之间的距离D。输出是移动机器人的左右轮加速度的信息a以及舵机转向信息α。

将距离D定义为{NEAR，MIDDLE，FAR}；将当前运动速度v定义为{SLOW，MIDDLE，FAST}；将目标方位θ定义为{LEFT，FRONT，RIGHT}；将移动机器人的转向角α定义为{LVL，LL，LM，LS，ZO，RS，RM，RL，RVL}；将移动机器人后轮加速度a划分为{NB，NS，Z，PS，PB}。

模糊控制算法流程如图3所示。

图3 模糊控制算法框图

通过以上定义，并结合遗传规划分类结果，将分类结果模糊化，构建模糊规则库，如表1所示。

表1 模糊规则库

隶属度取各个语言变量的隶属度函数形状为对称的三角形且模糊分割是对称的。根据不同的目标方向确定合适的模糊规则，其形式为：

ifDisDiandvisvjandθisθkthenαisαlandaisam

其中，i=NEAR,MIDDLE，FAR；j=SLOW，MIDDLE，FAST；k=LEFT，FRONT，RIGHT；l=LVL，LL，LM，LS，ZO，RS，RM，RL，RVL；m=NB，NS，Z，PS，PB。这些规则把输入模糊变量变换成模糊输出指令(即转向角和加速度)，再应用重心法对这些模糊输出指令进行去模糊化处理，最后得到精确的控制指令。

4 仿真实验

为验证文中路径规划算法的有效性，将提出的遗传规划算法(GP)路径规划与蚁群算法路径规划收敛特性进行比较。从图4(a)、(b)可以看出，蚁群算法的收敛过程较为平滑，最终在迭代600次以后收敛于适应度值680，GP在前300次迭代过程中呈现震荡形态，但在400次以后收敛于650，并且表现较为稳定，说明GP较早获得最优解，且收敛后较为稳定。

图4 遗传规划与蚁群算法收敛过程比较

图5 采用遗传规划与模糊控制的局部

图5是采用遗传规划与模糊控制的局部路径规划搜索结果以及采用蚁群算法和模糊控制的局部路径规划搜索结果。设定环境为20×20有固定障碍物的栅格环境，图5(b)相较于图5(a)有一段明显的无效路径，即(5,15)～(10,5)。总体仿真结果表明，遗传规划与模糊控制相结合的局部路径规划算法在收敛效率和路径搜索的稳定性方面优于蚁群算法和模糊控制的局部路径规划算法。

5 结束语

提出一种基于进化算法和模糊控制算法相结合的智能路径规划策略。采用GP对移动机器人的环境信息进行识别和分类，并将分类结果作为模糊控制器计算的依据；然后将障碍物位置和目标信息模糊化，并在进化算法分类的基础上建立规划库，通过解模糊产生驱动命令，并使机器人按照最优路径达到指定目的地；最后将该算法与GP路径规划及模糊控制路径规划仿真结果进行比较。结果表明，提出的智能路径规划策略可以使移动机器人对未知环境信息的分类更加准确，识别更加高效。

参考文献:

[1] 王耀南.机器人智能控制工程[M].北京:科学出版社,2004.

[2] 熊开封,张 华.基于改进型FNN的移动机器人未知环境路径规划[J].制造业自动化,2013,35(11):1-4.

[3] 魏 唯，欧阳丹彤，吕 帅，等.动态不确定环境下多目标路径规划方法[J].计算机学报,2011,34(5):836-846.

[4] 张德惠,王利辉.移动机器人复杂路径规划优化方法研究[J].制造业自动化,2012,34(5):98-101.

[5] 陈卫东,朱奇光.基于模糊算法的移动机器人路径规划[J].电子学报,2011,39(4):971-974.

[6] 刘国荣,张扬名.移动机器人轨迹跟踪的模糊PID-P型迭代学习控制[J].电子学报,2013,41(8)：1536-1541.

[7] 付宜利,顾晓宇,王树国.基于模糊控制的自主机器人路径规划策略研究[J].机器人,2004,26(6):548-552.

[8] 陈卫东，李宝霞，朱奇光.模糊控制在移动机器人路径规划中的应用[J].计算机工程与应用,2009，45(31)：221-223.

[9] 张明路,彭商贤,曹作良,等.用于移动机器人避障的人工神经网络和模糊逻辑控制技术[J].中国机械工程,1997,8(2):21-24.

[10] LIU Chuanling,LIU Huaiwang,YANG Jingyu.A path planning method based on adaptive genetic algorithm for mobile robot[J].Journal of Information and Computational Science,2011,8(5):808-814.

[11] KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].International Journal of Robotics Research,1986,5(1):90-98.

[12] KOREN Y, BORENSTEIN J. Potential field methods and their inherent limitations for mobile robot navigation[C]//Proceedings of IEEE conference on robotics and automation.Sacramento,CA,USA:IEEE,1991:1398-1404.

[13] 柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224.

[14] 杜鹏桢，唐振民，陆建峰,等.不确定环境下基于改进萤火虫算法的地面自主车辆全局路径规划方法[J].电子学报,2014,42(3):616-624.

[15] 刘 玲,王耀南,况 菲,等.基于神经网络和遗传算法的移动机器人路径规划[J].计算机应用研究,2007,24(2):264-265.

[16] 周 庆，牟 超,杨 丹.教育数据挖掘研究进展综述[J].软件学报,2015,26(11):3026-3042.

[17] 云庆夏.进化算法[M].北京:冶金工业出版社,2000.

[18] DOWNEY C,ZHANG Mengjie.Parallel linear genetic programming[C]//Proceedings of the 14th European conference on genetic programming.Torino,Italy:[s.n.],2011:178-189.

[19] KUO C S,HONG T P,CHEN C L.A knowledge-acquisition strategy based on genetic programming[J].Cybernetics and Systems,2008,39(7):670-683.

[20] ETEMADI H,ROSTAMY A A A,DEHKORDI H F.A genetic programming model for bankruptcy prediction:empirical evidence from Iran[J].Expert Systems with Applications,2009,36(2):3199-3207.

[21] ALAVI A H,GANDOMI A H.A robust data mining approach for formulation of geotechnical engineering systems[J].Engineering Computations,2011,28(3):242-274.

[22] OUANNES N,DJEDI N E,DUTHEN Y,et al.Gait evolution for humanoid robot in a physically simulated environment[M]//Intelligent computer graphics.[s.l.]:[s.n.],2012:157-173.

[23] GELLY S,TEYTAUD O,BREDECHE N,et al.A statistical learning theory approach of bloat[C]//Genetic and evolutionary computation conference.Washington DC,USA:IEEE,2005:1783-1784.