基于遗传算法的静态环境全局路径规划

第３２卷第１期 ２００５年１月

浙江大学学报（理学版）Ｊｏｕｒｎａｌ　ｏｆ　Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　（Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ） ｈｔｔｐ：／／ｗｗｗ．　ｊｏｕｒｎａｌｓ．　ｚｊｕ．　ｅｄｕ．　ｃｎ／ｓｃｉＶｏｌ．　３２　Ｎｏ．　１

Ｉａｎ．　２００５

基于遗传算法的静态环境全局路径规划陈华华，杜欲，顾伟康（浙江大学信息与电子工程系，浙江杭州３１００２７）

摘要：静态环境中移动机器人全局路径规划一直是路径规划中的一个重要问题．作者提出了基于遗传算法的静态环境下机器人全局路径规划方法．该方法首先提出机器人工作空间中环境信息的神经网络模型，并利用该模型建立机器人免碰撞路径与神经网络输出的关系，然后将需规划的路径的二维编码简化成一维编码，并把免碰撞要求和最短路径要求融合成一个适应度函数．通过对算法进行实验仿真表明，提出的全局路径规划方法是正确和有效的．

关键词：机器人；中图分类号：ＴＰ２４２．　６遗传算法；全局路径规划；神经网络；适应度函数

文献标识码：Ａ文章编号：１００８－　９４９７（２００５）０１一０４９－０５

ＣＨＥＮ　Ｈｕａ－ｈｕａ，ＤＵ　Ｘｉｎ，　ＧＵ　Ｗｅｉ－ｋａｎｇ（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｅｌｅｃｔｒｏｎｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ，　Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒ－ｓｉｔｙ，Ｈａｎｇｚｈｏｕ　３１００２７，Ｃｈｉｎａ）Ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｇｌｏｂａｌ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｉｎ　ａ　ｓｔａｔｉｃ　ｅｎｖｉｒｏｎｍｅｎｔ．　Ｊｏｕｒｎａｌ　ｏｆ　Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　（Ｓｃｉｅｎｃｅ　Ｅｄｉ－ｔｉｏｎ），２００５，３２（１）：４９＾－５３Ａｂｓｔｒａｃｔ：Ｍｏｂｉｌｅ　ｒｏｂｏｔ　ｇｌｏｂａｌ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｉｎ　ａ　ｓｔａｔｉｃ　ｅｎｖｉｒｏｎｍｅｎｔ　ｈａｓ　ｂｅｅｎ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｐｒｏｂｌｅｍ　ａｌｌ　ａｌｏｎｇ．　Ｔｈｅｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｍｅｔｈｏｄ　ｏｆ　ｇｌｏｂａｌ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｂａｓｅｄ　ｏｎ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ．　Ｔｈｅ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ｍｏｄｅｌ　ｏｆ　ｅｎｖｉｒｏｎ－ｍｅｎｔａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｉｎ　ｔｈｅ　ｗｏｒｋｓｐａｃｅ　ｆｏｒ　ｒｏｂｏｔ　ｉｓ　ｃｏｎｓｔｒｕｃｔｅｄ．　Ｔｈｅ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｂｅｔｗｅｅｎ　ａ　ｃｏｌｌｉｓｉｏｎ－ｆｒｅｅ　ｐａｔｈ　ａｎｄｔｈｅ　ｏｕｔｐｕｔ　ｏｆ　ｔｈｅ　ｍｏｄｅｌ　ｉｓ　ｅｓｔａｂｌｉｓｈｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｉｓ　ｍｏｄｅｌ　ａｎｄ　ｔｈｅ　ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ　ｃｏｄｉｎｇ　ｆｏｒ　ｔｈｅ　ｖｉａ－ｐｏｉｎｔｓ　ｏｆ　ｐａｔｈｉｓ　ｃｏｎｖｅｒｔｅｄ　ｔｏ　ｏｎｅ－ｄｉｍｅｎｓｉｏｎａｌ　ｏｎｅ．　Ｔｈｅｎ　ｔｈｅ　ｆｉｔｎｅｓｓ　ｏｆ　ｔｈｅ　ｃｏｌｌｉｓｉｏｎ－ｆｒｅｅ　ｐａｔｈ　ａｎｄ　ｔｈａｔ　ｏｆ　ａ　ｓｈｏｒｔｅｓｔ　ｄｉｓｔａｎｃｅ　ａｒｅｆｕｓｅｄ　ｔｏ　ａ　ｆｉｔｎｅｓｓ　ｆｕｎｃｔｉｏｎ．　Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｉｓ　ｃｏｒｒｅｃｔ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ．

