文章

基于遗传算法的多移动机器人协调路径规划

2012-05-09孙树栋 林茂

726阅
采用链接图法建立了机器人工作空间模型;应用遗传算法规划多移动机器人运动路径;引入适应值调整矩阵新概念,以达到对多移动机器人运动路径的全局优化;基于面向对象技术,研制成功多移动机器人路径规划动态仿真系统。大量仿真实验结果表明3所提方法可行。

1引言

    多移动机器人的运动规划受到普遍重视,文献应用链接图建立工作空间模型.而用动态图处理移动机器人之间的协调.两者结合解决多移动机器人路径规划.文献基于一种相对固定的协调策略.提出了分布式运动规划方法。

    机器人路径规划是NP(Nonlincar Programming)困难问题,传统的优化算法难以奏效。文献分别应用遗传算法规划机器人运动路径取得较好效果.本文对遗传算法适应值计算方法作了改进,从而规划出多移动机器人全局最优的运动路径。

2模型建立

    假设:1)移动机器人在2D空间中运动;

    2)障碍物可用凸多边形描述;

    3)把障碍物边界向外扩展机器人木体在长、宽力一向上最人尺寸的1/2.机器人可看作质点.

    自由空间的构造方法如下.:

    1)从一个障碍物顶点到其它障碍物顶点之间的连线或顶点到边界之间的垂线称为链接线,链接线不与任何障碍物相交,设Pi(i=1,2,....n)表示障碍物顶点,从P1点开始,依次做Pi的链接线;

    2)删去多余的链接线2使链接线与边界、障碍物边线围成的每一个自由空间均是凸多边形,且凸多边形面积最大;

    3)链接线的中点作为机器人路径点,这些路径点顺序标识为1,2,3,...n;连接各路径点形成的网络图即为机器人可自由运动的路线,如图1所示。

机器人工作空间链接图

图1 机器人工作空间链接图

3 路径规划算法

    3.1 编码方法

    取网络图中路径点的标识序列数作为路径编码,若起始点或终止点不在网络图上,则从该点向临近的路径点做链接线,并将该点作为一个新的网络图路径点。

    3.2 遗传算法

    1)初始路径集的产生

    如图1所示,机器人A、B的初始路径产生过程如下:从起始点出发,随机选取与起始点相邻的一个点作为下一路径点,如此反复,直到找到终点为止。在一条路径的产生过程中,为避免产生重复路径,规定当一个路径点选中以后,随后的随机选点操作将忽略该点,即认为该点与其它点的边长为∞,若选择一点后,尽管该点不是终点,但该点的所有邻接点都已在前面的步骤中选择过,那么该点作为无效点,再退回到前一点,重新选择。

    设机器人AB的初始路径集分别表示为:

    rA={ra1,ra2,...raN},rB={rb1,rb2...,rbN}

    2)适应值的确定

    设rA,rB中个体rai,rbj的路径长度分别为L(rai),L(rbj)对单机器人路径规划,可以将每条路径的长度作为其适应值。但在多机器人系统中,为了避免机器人之间的相互碰撞,还要考虑各移动机器人之间协调问题。

    设当一台机器人在两路径点之间的边运动时,另一台机器人不能以相反方向进入该边,而只能在该边的另一端等待,直到先进入该条边的机器人走出该边,若两台机器人同时到达一条边的两端,则按优先级别确定先后顺序。设rai,rbj两条路径协调后,对应rai的等待时间为taij,对应rbj的等待时间为tbji,相应的距离为

    Waij=v*taij,wbji=v*tbji

    式中V表示机器人运动速度,此处认为机器人的移动速度不变,故路径最短与时间最短等价,从而得到两个适应值调整矩阵Ma,Mb为

   

    式(9)得到的H矩阵是多机器人系统的总体适应值矩阵,矩阵中的元素gaij+gbji表示机器人A与机器人B路径协调后的适应值之和。

 

分页

    多机器人系统的优化是指对其总体进行优化,即总体适应值达到最小

   

4仿真研究

    基于上述方法.在Windows 95环境下,应用VC++4.0开发成功多机器人运动规划仿真系统,对图1所示的环境条件,不同情况的优化结果分别如图2和图3所示。

 

    图2 优化仿真结果2

 

    图3 优化仿真结果3

    图2中机器人A,B的起始点与终止点恰好相反,分别为4,24和24,4.图2中粗线所示即为优化结果,机器人A路径为:4-8-10-15-20-23-24.机器人B运动路径为24-23-20-15-7-10-8-4,显而易见,从点4到点24的最短路径就是机器人A所走路径,机器人B为了避免与机器人A在10-15路径段相碰,绕道15-7-10,此结果即是给定条件下的最优解。

    图3中机器人A和B的起始点与终止点分别为:4,21和25,2.图中粗线所示即为优化结果。从图中可见,虽然机器人A与机器人B路径相交,但它们到达相交点的时间不同,所以机器人A与B的运动路径就是图中最短路径。

5 结论

    1)本文采用链接图法标识多机器人二维工作空间,简单易行。

    2)以链接图顶点序列号作为机器人路径和遗传算法编码,简化了路径表示方法#便于遗传算子操作。

    3)引入的适应值调整矩阵,较好解决了多机器人路径规划相互避碰问题,仿真结果进一步说明算法的有效性。

责任编辑:赵蔓
本文为授权转载文章,任何人未经原授权方同意,不得复制、转载、摘编等任何方式进行使用,e-works不承担由此而产生的任何法律责任! 如有异议请及时告之,以便进行及时处理。联系方式:editor@e-works.net.cn tel:027-87592219/20/21。
读者评论 (0)
请您登录/注册后再评论
相关阅读