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

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

摘要:針對(duì)機(jī)器人作業(yè)單元內(nèi)設(shè)備的布局問(wèn)題，提出了一種基于遺傳算法的優(yōu)化布局方法.引入了工程師的經(jīng)驗(yàn)和知識(shí)描述布局過(guò)程中的作業(yè)單元空間及機(jī)器人運(yùn)動(dòng)學(xué)約束，減小了優(yōu)化空間，提高了算法的收斂速度.基于壓鑄作業(yè)的實(shí)例研究結(jié)果表明了該方法的有效性.該方法已與商業(yè)化的機(jī)器人編程與仿真軟件相結(jié)合，表現(xiàn)出了較高的實(shí)用價(jià)值.關(guān)鍵詞:機(jī)器人;機(jī)器人作業(yè)單元;布局優(yōu)化;遺傳算法;約束Abstract:Thispaperproposedarobotworkcelllayoutoptimizationmethodbasedongeneticalgorithm.Thismethodappliesengineer’sexperienceandknowledgeinroboticmanufacturingsystemtothedescrip-tionofgeometricandkinematicrestrictions，thusreducessearchspace，improvesthecomputationaleffi-ciencyandmakesthelayoutmeettheindustrialrequirementsbetter.Themethodhasbeenembeddedincommercialrobotprogrammingandsimulatingsoftware，andusedsuccessfullyinlayoutdesign.Adie-castapplicationcasevalidatestheeffectivenessofthemethod.Keywords:robotic;robotworkcell;layoutoptimization;geneticalgorithm;constraint布局優(yōu)化問(wèn)題[1]是指給定一個(gè)布局空間和若干待布局物體，將待布局物體合理地?cái)[放在空間中，并滿(mǎn)足必代寫(xiě)論文要的約束，達(dá)到某種最優(yōu)指標(biāo).機(jī)器人作業(yè)單元布局問(wèn)題的復(fù)雜性在于:①在求解算法上，具有NP-完全問(wèn)題的性質(zhì)[2];②布局方案需滿(mǎn)足機(jī)器人運(yùn)動(dòng)學(xué)的要求;③一些周邊設(shè)備與機(jī)器人間的位置和朝向受生產(chǎn)環(huán)境的約束;④布局方案的評(píng)價(jià)沒(méi)有統(tǒng)一的指標(biāo)[3，4].本文利用設(shè)備間的約束條件和工程師經(jīng)驗(yàn)，提出了一種基于遺傳算法的布局優(yōu)化方法，實(shí)現(xiàn)了機(jī)器人作業(yè)單元在三維空間內(nèi)的優(yōu)化布局.本方法減小了優(yōu)化空間，提高了算法的速度，并與國(guó)際上廣泛采用的商業(yè)化機(jī)器人編程與仿真軟件相結(jié)合，可以為工業(yè)應(yīng)用設(shè)計(jì)布局方案.本文通過(guò)以壓鑄任務(wù)為對(duì)象的實(shí)例研究，表明了方法和軟件的有效性.1建模方法及指標(biāo)和約束1.1建模方法建模[5]是優(yōu)化算法的基礎(chǔ).本算法建模的對(duì)象包括機(jī)器人工作空間[6]、各種設(shè)備的三維幾何特征以及機(jī)器人在各種設(shè)備中操作時(shí)末端運(yùn)動(dòng)的路徑.機(jī)器人的工作空間是復(fù)雜的三維空間，往往難以描述.本文針對(duì)工業(yè)機(jī)器人加以簡(jiǎn)化，認(rèn)為工作空間是2個(gè)同球心、不同半徑半球差集的一部分.其中，球心定于機(jī)器人底座的中心.2個(gè)半球的半徑根據(jù)機(jī)器人型號(hào)標(biāo)定.機(jī)器人工作空間如圖1所示.(a)單機(jī)器人(b)2個(gè)機(jī)器人圖1簡(jiǎn)化的機(jī)器人工作空間Fig.1Simplifiedrobotoperationalspace

待布局物體也就是機(jī)器人周邊設(shè)備，其幾何特征用長(zhǎng)方體外包來(lái)描述，朝向用向量表示，如圖2所示.周邊設(shè)備的操作路徑是復(fù)雜三維的空間曲線(xiàn)，可以用折線(xiàn)來(lái)描述.圖2工作臺(tái)和壓鑄機(jī)的建模Fig.2Modelingofstationsanddie-castmachine

周邊設(shè)備與機(jī)器人的相對(duì)位置和姿態(tài)關(guān)系用它們?cè)跈C(jī)器人底座平面的投影來(lái)描述，如圖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)過(guò)設(shè)備中心點(diǎn)的射線(xiàn)與設(shè)備朝向的夾角，逆時(shí)針為正.圖3周邊設(shè)備的位置和姿態(tài)Fig.3Expressionofpositionandposeofperipheralfacility1.2布局指標(biāo)和約束機(jī)器人的操作周期可以反映其工作效率，受機(jī)器人的速度、加速度和末端運(yùn)動(dòng)距離的影響.對(duì)于確定的生產(chǎn)環(huán)境和機(jī)器人型號(hào)來(lái)說(shuō)，機(jī)器人運(yùn)動(dòng)速度、加速度可調(diào)整幅度較小.操作周期主要取決于機(jī)器人末端運(yùn)動(dòng)的距離.該距離其實(shí)也是對(duì)生產(chǎn)工藝流程和設(shè)備布局的反應(yīng)，可以用作布局指標(biāo).周邊設(shè)備在機(jī)器人工作空間內(nèi)布局時(shí)，要滿(mǎn)足下列約束:①機(jī)器人工作空間的約束，即設(shè)備上的操作路徑必須在機(jī)器人工作空間內(nèi);②干涉約束，即各種設(shè)備之間以及設(shè)備與機(jī)器人之間不能發(fā)生干涉;③機(jī)器人和設(shè)備之間相對(duì)位置和姿態(tài)的約束，即根據(jù)生產(chǎn)的要求，某些設(shè)備相對(duì)于機(jī)器人的位置和朝向只可以在一個(gè)受約束的范圍變動(dòng).2布局優(yōu)化算法機(jī)器人作業(yè)單元優(yōu)化布局方法[7]包括編碼/解碼、評(píng)價(jià)、選擇、交叉和變異模塊(見(jiàn)圖4).