Ｋｅｙ　ｗｏｒｄｓ：ｒｏｂｏｔ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；　ｇｌｏｂａｌ　ｐａｔｈ　ｐｌａｎｎｉｎｇ；　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ；ｆｉｔｎｅｓｓ　ｆｕｎｃｔｉｏｎ 机器人路径规划是指在机器人工作空间中分布一些障碍物，在给定起始点和目标点之间为机器人找到一条安全、高效的免碰撞运行路径．一般而言，符合这种条件的路径有许多条，实际应用中往往要选择一条在一定准则下最优的路径，通常的准则有：路径最短或者时间最短等〔１－８］ 路径规划的典型方法有可视图法［９．１０］、人工势场法［［１１〕等．这些算法存在的问题是缺乏灵活性，或者算法易陷入局部最小点．遗传算法弥补了这些方法的不足，它是基于自然遗传和自然选择的多搜索算法［１２］，具有算法鲁棒、灵活，在种群中搜索不易落人局部最小点等优点．已有许多学者的研究表明，遗传算法在规划机器人运动路径中取得了较好的效果仁‘一“，１３＾１５］ 自主机器人导航通常假定环境中有已知的和未知的障碍物，它包括在已知障碍物之间规划道路的全局路径规划和实时障碍物免碰撞的局部路径规划［［５，６］．静态环境中机器人全局路径规划一直是路径规划中的一个重要问题，具有广阔的应用范围［［１６］本文首先提出了机器人工作空间中环境信息的神经网络模型，把工作空间区分为障碍物区域与非障碍物区域，并利用模型建立了机器人免碰撞路径与神经网络输出的关系，然后将需规划的路径的二维编码简化成一维编码，将免碰撞要求和路径最短要求融合成遗传算法的一个简单适应度函数，并通过实验仿真验证了方法的有效性和准确性．

收稿日期：２００４－０５－２０．基金项目：国家自然科学基金资助项目（Ｎｏ．　６０１０５００３　）；浙江省自然科学基金资助项目（Ｎｏ．　６０００２５）．作者简介：陈华华（１９７５－），男，博士生，主要从事智能机器人研究．

万方数据浙江大学学报（理学版）第３２卷

１环境信息的神经网络描述 首先对工作空间提出假设： （１）移动机器人在有限二维空间中运动； （２）把障碍物边界向外扩展机器人本体在长、宽方向上最大尺寸的１／２，则机器人可看作质点忽略不计； （３）工作空间中的障碍物可用凸多边形来描述． 设机器人工作空间如图１所示，其中阴影部分表示障碍物．根据文献［１７，１８］，环境信息可以用如图２所示的神经网络模型来描述，式（１）是其数学表不．

激发函数，（Ｘ，ｉ，Ｙ）为机器人工作空间中的任意一点的坐标．由模型可知，整个工作空间中任意点的坐标相对于模型输出只有。和１，当Ｃｋ　＝　１（ｋ　＝　１，２）时，表示（Ｘ；，Ｙ）在第ｋ个障碍物区域内，反之表示不在障碍物区域内。 假设机器人是一个质点，对于工作空间中的任意一点（Ｘ，，Ｙ；），当机器人运动过程中到达这一点时，如果Ｃｋ　＝　１（ｋ　＝　１，２），那么表示机器人与第ｋ个障碍物发生碰撞，反之，没有发生碰撞．因此免碰撞的路径可以描述为神经网络模型输出为Ｃ夕＝０（ｋ＝１，２）的路径．图１中工作空间中只有两个障碍物，其神经网络模型相对比较简单．对于多障碍物的工作空间，其神经网络模型也相应的变得复杂，图３是其神经网络模型表示．

