多目標優(yōu)化在路徑優(yōu)化中的應用

第31卷第4期計算機仿真2014年4月文章編號:1006 -9348(2014)04 -0364 -05多目標優(yōu)化在路徑優(yōu)化中的應用梁靜',宋慧',瞿博陽(yáng)2(1.鄭州大學(xué)電氣工程學(xué)院,河南鄭州450001 ;2.中原工學(xué)院電子信息學(xué)院,河南鄭州450007)摘要:在移動(dòng)機器人路徑規劃問(wèn)題的研究中,路徑規劃的實(shí)質(zhì)是機器人按照- -定的技術(shù)指標找到一條從起 點(diǎn)到終點(diǎn)與障礙物無(wú)碰擅的最短路徑。由于路徑長(cháng)度和安全性指標是相互矛盾的兩個(gè)技術(shù)指標,大多數現存算法在把它們作為單目標優(yōu)化時(shí)容易陷人局部最優(yōu),用多目標優(yōu)化中的帕累托最優(yōu)則能夠很好地平衡和解決這兩個(gè)目標不同資源分配下的組合情況。用貝塞爾曲線(xiàn)來(lái)描述路徑,用帕累托最優(yōu)解決路徑長(cháng)度和安全性指標之間的共存問(wèn)題。實(shí)驗結果表明,比起單目標處理,多目標優(yōu)化在解決路徑優(yōu)化問(wèn)題中路徑長(cháng)度及安全性指標時(shí)較穩定,能夠找到滿(mǎn)足條件的更短路徑，并且帕累托最優(yōu)能夠很好地解決不兼容目標之間的共存問(wèn)題,找到不同安全性指標下優(yōu)化最短路徑。關(guān)鍵詞:貝塞爾曲線(xiàn);多目標優(yōu)化;帕累托最優(yōu)中圖分類(lèi)號:TP18文獻標識碼:AApplication of Multi - objective Optimizer in Path PlanningLIANG Jing'，SONG Hui' ,QU Bo - yang2(1. School of Electrical Engineering, Zhengzhou University , Zhengzhou Henan 450001 , China;2. School of Electric and Information Engineering, Zhongyuan University of Technology,Zhengzhou Henan 450007 , China)ABSTRACT :The essence of robotic path planning is to fnd a cllision - free path from the start location to the targetlocation in an environment with obstacles which satisfy certain optimum criteria. Criteria of path length and securityare contradictory isues in path planning problem, most existing algorithms regard it as a single objective problem andare easily to be trapped into local optima while Pareto optimality in multi - objective optimizer can balance and solvethe combination well under different resource assigned of two goals. In the paper, Bezier curve was used to describepath in this task, and Pareto optimality was utilized to solve the coexistence of path length and security. The resultshows that compared with single - objective optimizer, the multi - objective optimizer is more stable in achieving thecriteria of path length and security and can find the shortest path which satisfies certain conditions. The Pareto opti-mality can effectively solve the coexistence problem of incompatible objectives and find the shortest path under differ-ent safety criteria.KEYWORDS: Bezier curve; Muti - objective optimizer; Pareto optimality最短,機器人消耗能量最低,花費時(shí)間最少,安全性及路徑光1引言滑度等技術(shù)指標"。但是這些指標在作為單目標優(yōu)化處理路徑規劃在移動(dòng)機器人導航中占有很重要的位置,表現時(shí)容易陷局部最優(yōu),因此路徑優(yōu)化問(wèn)題通常被當作很難發(fā)現為機器人按某--性能指標找到--條從起點(diǎn)到終點(diǎn)的和障礙最優(yōu)解的具有多個(gè)目標的NP完全問(wèn)題(2] ,即大多采用多目物無(wú)接觸最優(yōu)或者接近最優(yōu)路徑。路徑問(wèn)題通常涉及路徑標優(yōu)化來(lái)進(jìn)行處理。與單目標優(yōu)化問(wèn)題不同,多目標優(yōu)化向題的目標函數是大于等于二的,大多數專(zhuān)家學(xué)者用保持非支基金項目:國家自然科學(xué)基金項目(60905039) ;中國博士后科學(xué)基金配解集,同時(shí)將種群朝著(zhù)非支配解集移動(dòng)并最終收斂于帕累特別資助項目(2012750639);教育部高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項科研托曲面的中國煤化工基金( 2010000 ;河南省科技攻關(guān)項目(132102210521)本文中CNMH G'題，需要優(yōu)化的目標收稿日期:2013 -07-26修回日期:2013-08 -05是路徑長(cháng)度相女王比伯你，很亞然，這是兩個(gè)相互矛盾的概一364一念,這兩個(gè)指標是不能同時(shí)滿(mǎn)足的,那么就需要- - 些方法來(lái)其中，u∈[0,1],PO、P分別表示起點(diǎn)和終點(diǎn),i表示產(chǎn)生路滿(mǎn)足不同使用者的需求。多目標優(yōu)化能夠實(shí)現同時(shí)對多個(gè)徑的曲線(xiàn)段。目標的優(yōu)化,并對這些目標進(jìn)行協(xié)調，設計者選擇的算法每安全性指標指的是機器人要實(shí)現和障礙物之間無(wú)碰撞。運行一次都會(huì )產(chǎn)生一組Pareto 最優(yōu)解,使用者可以根據自己用圓來(lái)表示障礙物,那么圓的半徑就是用來(lái)評價(jià)安全性指標對優(yōu)化指標的要求來(lái)選擇合適的解。的重要因素,用R表示。用d,表示曲線(xiàn)上的點(diǎn)與障礙物j之從20世紀70年代中期,機器人路徑規劃問(wèn)題就以多種間的最短距離,安全性指標的求解如下:形式被研究。傳統的一些方法如圖搜索法,人工勢場(chǎng)法,柵forj=1:k格法等由于搜索效率比較低而逐漸被淘汰,遺傳算法、蟻群fori=2:(L-1)算法、免疫算法、神經(jīng)網(wǎng)絡(luò )等智能算法得到了一些改進(jìn)而被dis(i-1) = sqr(sum((P,(i)應用到路徑優(yōu)化中[41。- circle(j,1))~2 +例如裴振奎等提出了改變變異操作提高差分算法在優(yōu)(P,(i) -circle(j,2))2));化多目標VRP問(wèn)題(優(yōu)化目標:路徑長(cháng)度和客戶(hù)所需貨物重end物的車(chē)輛)中的應用'5] ,申曉寧等用引用了刪除,修復和平滑d(j) = min(dis-R)算子提高了多目標路徑優(yōu)化(優(yōu)化目標:路徑長(cháng)度,路徑安全性和平滑性)中遺傳算法的搜索效率低并防止出現早熟現fy= - min(d)(2)象[6] ,王振華等采用增強全局搜索能力的改進(jìn)蟻群算法解決其中,K表示障礙物的個(gè)數,circle表示障礙物的圓心坐標，了多目標無(wú)人機路徑規劃(優(yōu)化目標:路徑長(cháng)度和無(wú)人機選P.P,表示曲線(xiàn)上每個(gè)點(diǎn)的坐標,L = length(P.)表示曲線(xiàn)上擇該路徑時(shí)所受到的威脅強度)問(wèn)題[7] , Masehian等提出了用改進(jìn)粒子群優(yōu)化算法解決多目標路徑優(yōu)化(優(yōu)化目標:最點(diǎn)的個(gè)數fw表示安全性指標,可以看出,當機器人為安全短路徑和路徑光滑性)問(wèn)題[8] ,這些研究者及其它- -些沒(méi)有情況下行駛,其值為負值;當機器人與障礙物相撞情況下,其提到的等在多目標路徑規劃中都做出了自己的成就，但由于值為正值。各個(gè)研究者在研究路徑問(wèn)題時(shí)設置的場(chǎng)景、障礙物的方式或路徑規劃描述的是在起點(diǎn)和終點(diǎn)已知的情況下,找到- -者用帕累托最優(yōu)表示的目標不同,因此無(wú)法對不同研究者進(jìn)個(gè)從起點(diǎn)到終點(diǎn)的和障礙物無(wú)碰撞的路徑。用fmnmn 描述路行對比。徑長(cháng)度,表示方式如下: .本文采用克服了傳統粒子群優(yōu)化算法易于收斂和早熟fmgu=sum(sqr((P.(2:L) -P,(1:L-1))). ^2+(P,現象缺點(diǎn)的動(dòng)態(tài)多組群粒子群優(yōu)化算法,結合本文中要用到(2:L) -P,(1:L-1))).2))(3)的多目標優(yōu)化思想來(lái)解決路徑優(yōu)化問(wèn)題(多目標動(dòng)態(tài)多組群2.2約束處理粒子群優(yōu)化算法,簡(jiǎn)稱(chēng)MO - DMS- PS0)。同時(shí),用三次在優(yōu)化計算領(lǐng)域,很多問(wèn)題被一些因素( 例如:物理,地Bezier 曲線(xiàn)來(lái)描述路徑,對技術(shù)指標路徑長(cháng)度和安全性進(jìn)行理等其它限制條件)所約束著(zhù)。- -般情況下,這類(lèi)問(wèn)題可以?xún)?yōu)化。實(shí)驗結果表明:動(dòng)態(tài)多組群粒子群優(yōu)化算法能夠很好歸納如下":的解決路徑優(yōu)化問(wèn)題, Pareto最優(yōu)能夠很好的表示相互矛盾最小化的目標之間的共存關(guān)系能夠在不同組合的優(yōu)化指標下尋求f(x),x= [x,*..*n](4)與障礙物無(wú)碰撞的最優(yōu)路線(xiàn)。滿(mǎn)足h,(x)≤0,i = 1,.,.,p;2問(wèn)題描述(5)2.1技術(shù)指標g;(x) =0,j =p+1,"",m在機器人路徑規劃中,技術(shù)指標(路徑最短、安全性、時(shí)其中x∈[xmn,x..]" ,p是不等式約束的個(gè)數,(m-p)是等間最短路徑光滑性等)是- - 個(gè)非常重要的評價(jià)因素。接下式約束的個(gè)數,為了簡(jiǎn)化問(wèn)題，所有的等式約束均可以轉化來(lái)要討論的技術(shù)性指標是安全性和最短路徑指標，依然采用為如下不等式約東:Beier曲線(xiàn)911(]來(lái)描述路徑,曲線(xiàn)的參數方程為:|g;(x)|-s≤0(6)(P。(1-u)3 +3P"u(1-u)2+其中8是允許的誤差,然后所有的約束問(wèn)題就可以被定3Pu2(1-u) +Pju',i=1義為:P(u) =.P5~'(1-u)3 +3(2P5-1 -P:-')u(1-u)2 +f(x),x= [*1.*](7)3P%u2(1-u) +PJu2,1e3.1動(dòng)態(tài)多組群粒子群優(yōu)化算法fne(x) >&nwe(x) > e&fne(x.)