刘山;梁文君
【摘 要】针对多机器人协作系统,提出了一种新的混合定点转动和遗传算法的方法,解决其协作路径规划问题.该方法利用遗传算法并行计算、不易陷入局部最优的优点,具备概率上寻全局最优解的能力,同时结合了定点转动法易实现、有效减少单机器人路径浪费的优点.仿真实验结果表明,该规划方法运算速度较快,在得到有效规划路径的同时,也易于实现对单机器人的控制. 【期刊名称】《计算机工程与应用》
【年(卷),期】2010(046)032
【总页数】5页(P197-201)
【关键词】多机器人;协作;路径规划;遗传算法
abp-356【作 者】刘山;梁文君
【作者单位】烧烤车浙江大学工业控制技术国家重点实验室,杭州,310027;浙江大学工业控制技术国家重点实验室,杭州,310027
【正文语种】中 文
【中图分类】TP242
1 引言
随着机器人应用领域和范围的不断扩展，单机器人模式已不再是最为理想的解决方案，而多机器人组成的系统表现更优。与前者相比，多机器人系统具有多方面的优点：（1）对于大型重物的搬运，多个简单机器人组成的协作系统在设计的复杂性和成本等方面都优于能力特别强的单机器人；（2）多机器人系统可以并行地解决问题，这种分散任务的方式大大提高了工作效率；（3）对于多机器人系统，其相互协作还能增加整个系统的冗余度，增强了解决方案的鲁棒性。
虚拟试衣技术
多机器人系统在规划环境下避障避碰和合作搬运物体的路径规划问题一直是近年来多机器人系统的研究热点[1-4]，其解决方案主要包括基于栅格法、人工势场法、遗传算法、最优
控制算法、动态规划算法[5]等规划算法。其中，孙树栋等人[6]提出了基于集中协调思想的混合遗传算法来规划多机器人路径，该方法较好地解决了避障问题，但只能保证到一个比较满意的解而非全局最优解；刘国栋等人[7-8]进一步改进遗传算法，采用实数编码方法及有明确物理意义的适应度函数，加快了算法的实时性和运算精度，但该方法适用于简单环境特殊状态动态规划，不具有普适性。
本文针对实际工业中常有的多机器人协作搬运杆状物体的过程，将多机器人路径规划问题转换为带约束条件的多机器人系统中心的路径规划问题，提出一种简单的基于定点转动-遗传算法的多机器人协作路径规划方法。该方法不仅可以克服遗传算法在复杂环境下路径不平滑、进化效率不高等缺点，而且具备搜索完备性、运算快等优点。
2 问题描述
本文研究的问题是多机器人系统协作搬运刚性杆状物体时的多机器人路径规划问题。在该问题中，一个重要的约束是在搬运过程中，多机器人系统中各单机器人之间的距离需要保持不变。以两个机器人组成的多机器人系统搬运杆状零件为例，在这一搬运问题中，单机器人位于杆状零件两端，其组成的多机器人系统需要保持相对位置不变以夹持零件，这样，
多机器人协作路径规划问题就转化成为平面杆状零件运动规划问题。得到了杆状零件的离散位姿信息，即解决了多机器人系统协作路径规划问题。
规划上述多机器人系统协作路径关键在于确定整条路径上的所有离散点处该系统的位姿信息，从而确定每个机器人的位置点集合以得到单机器人的规划路径轨迹。多机器人系统位姿信息包括位置和姿态两部分，位置信息的变化表示多机器人系统的整体平移，姿态信息的变化表示多机器人系统的整体转动，协作轨迹即由平移和旋转动作共同完成。
为描述算法思路，不失一般性，本文的规划问题为以两个机器人搬运一个杆状零件时的多机器人路径规划；对于多机器人搬运凸多边形物体的问题，可以类似考虑。
此时，杆状零件中点坐标表示多机器人系统的位置信息，杆状零件相对于设定坐标系水平轴的角度表示多机器人系统的姿态信息。因此，得到了杆状零件中心的运动轨迹和杆状零件在轨迹上每一点的角度信息就等于得到了整组多机器人系统协作规划路径，从而可以得出单机器人的规划路径。
因此，多机器人协作路径规划的目标包括以下四个方面：（1）免碰撞；（2）多机器人系
统中心路径最短；（3）多机器人系统姿态变化总量最小，即尽可能地减少姿态变化幅度；（4）多机器人系统姿态变化率最小，即尽可能地减少姿态变化次数。
本文算法基于以上原则设计，在保证算法完备性的基础上争取算法规划协作路径的性能更优。
3 分析基于遗传算法的路径规划
如图1所示，多机器人协作系统位姿信息由三维离散数据（X，Y，C）表示，形成的构形空间，即C空间，是二维平面中物体连续位姿的表达方式。三维数据结构中X、Y的取值范围是整个环境空间的长宽度，C的取值范围则通过设定多机器人系统单位姿态改变量得到[4]。
在上述位姿描述下，多机器人路径规划问题可用遗传算法等计算智能方法求解。因此，首先选用遗传算法这一常规方法求解多机器人系统协作轨迹规划问题，并分析该方法所得结果的缺陷。
pbst
3.1 遗传算法
3.1.1 轨迹编码方式
如图1所示，起始点start为多机器人系统的初始位置和姿态，目标点goal为多机器人系统的目标位置和姿态，它们表示零件的当前状态和需求状态。算法需规划的路径就是在start和goal之间确定遗传进化以得到最优序列坐标集合。由于C作为一个独立的坐标系单独衡量，这里仅对原始平面直角坐标系 XOY进行坐标转换；转换后的坐标系是 X′O′Y′，将 X′轴等分为x1，x2，...，xn，固定横轴变化量来降低单点编码长度。
图1 路径编码示意图
遗传算法中，编码长度和搜索空间很大程度上决定了其计算时间。因此采用简化编码长度，即将路径描述所需的每一个离散三维编码(Xi，Yi，Ci)简化为二维编码，此时优化问题简化为Y′C编码优化问题，编码格式，如表1所示。
表1 路径编码结构?
3.1.2 适应度函数定义
适应度函数是遗传算法收敛和稳定的依据。本算法采用各项评价函数加权求和的常用方法来确定适应度函数。
免碰撞是规划的基本条件，是机器人安全通过工作空间的保证。在路径中不可出现多机器人系统搬运杆状零件位姿状态与障碍物发生碰撞或覆盖其上的情况，因此将碰撞判断分为如下步骤：
（1）判断杆状零件是否与障碍物有重合，即=1，若杆状零件位姿i时位于零件两端的机器人均在障碍物内；
亨润成型机炮筒材质
（2）求得杆状零件所在直线方程；
（3）求得每个障碍物的各边所在直线方程；
（4）根据以上方程组求得障碍物和零件边沿所在直线的所有重合点；
（5）判断杆状零件是否与障碍物有碰撞，即=1，若杆状零件位姿i时位于零件两端的机器人在障碍物j的第k条边上。
综合以上公式可得避障适应度函数为：fcol= α∙fcol1+ β∙fcol2
其中，α、β为两种碰撞形式对应可调适应比例系数。
肉模
算法采用了多机器人系统中心路径最短作为最优路径的标准，但为了避免多机器人系统相邻位姿的变化需要穿越障碍物才能实现的情况，需要进行如下讨论：
（1）对于整条无碰路径：
（2）当整条路径中有相邻位姿变化穿越障碍物时：若位姿i与位姿i+1变化过程穿越障碍物j。
由以上两式可得路径长度适应度函数为：
多机器人系统姿态变化幅度和姿态变化频率两性能指标可用两个适应度函数来表述：
fcri=1，若 Ci+1≠Ci。
由以上各式可得最终适应度函数为：
3.1.3 遗传操作算子定义
初始化种在起始位姿start（y0，c0）和目标位姿（yn，cn）的连线上引入一个[-0.5，0.5]的零均值白噪声并叠加一个[-1，1]的正态分布噪声而随机产生yi，而ci通过在位姿变化连线上叠加[-0.15，0.15]的随机扰动而产生。
图2 简单环境下的基于遗传算法的多机器人系统路径规划
图3 复杂环境下的基于遗传算法的多机器人系统路径规划
交叉操作：采用多点交叉方法，即随机选取一个区域，用交叉后的子代个体代替原种中的父代个体，产生新的种。
变异操作：在新的个体中加入[-3，3]的正态分布白噪声作为y变量的随机扰动，加入位姿最小变化角度2倍的随机噪声作为c变量的随机扰动，构建新的基因以寻最优解。
3.2 算法分析
仿真中取基于较优实验结果的参数如下：初始种规模15，交叉概率0.7，变异概率0.3，
最大子代数500。适应度函数中各参数分别取α=5，β=1，kcol=2 200，kpath=10，kcq=9，kcr=8。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议