论文研究-基于图论的参数曲线集目标区域识别方法.pdf

所需积分/C币:5 2019-09-06 18:38:53 680KB .PDF

针对多机器人协作系统,提出了一种新的混合定点转动和遗传算法的方法,解决其协作路径规划问题。该方法利用遗传算法并行计算、不易陷入局部最优的优点,具备概率上寻找全局最优解的能力,同时结合了定点转动法易实现、有效减少单机器人路径浪费的优点。仿真实验结果表明,该规划方法运算速度较快,在得到有效规划路径的同时,也易于实现对单机器人的控制。
刘凵,梁文君:多机器人协作搬运路径规划研究 2010,46(32)199 20 -20-15-10-505101520 20-15-10-505101520 (a)多机器人系统整体协作路径示意 (b)单机器人路径示意 图2筒单环境下的基于遗传算法的多机器人系统路径规划 15-10-5051015202530 15-10-5051015202530 (a)多机器人系统整体协作路径示意 b)单机器人路径示意 图3复杂环境下的基于遗传算法的多机器人系统路径规划 加「-0.15,0.151的随机扰动而产生。 定点转动法能够实现多机器人系统的平滑路径,计算筍 交叉操作:采用多点交叉方法,即随机选取一个区域,用单,效率高。算法的思路是首先确定一系刎多机器人系统姿 中交又后的子代个体代替原种群中的父代个体,产生新的种群。态旋转候选点(以下简称候选点,然后连接某些候选点得到 变异操作:在新的个体屮加入[-3,3]的正态分布白噪声作多机器人系统屮心的最短平滑路径;最后规定多机器人系统 为y变量的随机扰动,加入位姿最小变化角度2倍的随机噪声只在候选点绕其中心旋转特定角度以改变姿态,而在路径上 作为c变量的随机扰动,构建新的基因以寻找最优解。 的其他点则保持姿态,根据多机器人系统中心的规划路径改 3.2算法分析 变位置状态;通过以上步骤得到多机器人协作系统的整体规 仿真屮取基于较优实验结果的参数如下:初始种群规模划轨迹 15,交叉概率0.7,变异概率0.3,最大子代数500适应度函数4.1确定姿态旋转候选点 中各参数分别取a=5,B=1,k=2200,km=10,k=9,k=8。 如图4所示,令r为多机器人系统位置约束距离(即杆状零 如图2、图3所示,图中方框表示障碍物;离散线段表示杆件长度),A为安全变量,则R=r+A。以R2扩张障碍物边缘 状零件搬运过程中的离散位姿,即多机器人系统离散位姿信虚线表示扩张后的环境信息,虚线的交点则是候选点,如图4 息,如图(a)所示;离散线段端点连线表示单机器人规划路径,中小方块所示(包括多机器人系统中心起始点和终点);位于 如图(b)所示;端点连线没有穿越障碍物表示了算法避碰的有障碍物里的交点为不合格的候选点,需要从候选点集合中除 效性。 去。很明显,多机器人系统可以在侯选点仼意改变位姿,而不 由规划结果可以看岀,算法能够求岀多杋器人协作搬运会碰到任何障碍物。文中设定多机器人系统仅在候选点改变 零件的可行路径,但所得到的各单机器人的路径波动较大,表姿态。 明在搬运过程中发生了过多的转动,尤其是在障碍物分布比 20 较稀疏的空间中,表现更为明显,各机器人都走了很多不必要 的弯路。这是上述基于遗传算法的规划方法的一个重大缺 10 陷,主要是由于应用遗传算法时,染色体个体包含较多协作信 息,进化过程中存在较大的随机性,使得在稀疏障碍物分布空 间中,多机器人系统形成的离散位姿存在频繁变化,得到的单 机器人轨迹不能形成直线段,这就造成了路径浪费和资源消 》→ 耗,同时,也引起了规划耗时的问题。 4基于定点转动法的路径规划 针对上述不足,提出一种新颖的定点转动法以提高算法 1015 速度,减少路径浪费。 图4候选点示意及候选点连线穿越障碍物示意 2002010,46(32) Computer Engineering and Applications计算机工程与应用 4.2寻找最短路径 多机器人系统保持姿态以平移动作沿着其屮心规划轨迹经调 在定点转动法中,最重要的是在候选点中选择构成路径整点、移动到位姿改变点 的点,可以采用最短路径为目标,通过常规的搜索算法得到。 (3)其他情况下,San=-1,此时点之间通过直连方式 文中,最短路径搜索法采用迪科斯彻( Dijkstra)算法。该算法或小幅平移方式均得不到有效路径。 可以在一个有权重的有向图中,找到从一个顶点到任何其他4.4算法分析 顶点的最短路径。初始时,原点s的路径长度值被赋为0,同时 如图5所示,图中方框表示障碍物、离散线段表示杆状零件 把所有其他顶点的路径长度设为无穷大,即表示不知道任何搬运过程中的离散位姿,即多机器人系统离散位姿信息如图(a) 通向这些顶点的路径。当算法结束时,dv中储存的便是从8所示离散线段端点连线表示单机器人规划路径,如图(b)所示。 到ν的最短路径,或者如果路径不存在的话v为空。前述得 通过比较同一规划环境的算法结果,如图3、图5所示,得 到的候选点及其分布状态形成了有向图,有向图中任意两点到表2所示数据,证明了定点转动法在算法计算消耗时间和单 之间的距离权重信息则通过构建有效距离矩阵Di得到,这机器人路径和这两方面远优于遗传算法。 样,通过迪科斯仞算法,就能确定从起始点到终点之间被选定 构成多机器人协作路径的候选点。 表2算法结果比较 构建有效距离矩阵Dis=[DisJ]-,2.--,2-,,n为候选点个 遗传算法定点转动法 计算消耗时间/51287107617 数。矩阵中的元素Dis。表示候选点i和侯选点j的距离信息, 单机器人路径和 097348 6.4942 其值通过以下三种计算方式得到 系统环境: Intel Core2CPUT5001.66GIz,1GB内存。 (1)候选点i和侯选点j的连线不穿越障碍物,即为直连方式 定点转动法在稀疏障碍物分布环境中是迅速而有效的, 但这一算法也存在局限性,主要是算法的完备性得不到保证 (2候选点i和候选点的连线虽然穿越障碍物,但以ⅳ为即当系统存在可行路径时,可能得不到可行解。这种情况发 起点,沿障碍物边缘扩张线小幅平移(平移距离最大不超过R/2)牛在复杂窄道环境屮,由于找不到符合算法要求的候选点而 得到调整点、∫后,连接ρ、的直线不穿越障碍物,即为小得不到有效规划路径。而前一节所提出的基于遗传算法的规 幅平移方式,如图4圈中所示,圆点为得到的词整点、广。 划方法能够较好地处理这种情况,因此,提岀定点转动-遗传算 Ds=x-x)+(y:-y)+(x;=x)+(y-y)y+ 法作为多机器人系统协作搬运问题的最终解决方案 5基于定点转动-遗传算法的路径规划 其中,x1、y1、x、y为i点小幅移动后的坐标位置; 基于定点转动-遗传算法的多机器人系统协作路径规划, (3)其他情况,则Dis=inf 即在整个搜索空间中,稀疏障碍物分布处使用定点转动法,障 至此,通过连接某些候选点得到了从起始位姿到目标位碍物分布形成过窄L型、T型通道时使用遗传算法规划路径方 姿的多机器人系统中心的最短路径。 法,其关键点在于如何得到遗传算法的作用区域,即得到遗传 43确定多机器人系统整体协作路径 算法的起始点和终止点。由于遗传算法保证了特殊窄道环境 确定多机器人系统整体协仵路径的关键在于确定多机器的路径搜索完备性,基于定点转动-遗传算法的路径规划方法 人系统在候选点转动的角度,根据候选点的连接方式决定。 能保证规划空问路径搜索的完备性。 构建状态矩阵Sa=[Sa-1,…m-…,n为候选点个数。5.1算法描述 矩阵中的元素S表示侯选点i和候选点j的连接状态信息,决 在生成如前所述Di、Sa矩阵同时生成遗传算法路径长 定了多机器人系统在候选点上的旋转动作,其取值对应于前度信息矩阵GA。定义G4[GA]1212.,nm为候选点个 述Dis的计算方式: 数。GA矩阵元素GA表示以候选点ⅳ作为遗传算法起始点 (1)直连方式下,San-0,此时多机器人系统在点改变和终止点得到的多机器人系统中心路径长度。 其姿态信息使得杆状零件与点连线方向平行; 取出所有Sa=-1的侯选点对,这些点对都可以作为候选 (2)小幅平移方式下,San=1,此时多机器人系统首先在遗传算法起始点和终止点;再根据迪科斯彻算法判断以上所 点改变其姿态信息使得杆状零件与点连线方向平行,随后有候选点对的连接情况 20-15-10-5051015202530 0-15-10-5051015202530 X (a)多机器人系统整体协作路径示意 (b)单机器人路径示意 图5基于定点转动法的多机器人系统路径规划 刘凵,梁文君:多机器人协作搬运路径规划研究 2010,46(32)201 10 0 15-10-50 15 X (a)多机器人系统整体协作路径示意 (b)单机器人路径示意 图6复杂环境下的基于定点转动-遗传算法的多机器人系统路径规划 (1)若迪科斯彻算法返回确定值,即可以通过其他侯选点结果,进一步提出定点转动-遗传算法这一最终解决方案,以改 连接Sa=-1的点对i,则保持Ds值不变; 进遗传算法的某些固有缺点,使得多机器人系统在规划空间 (2)若迪科斯彻算法返回无穷大值,则这一点对确实无法中大范围通过定点转动法得到协作路径,在特殊窄道环境中 通过其他候选点连接,那么它们就是遗传算法起始点和终止点。通过遗传算法得到协作路径。仿真结果证明,定点转动遺传 使用遗传算法规划出子路径后,能得到GA的值,令Dis=CA。算法在存在窄道环境的稀疏障碍物分布空间中规划多机器人 计算过所有sa,=-l的候选点对后,就确定出了所有遗传协作路径是可行且高效的 算法起点和终点,即确定了需要用遗传算法规划路径的搜索 对多机器人系统协作搬运零件问题进行了描述,提出了 环境子区间。以重新赋值后的D矩阵表示迪科斯彻算法两定点转动遗传算法的最终解决方案。该方案在得到多机器人 点之间距离权重后,得到的多机器人系统协作规划路径即是系统中心的最短路径的同时,实现了单机器人易控制,多机器 最短路径,具有全局最优性。如果迪科斯彻算法最终找不到人系统运动能耗低,算法运算时间短等更奷的指标。算法适 规划路径,则说明起始位姿和目标位姿不可达,即搬运零件冋用于静态环境,在实际应用中需要进一步考虑路径规划的实 题无解。 时性,以及动态环境对路径规划的影响等因素,这些T作还需 定点转动遗传算法的协作路径规划方法具有搜索的完备要进一步研究 性,在遗传算法能找到规划路径的搜索空间中本方法同样有 效但结果更优。 参考文献: 5.,2仿真结果 Il张亚鸣,雷小字,杨胜跃,等多机器人路径规划研究方法J.计算 为了验证算法的有效性,在仿真环境中设计出多种类型的 机应用研究,2008,25(9):2566-2569 窄道,对应前述各St状态的候选点对。以搜索环境出现一段2] Panait L, Luke S Cooperative multi-agent learning: The state of 遗传算法路径的情况为例.即由起点到以GA起始点为临时终 the art[J Autonomous Agents and Multi-Agent Systems, 2005,11 点的第一段区间,和以(A终止点为临时起点到终点的第三段 (3):387-434 区间采用定点转动法得到规划路径;以GA起始点为临时起点[3] Tzafestas c s, Prokopiou P A, Tzafestas S G Path planning and 到以GA终止点为临时终点的第二段区间用遗传算法得到路径, control of a cooperative three robot systen manipulating large 同时,算法规定将GA起始位姿默认为起点位姿,GA终止位姿 objects[J]Journal of Intelligent and Robotic Systems, 1998, 22 默认为终点位姿。多机器人协作系统的整体规划轨迹如图6 (2):99-116 (a)所示,其中的虚线表示杆中心运动轨迹;图6(b所示为位4 Victoria C, Mexico T Cooperative multi-robot box-pushing in a 于杆两端的单机器人各自运动轨迹,以点划线和断点线表示。 cluttered environment[C]/IEEE International Conference on Ro 出仿真结果可以看出,基于定点转动-遗传算法在解决多 botics and Automation California 2008: 514-519 机器人协作搬运问题路径规划上是可行且高效的。 [S]唐振民,赵春霞,杨静宁,等基于动态规划思想的多机器人路径规 划门南京理工大学学报,2003,27(5):610-615 6结语 [6]孙树栋,林茂基于遺传算法的多移动机器人协调路径规划[J.自 动化学报,2000,26(5):672-676 以多机器人系统搬运零件这一实际问题为研究背景,在 ⑦7]刘国栋,谢宏斌,李春光动态环境中基于遗传算法的移动机器人 搬零件时,多机器人系统需要保持一定的空间位姿约束并路径规划方法门机器人,20014):32734 实现避障。为了满足实际需求,提出了多机器人系统协作路8] Cai zi-x in,Peng7 hi-hong Cooperative coevolutionary adaptive 径规划这一研究课题。 genetic algorithm in path planning of cooperative multi-robot 首先按照常规思路采用基于遗传算法的路径规划方法解 systens[J]Journal of IntelligenL and Robotic Systems: Theory 决多机器人协作路径规划问题,为了提高算法效率、优化规划 and Applications, 2002, 33(1): 61-71

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