基于遗传算法的机器人作业单元布局优化

摘　要:针对机器人作业单元内设备的布局问题,提出了一种基于遗传算法的优化布局方法.引入了工程师的经验和知识描述布局过程中的作业单元空间及机器人运动学约束,减小了优化空间,提高了算法的收敛速度.基于压铸作业的实例研究结果表明了该方法的有效性.该方法已与商业化的机器人编程与仿真软件相结合,表现出了较高的实用价值.

关键词:机器人;机器人作业单元;布局优化;遗传算法;约束

Abstract:This paper proposed a robot workcell layout optimization method based on genetic algorithm.This method applies engineer’s experience and knowledge in robotic manufacturing system to the descrip-tion of geometric and kinematic restrictions, thus reduces search space, improves the computational effi-ciency and makes the layout meet the industrial requirements better. The method has been embedded incommercial robot programming and simulating software, and used successfully in layout design. A die-castapplication case validates the effectiveness of the method.

Key words:robotic; robot workcell; layout optimization; genetic algorithm; constraint　　

布局优化问题[1]是指给定一个布局空间和若干待布局物体,将待布局物体合理地摆放在空间中,并满足必代写论文要的约束,达到某种最优指标.机器人作业单元布局问题的复杂性在于:①在求解算法上,具有NP-完全问题的性质[2];②布局方案需满足机器人运动学的要求;③一些周边设备与机器人间的位置和朝向受生产环境的约束;④布局方案的评价没有统一的指标[3,4].本文利用设备间的约束条件和工程师经验,提出了一种基于遗传算法的布局优化方法,实现了机器人作业单元在三维空间内的优化布局.本方法减小了优化空间,提高了算法的速度,并与国际上广泛采用的商业化机器人编程与仿真软件相结合,可以为工业应用设计布局方案.本文通过以压铸任务为对象的实例研究,表明了方法和软件的有效性.

1　建模方法及指标和约束1.1　建模方法建模[5]是优化算法的基础.本算法建模的对象包括机器人工作空间[6]、各种设备的三维几何特征以及机器人在各种设备中操作时末端运动的路径.机器人的工作空间是复杂的三维空间,往往难以描述.本文针对工业机器人加以简化,认为工作空间是2个同球心、不同半径半球差集的一部分.其中,球心定于机器人底座的中心.2个半球的半径根据机器人型号标定.机器人工作空间如图1所示.(a)单机器人(b) 2个机器人图1　简化的机器人工作空间Fig.1　Simplified robot operational space　　待布局物体也就是机器人周边设备,其几何特征用长方体外包来描述,朝向用向量表示,如图2所示.周边设备的操作路径是复杂三维的空间曲线,可以用折线来描述.图2　工作台和压铸机的建模Fig.2　Modeling of stations and die-cast machine　　周边设备与机器人的相对位置和姿态关系用它们在机器人底座平面的投影来描述,如图3所示.世界坐标系根据机器人确定,采用极坐标(极径ρ,极角θ).机器人处于初始姿态时,底座的中心位于坐标系的原点,底座前端朝向极轴正方向.周边设备的位置用该设备中心的极坐标值表示,姿态用角度φ表示,φ是从坐标系原点过设备中心点的射线与设备朝向的夹角,逆时针为正.图3　周边设备的位置和姿态Fig.3　Expression of position and pose of peripheral facility1.2　布局指标和约束机器人的操作周期可以反映其工作效率,受机器人的速度、加速度和末端运动距离的影响.对于确定的生产环境和机器人型号来说,机器人运动速度、加速度可调整幅度较小.操作周期主要取决于机器人末端运动的距离.该距离其实也是对生产工艺流程和设备布局的反应,可以用作布局指标.周边设备在机器人工作空间内布局时,要满足下列约束:①机器人工作空间的约束,即设备上的操作路径必须在机器人工作空间内;②干涉约束,即各种设备之间以及设备与机器人之间不能发生干涉;③机器人和设备之间相对位置和姿态的约束,即根据生产的要求,某些设备相对于机器人的位置和朝向只可以在一个受约束的范围变动.