(1)編碼方式.本算法中編碼的對(duì)象是待布局物體的模型.基因表示待布物即加工臺(tái)的極坐標(biāo)值和姿態(tài)夾角.染色體由多個(gè)基因組成，代表一個(gè)布局方案.(2)適應(yīng)度函數(shù).根據(jù)布局指標(biāo)，好的布局方案首先要滿(mǎn)足所有周邊設(shè)備的內(nèi)部路徑在機(jī)器人工作空間內(nèi);其次，還要滿(mǎn)足一個(gè)操作周期內(nèi)機(jī)器人運(yùn)動(dòng)路徑較短.適應(yīng)度函數(shù)必須反映這2個(gè)要求.適應(yīng)度函數(shù)設(shè)計(jì)如下:

f=P1∑ni=1∑mj=1kj+P2∑sr=1(c1-Δdr)+P3∑sr=1(c2-Δθr)(1)式中:∑ni=1∑mj=1kj反映了機(jī)器人訪問(wèn)周邊設(shè)備的難易情況;i為周邊設(shè)備的編號(hào);n為周邊設(shè)備的數(shù)量;j為某臺(tái)周邊設(shè)備內(nèi)部路徑上必經(jīng)點(diǎn)的編號(hào);m為這些點(diǎn)的數(shù)量;kj為一個(gè)0/1變量，第j個(gè)必經(jīng)點(diǎn)在機(jī)1698上海交通大學(xué)學(xué)報(bào)第42卷圖4算法結(jié)構(gòu)圖Fig.4Algorithmarchitecture器人工作空間內(nèi)為1，否則，為0(見(jiàn)圖5(a)).∑sr=1(c1-Δdr)反映了周邊設(shè)備擺放的疏密情況;s為路徑總數(shù);Δdr為起始設(shè)備內(nèi)部路徑從終點(diǎn)到下一設(shè)備內(nèi)部路徑起點(diǎn)的距離，表示第r條路徑的長(zhǎng)度(見(jiàn)圖5(b));c1為常數(shù);P1、P2為權(quán)重，取P1>P2(一般取P1是P2的10倍，則能起到較好的效果).引入這樣的權(quán)重可以在保證機(jī)器人容易訪問(wèn)周邊設(shè)備的情況下，再考慮縮短機(jī)器人運(yùn)動(dòng)路徑.P3∑sr=1(c2-Δθr)中P3、c2是常數(shù)，Δθr為2臺(tái)周邊設(shè)備間的夾角(見(jiàn)圖5(c))，其目的是為了防止出現(xiàn)一種較差的布局.這種布局類(lèi)似圖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.5Fitnessfunction圖6一種不合理的布局Fig.6Anunexpectedlayout