图１机器人工作空间Ｆｉｇ．　１　Ｔｈｅ　ｗｏｒｋｓｐａｃｅ　ｆｏｒ　ａ　ｒｏｂｏｔ 图３多障碍物工作空间的神经网络模型Ｆｉｇ．　３ Ｔｈｅ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ｆｏｒ　ｔｈｅ　ｍｕｌｔｉ－ｏｂｓｔａｃｌｅ

２路径规划的遗传算法

图２环境信息神经网络模型Ｆｉｇ．　２　Ｔｈｅ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ｆｏｒ　ｔｈｅ　ｅｎｖｉｒｏｎｍｅｎｔ＝ｆ（Ｔｒ），（ｋ＝１，２）．

一艺ＯＭｍ＋ＯＴ．（１）

曰兀ＯＭｍ＝ｆ（ＩＭ．）＂Ｉ　，ｍ＝Ｗ－Ｘ　ｉ＋二＊Ｙ；＋入＂．其中，日是顶层结点的输出，Ｔ，是顶层结点的输入，外是顶层结点的阂值，Ｏ、是中间层第ｍ个结点的输出，ＩＭ．是中间层第ｍ个结点的输人，ｗ，和ｗｙ．是输人层到中间层的权值，ｆ　（ｘ）　＝　１／＜１　＋　ｅ　－ＩＴ）是

遗传算法（ＧＡ）是一种基于自然选择和自然遗传的全局优化算法［１２］，它采用从自然界选择、遗传操作中抽象出来的几个算子—复制、交叉和变异操作，对参数编码的字符串进行遗传操作，每一字符串对应于一个可行解，这种遗传操作是对多个可行解组成的群体进行的．ＧＡ的主要优点是：采用群体方式对目标函数空间进行多线索的并行搜索，可同时对多个可行解进行检查，交叉和变异操作使可行解之间交换信息和产生新的可行解，不会陷人局部极小点；ＧＡ只需要可行解目标函数的值，而不需要其它信息，对目标函数的连续性、可微性没有要求，因此使用方便；解的选择和产生采用概率方式，因此具有较强的适应能力和鲁棒性．

万方数据第１期陈华华，等：基于遗传算法的静态环境全局路径规划２．１路径编码方式 遗传算法中，影响计算时间的主要因素是编码长度和搜索空间，太长的编码长度和太大的搜索空间都会使计算时间迅速增长，因此，采用简化编码长度技术，即把路径的二维编码简化为一维编码．编码技术如图４所示．图中的起始点ｓｔａｒｔ为移动机器人的当前位置，ｇｏａｌ为目标点位置．算法规划的路径就是在起始点和目标点之间确定最佳路径的点序列坐标（（ｘｙｉ）．在工作空间坐标系ＸＯＹ中，路径点序列的坐标是二维的，为降低编码长度，对坐标系进行坐标转换，转换后的坐标系是ｘｏ’　ｙ，ｘ轴为起始点与目标点的连线，然后把ｘ轴等分成二１　，　ｘ２　１　．．．，二。，那么优化的路径点就简化为一维的ｙ坐标编码优化问题．编码采用浮点数形式，编码格式如图５所示．息的神经网络模型式（１）的输出，路径点不在障碍物内的适应度函数介ｔ１，可表示为

，ｉｆ冗Ｃｋ　（ｘ，，ｙ）＝０；

ｆｉｔ１１（２）

ｏｔｈｅｒｓ．

１１

ｎ曰

‘！

气１ 一一