2　布局优化算法机器人作业单元优化布局方法[7]包括编码/解码、评价、选择、交叉和变异模块(见图4).　　(1)编码方式.本算法中编码的对象是待布局物体的模型.基因表示待布物即加工台的极坐标值和姿态夹角.染色体由多个基因组成,代表一个布局方案.(2)适应度函数.根据布局指标,好的布局方案首先要满足所有周边设备的内部路径在机器人工作空间内;其次,还要满足一个操作周期内机器人运动路径较短.适应度函数必须反映这2个要求.适应度函数设计如下:　　　f = P1∑ni=1∑mj=1kj+P2∑sr=1(c1-Δdr)+P3∑sr=1(c2-Δθr) (1)式中:∑ni=1∑mj=1kj反映了机器人访问周边设备的难易情况;i为周边设备的编号;n为周边设备的数量;j为某台周边设备内部路径上必经点的编号;m为这些点的数量;kj为一个0/1变量,第j个必经点在机1698上　海　交　通　大　学　学　报第42卷　图4　算法结构图Fig.4　Algorithm architecture器人工作空间内为1,否则,为0 (见图5(a)).∑sr=1(c1-Δdr)反映了周边设备摆放的疏密情况;s为路径总数;Δdr为起始设备内部路径从终点到下一设备内部路径起点的距离,表示第r条路径的长度(见图5(b));c1为常数;P1、P2为权重,取P1>P2(一般取P1是P2的10倍,则能起到较好的效果).引入这样的权重可以在保证机器人容易访问周边设备的情况下,再考虑缩短机器人运动路径.P3∑sr=1(c2-Δθr)中P3、c2是常数,Δθr为2台周边设备间的夹角(见图5(c)),其目的是为了防止出现一种较差的布局.这种布局类似图6所示的情形,周边设备靠近机器人不可达的区域.(a)第1项(b)第2项(c)第3项图5　适应度函数式(1)中各项图示Fig.5　Fitness function图6　一种不合理的布局Fig.6　An unexpected layout　　(3)选择规则.采用轮盘赌的方法[8],根据适应度大小确定选择的概率.(4)交叉和变异.它们都是对布局方案的改变.交叉是对2个布局方案中相同设备位置和姿态的交换,发生概率较高;变异是对单个布局方案中某些设备位置和姿态的变化调整,发生概率较低.变异范围为一个扇环,由平行于机器人基座底面,距底面为路径折线折点平均高度的平面截机器人工作空间得到.这样取变异范围能使得变异后设备的内部路径尽可能在机器人工作空间内.(5)收敛准则.它是进化到代数G的上界或适应度函数满足如下条件:| f*(G+1)-f*(G) |<σ(2)式中:f*(G)为第G代最好个体的适应度;σ为一个小整数.(6)干涉检验和布局调整.在布局空间中随机摆放较多的周边设备时,干涉的解即设备之间相互发生碰撞的解占大多数.因此,用干涉检验[9]和布局调整的方法把干涉的解排除出遗传算法的解空间,从而极大地提高遗传算法的速度.在调整干涉时,采用周边设备围绕机器人中心调整的方法.这样使得调整后的解和调整前的解比较相近,不会破坏遗传算法的搜索特性,也不会使优化陷于局部最优.

3　实例和结果分析实例的前提条件如下:①机器人是一台底座固1699　第10期项彬彬,等:基于遗传算法的机器人作业单元布局优化　　置固定)→5→2.　　算法遗传进化367代时,适应度满足收敛准则,算法结束运算.种群中最优个体的收敛情况以及布局结果如图10所示.(a)适应度的收敛过程(b)布局优化结果图10　实例3适应度的收敛过程及布局优化结果Fig.10　Fitness convergence and optimized layout in case 34　结　语针对机器人作业单元的布局问题,本文提出的布局优化方法结合了遗传算法以及工程师经验与知识,减小了优化空间,提高了算法的收敛速度,生成的布局更符合工业生产的要求.基于压铸作业的实例结果表明了该方法的有效性.该方法已经和ABB公司的工业机器人编程与仿真软件相结合,为机器人作业单元的布局提供方便易用的优化工具.　　另外,还有待于进一步研究以下问题:一方面,机器人布局优化是带约束的优化问题,寻找更系统化的约束定义和描述方法,具有很强的应用价值;另一方面,需要寻找更精确、高效的布局评价函数,来兼顾优化结果的最优性和提高优化算法的计算效率.

参考文献:

[1]　查建中,唐晓君,陆一平.布局及布置设计问题求解自动化的理论与方法综述[J].计算机辅助设计与图形学学报, 2002, 14 (8): 705-712.　 　CHA Jian-zhong, TANG Xiao-jun, LU Yi-ping. Sur-vey on packing problems [J].Journal of Computer-Aided Design & Computer Graphics, 2002, 14 (8):705-712.

[2]　Garey M R, Johnson D S. Computers and intractabili-ty: A guide to the theory of NP-completeness [M].New York: W. H. Freeman and Company, 1979.

[3]　Nehme D, McKiddie R. Evaluating workcell layouts[C]//Proceedings of IEEE/SEMI 1995 Advanced Semi-conductor Manufacturing Conference and Workshop.Cambridge, MA, USA: IEEE, 1995: 111-114.

[4]　Lueth T C. Automated planning of robot workcell lay-outs[C]//Proceedings of 1992 IEEE International Con-ference on Robotics and Automation.Nice, France:IEEE, 1992: 1103-1108.

[5]　Govindaraj S, Doty K L. Manufacturing workcellmodelling and task facility[C]//IEEE Conference Pro-ceedings of Southeastcon’88.Knoxville, TN, USA:IEEE, 1988: 492-496.