(3)選擇規(guī)則.采用輪盤(pán)賭的方法[8]，根據(jù)適應(yīng)度大小確定選擇的概率.(4)交叉和變異.它們都是對(duì)布局方案的改變.交叉是對(duì)2個(gè)布局方案中相同設(shè)備位置和姿態(tài)的交換，發(fā)生概率較高;變異是對(duì)單個(gè)布局方案中某些設(shè)備位置和姿態(tài)的變化調(diào)整，發(fā)生概率較低.變異范圍為一個(gè)扇環(huán)，由平行于機(jī)器人基座底面，距底面為路徑折線(xiàn)折點(diǎn)平均高度的平面截機(jī)器人工作空間得到.這樣取變異范圍能使得變異后設(shè)備的內(nèi)部路徑盡可能在機(jī)器人工作空間內(nèi).(5)收斂準(zhǔn)則.它是進(jìn)化到代數(shù)G的上界或適應(yīng)度函數(shù)滿(mǎn)足如下條件:|f*(G+1)-f*(G)|<σ(2)式中:f*(G)為第G代最好個(gè)體的適應(yīng)度;σ為一個(gè)小整數(shù).(6)干涉檢驗(yàn)和布局調(diào)整.在布局空間中隨機(jī)擺放較多的周邊設(shè)備時(shí)，干涉的解即設(shè)備之間相互發(fā)生碰撞的解占大多數(shù).因此，用干涉檢驗(yàn)[9]和布局調(diào)整的方法把干涉的解排除出遺傳算法的解空間，從而極大地提高遺傳算法的速度.在調(diào)整干涉時(shí)，采用周邊設(shè)備圍繞機(jī)器人中心調(diào)整的方法.這樣使得調(diào)整后的解和調(diào)整前的解比較相近，不會(huì)破壞遺傳算法的搜索特性，也不會(huì)使優(yōu)化陷于局部最優(yōu).3實(shí)例和結(jié)果分析實(shí)例的前提條件如下:①機(jī)器人是一臺(tái)底座固1699第10期項(xiàng)彬彬，等:基于遺傳算法的機(jī)器人作業(yè)單元布局優(yōu)化

置固定)→5→2.

算法遺傳進(jìn)化367代時(shí)，適應(yīng)度滿(mǎn)足收斂準(zhǔn)則，算法結(jié)束運(yùn)算.種群中最優(yōu)個(gè)體的收斂情況以及布局結(jié)果如圖10所示.(a)適應(yīng)度的收斂過(guò)程(b)布局優(yōu)化結(jié)果圖10實(shí)例3適應(yīng)度的收斂過(guò)程及布局優(yōu)化結(jié)果Fig.10Fitnessconvergenceandoptimizedlayoutincase34結(jié)語(yǔ)針對(duì)機(jī)器人作業(yè)單元的布局問(wèn)題，本文提出的布局優(yōu)化方法結(jié)合了遺傳算法以及工程師經(jīng)驗(yàn)與知識(shí)，減小了優(yōu)化空間，提高了算法的收斂速度，生成的布局更符合工業(yè)生產(chǎn)的要求.基于壓鑄作業(yè)的實(shí)例結(jié)果表明了該方法的有效性.該方法已經(jīng)和ABB公司的工業(yè)機(jī)器人編程與仿真軟件相結(jié)合，為機(jī)器人作業(yè)單元的布局提供方便易用的優(yōu)化工具.

另外，還有待于進(jìn)一步研究以下問(wèn)題:一方面，機(jī)器人布局優(yōu)化是帶約束的優(yōu)化問(wèn)題，尋找更系統(tǒng)化的約束定義和描述方法，具有很強(qiáng)的應(yīng)用價(jià)值;另一方面，需要尋找更精確、高效的布局評(píng)價(jià)函數(shù)，來(lái)兼顧優(yōu)化結(jié)果的最優(yōu)性和提高優(yōu)化算法的計(jì)算效率.參考文獻(xiàn):[1]查建中，唐曉君，陸一平.布局及布置設(shè)計(jì)問(wèn)題求解自動(dòng)化的理論與方法綜述[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14(8):705-712.CHAJian-zhong，TANGXiao-jun，LUYi-ping.Sur-veyonpackingproblems[J].JournalofComputer-AidedDesign&ComputerGraphics，2002，14(8):705-712.[2]GareyMR，JohnsonDS.Computersandintractabili-ty:AguidetothetheoryofNP-completeness[M].NewYork:W.H.FreemanandCompany，1979.[3]NehmeD，McKiddieR.Evaluatingworkcelllayouts[C]//ProceedingsofIEEE/SEMI1995AdvancedSemi-conductorManufacturingConferenceandWorkshop.Cambridge，MA，USA:IEEE，1995:111-114.[4]LuethTC.Automatedplanningofrobotworkcelllay-outs[C]//Proceedingsof1992IEEEInternationalCo