式中，ｉ为工作空间的路径上的所有点，ｎ为障碍物的个数．式（２）表明，如果路径点是免碰撞的，那么适应度为１，否则为。 （２）设机器人当前路径点与下一个路径点的连线为Ｐ，Ｐ；＋１，则其与各障碍物区域不相交的适应度函数．ｆｉｔ１２可表示为ｆｉｔ１２＝｝０，“Ｐ，Ｐ；＋１　ｎ１１，Ｏｂｓｔａｃｌｅ　（ｋ）　（ｋ

ｏｔｈｅｒｓ．＝１，…，ｎ）；

（３）

综合式（（２），　（３）得到动态避障的适应度函数方ｔ，为ｆｉｔ，＝ｆｉｔｓ，　Ｘ　ｆｔ　，ｚ．（４）

图４Ｆｉｇ．　４ Ｃｏｄｉ路径编码方法示意图

ｎｇ　ｆｏｒ　ｔｈｅ　ｖｉａ－ｐｏｉｎｔｓ　ｏｆ　ｐａｔｈ

Ｙ１｛Ｙｚ｝．Ｙ３｛……！ｙ 图５路径编码结构 Ｆｉｇ．　５ Ｔｈｅ　ｃｏｄｉｎｇ　ｓｔｒｕｃｔｕｒｅ　ｆｏｒ　ｐａｔｈ２．２确定适应度函数 适应度函数是遗传算法收敛性和稳定性的重要影响因素，路径的规划要求满足两个条件：免碰撞和路径最短．采用各项评价函数加权求和是确定适应度函数的典型方法，５．１９１，这种方法的缺点是各个权系数比较难调整和确定，易于引起优化不稳定，这是因为各个权系数不是恒定不变的，而是随着路径和障碍物的情况变化而变化的．因此，在确定适应度函数时，尽可能使适应度函数的项数最少，但又必须把路径规划的两个条件融合在遗传优化过程中． 免碰撞是路径规划的基本条件，是机器人安全通过工作空间的保证．免碰撞条件是任意路径点不在任意一个障碍物内，同时要保证当前路径点与下一个路径点的连线与各障碍物区域不相交．假设机器人的工作空间如图４所示，则： （１）任意路径点不在任意一个障碍物内，即路径点（二，．Ｙ）不能落人障碍物区域，结合动态环境信 路径最优有多个标准，本文采用路径最短作为最优路径的标准，其适应度函数方ｔ：可表示为 刀一Ｉ ｆｉｔ，一万Ｉ／（二＋，一ｘ；）２＋（二十，一Ｙｉ）Ｚ．　（５） 由式（４）、式（５）得到最终的适应度函数为 ｆｉｔ＝ｆｉｔ，　Ｘ　ｆｉｔ，． （６）式（６）把两个约束条件有机融合在一起，一方面使得计算简单，同时也避免了两项加权求和引起的优化不稳定问题．２．３遗传操作算子定义 初始化种群在工作空间中垂直于二ＩＩＸＺ９．．．＇ｘｎ的垂线上随机选择，种群规模反映了工作空间内随机产生的路径条数．规模越大，产生的路径越精确，而且容易找到全局最优解，但搜索时间也相应会越长一般取２０一１００，本文种群规模取为３５． 复制操作是将父代的个体原封不动地传递到子代．在复制过程中，每个个体是按照适应度值的大小决定其能否被复制到下一代的概率，复制算子可使群体中的优秀个体数目逐渐增加，使进化过程向更优解的方向发展，反映了自然界中优胜劣汰的法则．本文采用蒙特卡罗法则复制．同时考虑到最优个体在进化中可能受到破坏，对于新的种群中适应度最小的个体用上一代种群中最大的个体代替，使得群体中的可行路径数目增加，进化过程向着更优的方法发展． 交叉操作：复制算子只能在现有群体中寻优，而不能产生与父代不同的个体，交叉算子可使同一代的某对个体间，按一定的概率交换其中的部分基因，