基于遺傳算法機(jī)器人作業(yè)單元布局優(yōu)化

1、基于遺傳算法機(jī)器人作業(yè)單元布局優(yōu)化    摘要:針對機(jī)器人作業(yè)單元內(nèi)設(shè)備的布局問題,提出了一種基于遺傳算法的優(yōu)化布局方法.引入了工程師的經(jīng)驗(yàn)和知識描述布局過程中的作業(yè)單元空間及機(jī)器人運(yùn)動學(xué)約束,減小了優(yōu)化空間,提高了算法的收斂速度.基于壓鑄作業(yè)的實(shí)例研究結(jié)果表明了該方法的有效性.該方法已與商業(yè)化的機(jī)器人編程與仿真軟件相結(jié)合,表現(xiàn)出了較高的實(shí)用價(jià)值.     關(guān)鍵詞:機(jī)器人;機(jī)器人作業(yè)單元;布局優(yōu)化;遺傳算法;約束 Abstract:This paper proposed a robot workcell layout opt

2、imization method based on genetic algorithm.This method applies engineers 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 r

3、equirements 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 al

4、gorithm; constraint 布局優(yōu)化問題1是指給定一個布局空間和若干待布局物體,將待布局物體合理地?cái)[放在空間中,并滿足必寫作論文要的約束,達(dá)到某種最優(yōu)指標(biāo).機(jī)器人作業(yè)單元布局問題的復(fù)雜性在于:在求解算法上,具有NP-完全問題的性質(zhì)2;布局方案需滿足機(jī)器人運(yùn)動學(xué)的要求;一些周邊設(shè)備與機(jī)器人間的位置和朝向受生產(chǎn)環(huán)境的約束;布局方案的評價(jià)沒有統(tǒng)一的指標(biāo)3,4.本文利用設(shè)備間的約束條件和工程師經(jīng)驗(yàn),提出了一種基于遺傳算法的布局優(yōu)化方法,實(shí)現(xiàn)了機(jī)器人作業(yè)單元在三維空間內(nèi)的優(yōu)化布局.本方法減小了優(yōu)化空間,提高了算法的速度,并與國際上廣泛采用的商業(yè)化機(jī)器人編程與仿真軟件相結(jié)合,可以為工業(yè)應(yīng)用設(shè)計(jì)

5、布局方案.本文通過以壓鑄任務(wù)為對象的實(shí)例研究,表明了方法和軟件的有效性. 1建模方法及指標(biāo)和約束1.1建模方法建模5是優(yōu)化算法的基礎(chǔ).本算法建模的對象包括機(jī)器人工作空間6、各種設(shè)備的三維幾何特征以及機(jī)器人在各種設(shè)備中操作時(shí)末端運(yùn)動的路徑.機(jī)器人的工作空間是復(fù)雜的三維空間,往往難以描述.本文針對工業(yè)機(jī)器人加以簡化,認(rèn)為工作空間是2個同球心、不同半徑半球差集的一部分.其中,球心定于機(jī)器人底座的中心.2個半球的半徑根據(jù)機(jī)器人型號標(biāo)定.機(jī)器人工作空間如圖1所示.(a)單機(jī)器人(b) 2個機(jī)器人圖1簡化的機(jī)器人工作空間Fig.1Simplified robot operational space待布局物

6、體也就是機(jī)器人周邊設(shè)備,其幾何特征用長方體外包來描述,朝向用向量表示,如圖2所示.周邊設(shè)備的操作路徑是復(fù)雜三維的空間曲線,可以用折線來描述.圖2工作臺和壓鑄機(jī)的建模Fig.2Modeling of stations and die-cast machine周邊設(shè)備與機(jī)器人的相對位置和姿態(tài)關(guān)系用它們在機(jī)器人底座平面的投影來描述,如圖3所示.世界坐標(biāo)系根據(jù)機(jī)器人確定,采用極坐標(biāo)(極徑,極角).機(jī)器人處于初始姿態(tài)時(shí),底座的中心位于坐標(biāo)系的原點(diǎn),底座前端朝向極軸正方向.周邊設(shè)備的位置用該設(shè)備中心的極坐標(biāo)值表示,姿態(tài)用角度表示,是從坐標(biāo)系原點(diǎn)過設(shè)備中心點(diǎn)的射線與設(shè)備朝向的夾角,逆時(shí)針為正.圖3周邊設(shè)備的

7、位置和姿態(tài)Fig.3Expression of position and pose of peripheral facility1.2布局指標(biāo)和約束機(jī)器人的操作周期可以反映其工作效率,受機(jī)器人的速度、加速度和末端運(yùn)動距離的影響.對于確定的生產(chǎn)環(huán)境和機(jī)器人型號來說,機(jī)器人運(yùn)動速度、加速度可調(diào)整幅度較小.操作周期主要取決于機(jī)器人末端運(yùn)動的距離.該距離其實(shí)也是對生產(chǎn)工藝流程和設(shè)備布局的反應(yīng),可以用作布局指標(biāo).周邊設(shè)備在機(jī)器人工作空間內(nèi)布局時(shí),要滿足下列約束:機(jī)器人工作空間的約束,即設(shè)備上的操作路徑必須在機(jī)器人工作空間內(nèi);干涉約束,即各種設(shè)備之間以及設(shè)備與機(jī)器人之間不能發(fā)生干涉;機(jī)器人和設(shè)備之間相對位

8、置和姿態(tài)的約束,即根據(jù)生產(chǎn)的要求,某些設(shè)備相對于機(jī)器人的位置和朝向只可以在一個受約束的范圍變動. 2布局優(yōu)化算法機(jī)器人作業(yè)單元優(yōu)化布局方法7包括編碼/解碼、評價(jià)、選擇、交叉和變異模塊(見圖4).(1)編碼方式.本算法中編碼的對象是待布局物體的模型.基因表示待布物即加工臺的極坐標(biāo)值和姿態(tài)夾角.染色體由多個基因組成,代表一個布局方案.(2)適應(yīng)度函數(shù).根據(jù)布局指標(biāo),好的布局方案首先要滿足所有周邊設(shè)備的內(nèi)部路徑在機(jī)器人工作空間內(nèi);其次,還要滿足一個操作周期內(nèi)機(jī)器人運(yùn)動路徑較短.適應(yīng)度函數(shù)必須反映這2個要求.適應(yīng)度函數(shù)設(shè)計(jì)如下:f = P1ni=1mj=1kj+P2sr=1(c1-dr)+P3sr=1

9、(c2-r) (1)式中:ni=1mj=1kj反映了機(jī)器人訪問周邊設(shè)備的難易情況;i為周邊設(shè)備的編號;n為周邊設(shè)備的數(shù)量;j為某臺周邊設(shè)備內(nèi)部路徑上必經(jīng)點(diǎn)的編號;m為這些點(diǎn)的數(shù)量;kj為一個0/1變量,第j個必經(jīng)點(diǎn)在機(jī)1698上海交通大學(xué)學(xué)報(bào)第42卷圖4算法結(jié)構(gòu)圖Fig.4Algorithm architecture器人工作空間內(nèi)為1,否則,為0 (見圖5(a).sr=1(c1-dr)反映了周邊設(shè)備擺放的疏密情況;s為路徑總數(shù);dr為起始設(shè)備內(nèi)部路徑從終點(diǎn)到下一設(shè)備內(nèi)部路徑起點(diǎn)的距離,表示第r條路徑的長度(見圖5(b);c1為常數(shù);P1、P2為權(quán)重,取P1>P2(一般取P1是P2的10倍

10、,則能起到較好的效果).引入這樣的權(quán)重可以在保證機(jī)器人容易訪問周邊設(shè)備的情況下,再考慮縮短機(jī)器人運(yùn)動路徑.P3sr=1(c2-r)中P3、c2是常數(shù),r為2臺周邊設(shè)備間的夾角(見圖5(c),其目的是為了防止出現(xiàn)一種較差的布局.這種布局類似圖6所示的情形,周邊設(shè)備靠近機(jī)器人不可達(dá)的區(qū)域.(a)第1項(xiàng)(b)第2項(xiàng)(c)第3項(xiàng)圖5適應(yīng)度函數(shù)式(1)中各項(xiàng)圖示Fig.5Fitness function圖6一種不合理的布局Fig.6An unexpected layout(3)選擇規(guī)則.采用輪盤賭的方法8,根據(jù)適應(yīng)度大小確定選擇的概率.(4)交叉和變異.它們都是對布局方案的改變.交叉是對2個布局方案中相

11、同設(shè)備位置和姿態(tài)的交換,發(fā)生概率較高;變異是對單個布局方案中某些設(shè)備位置和姿態(tài)的變化調(diào)整,發(fā)生概率較低.變異范圍為一個扇環(huán),由平行于機(jī)器人基座底面,距底面為路徑折線折點(diǎn)平均高度的平面截機(jī)器人工作空間得到.這樣取變異范圍能使得變異后設(shè)備的內(nèi)部路徑盡可能在機(jī)器人工作空間內(nèi).(5)收斂準(zhǔn)則.它是進(jìn)化到代數(shù)G的上界或適應(yīng)度函數(shù)滿足如下條件:| f*(G+1)-f*(G) |<(2)式中:f*(G)為第G代最好個體的適應(yīng)度;為一個小整數(shù).(6)干涉檢驗(yàn)和布局調(diào)整.在布局空間中隨機(jī)擺放較多的周邊設(shè)備時(shí),干涉的解即設(shè)備之間相互發(fā)生碰撞的解占大多數(shù).因此,用干涉檢驗(yàn)9和布局調(diào)整的方法把干涉的解排除出遺傳

12、算法的解空間,從而極大地提高遺傳算法的速度.在調(diào)整干涉時(shí),采用周邊設(shè)備圍繞機(jī)器人中心調(diào)整的方法.這樣使得調(diào)整后的解和調(diào)整前的解比較相近,不會破壞遺傳算法的搜索特性,也不會使優(yōu)化陷于局部最優(yōu).3實(shí)例和結(jié)果分析實(shí)例的前提條件如下:機(jī)器人是一臺底座固1699第10期項(xiàng)彬彬,等:基于遺傳算法的機(jī)器人作業(yè)單元布局優(yōu)化置固定)52.算法遺傳進(jìn)化367代時(shí),適應(yīng)度滿足收斂準(zhǔn)則,算法結(jié)束運(yùn)算.種群中最優(yōu)個體的收斂情況以及布局結(jié)果如圖10所示.(a)適應(yīng)度的收斂過程(b)布局優(yōu)化結(jié)果圖10實(shí)例3適應(yīng)度的收斂過程及布局優(yōu)化結(jié)果Fig.10Fitness convergence and optimized layo

13、ut in case 34結(jié)語針對機(jī)器人作業(yè)單元的布局問題,本文提出的布局優(yōu)化方法結(jié)合了遺傳算法以及工程師經(jīng)驗(yàn)與知識,減小了優(yōu)化空間,提高了算法的收斂速度,生成的布局更符合工業(yè)生產(chǎn)的要求.基于壓鑄作業(yè)的實(shí)例結(jié)果表明了該方法的有效性.該方法已經(jīng)和ABB公司的工業(yè)機(jī)器人編程與仿真軟件相結(jié)合,為機(jī)器人作業(yè)單元的布局提供方便易用的優(yōu)化工具.另外,還有待于進(jìn)一步研究以下問題:一方面,機(jī)器人布局優(yōu)化是帶約束的優(yōu)化問題,尋找更系統(tǒng)化的約束定義和描述方法,具有很強(qiáng)的應(yīng)用價(jià)值;另一方面,需要尋找更精確、高效的布局評價(jià)函數(shù),來兼顧優(yōu)化結(jié)果的最優(yōu)性和提高優(yōu)化算法的計(jì)算效率. 參考文獻(xiàn): 1查建中,唐曉君,陸一平.布

14、局及布置設(shè)計(jì)問題求解自動化的理論與方法綜述J.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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. 2Garey M R, Johnson D S. Computers and intractabili-ty: A guide to the theory of NP-co

15、mpleteness M.New York: W. H. Freeman and Company, 1979. 3Nehme D, McKiddie R. Evaluating workcell layoutsC/Proceedings of IEEE/SEMI 1995 Advanced Semi-conductor Manufacturing Conference and Workshop.Cambridge, MA, USA: IEEE, 1995: 111-114. 4Lueth T C. Automated planning of robot workcell lay-outsC/Proceedings of 1992 IEEE International