第31卷第4期計(jì)算機(jī)仿真2014年4月文章編號:1006 -9348(2014)04 -0364 -05多目標(biāo)優(yōu)化在路徑優(yōu)化中的應(yīng)用梁靜',宋慧',瞿博陽2(1.鄭州大學(xué)電氣工程學(xué)院,河南鄭州450001 ;2.中原工學(xué)院電子信息學(xué)院,河南鄭州450007)摘要:在移動機(jī)器人路徑規(guī)劃問題的研究中,路徑規(guī)劃的實(shí)質(zhì)是機(jī)器人按照- -定的技術(shù)指標(biāo)找到一條從起 點(diǎn)到終點(diǎn)與障礙物無碰擅的最短路徑。由于路徑長度和安全性指標(biāo)是相互矛盾的兩個(gè)技術(shù)指標(biāo),大多數(shù)現(xiàn)存算法在把它們作為單目標(biāo)優(yōu)化時(shí)容易陷人局部最優(yōu),用多目標(biāo)優(yōu)化中的帕累托最優(yōu)則能夠很好地平衡和解決這兩個(gè)目標(biāo)不同資源分配下的組合情況。用貝塞爾曲線來描述路徑,用帕累托最優(yōu)解決路徑長度和安全性指標(biāo)之間的共存問題。實(shí)驗(yàn)結(jié)果表明,比起單目標(biāo)處理,多目標(biāo)優(yōu)化在解決路徑優(yōu)化問題中路徑長度及安全性指標(biāo)時(shí)較穩(wěn)定,能夠找到滿足條件的更短路徑，并且帕累托最優(yōu)能夠很好地解決不兼容目標(biāo)之間的共存問題,找到不同安全性指標(biāo)下優(yōu)化最短路徑。關(guān)鍵詞:貝塞爾曲線;多目標(biāo)優(yōu)化;帕累托最優(yōu)中圖分類號:TP18文獻(xiàn)標(biāo)識碼: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最短,機(jī)器人消耗能量最低,花費(fèi)時(shí)間最少,安全性及路徑光1引言滑度等技術(shù)指標(biāo)"。但是這些指標(biāo)在作為單目標(biāo)優(yōu)化處理路徑規(guī)劃在移動機(jī)器人導(dǎo)航中占有很重要的位置,表現(xiàn)時(shí)容易陷局部最優(yōu),因此路徑優(yōu)化問題通常被當(dāng)作很難發(fā)現(xiàn)為機(jī)器人按某--性能指標(biāo)找到--條從起點(diǎn)到終點(diǎn)的和障礙最優(yōu)解的具有多個(gè)目標(biāo)的NP完全問題(2] ,即大多采用多目物無接觸最優(yōu)或者接近最優(yōu)路徑。路徑問題通常涉及路徑標(biāo)優(yōu)化來進(jìn)行處理。與單目標(biāo)優(yōu)化問題不同,多目標(biāo)優(yōu)化向題的目標(biāo)函數(shù)是大于等于二的,大多數(shù)專家學(xué)者用保持非支基金項(xiàng)目:國家自然科學(xué)基金項(xiàng)目(60905039) ;中國博士后科學(xué)基金配解集,同時(shí)將種群朝著非支配解集移動并最終收斂于帕累特別資助項(xiàng)目(2012750639);教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研托曲面的中國煤化工基金( 2010000 ;河南省科技攻關(guān)項(xiàng)目(132102210521)本文中CNMH G'題，需要優(yōu)化的目標(biāo)收稿日期:2013 -07-26修回日期:2013-08 -05是路徑長度相女王比伯你，很亞然，這是兩個(gè)相互矛盾的概一364一念,這兩個(gè)指標(biāo)是不能同時(shí)滿足的,那么就需要- - 些方法來其中，u∈[0,1],PO、P分別表示起點(diǎn)和終點(diǎn),i表示產(chǎn)生路滿足不同使用者的需求。多目標(biāo)優(yōu)化能夠?qū)崿F(xiàn)同時(shí)對多個(gè)徑的曲線段。目標(biāo)的優(yōu)化,并對這些目標(biāo)進(jìn)行協(xié)調(diào)，設(shè)計(jì)者選擇的算法每安全性指標(biāo)指的是機(jī)器人要實(shí)現(xiàn)和障礙物之間無碰撞。運(yùn)行一次都會產(chǎn)生一組Pareto 最優(yōu)解,使用者可以根據(jù)自己用圓來表示障礙物,那么圓的半徑就是用來評價(jià)安全性指標(biāo)對優(yōu)化指標(biāo)的要求來選擇合適的解。的重要因素,用R表示。用d,表示曲線上的點(diǎn)與障礙物j之從20世紀(jì)70年代中期,機(jī)器人路徑規(guī)劃問題就以多種間的最短距離,安全性指標(biāo)的求解如下:形式被研究。傳統(tǒng)的一些方法如圖搜索法,人工勢場法,柵forj=1:k格法等由于搜索效率比較低而逐漸被淘汰,遺傳算法、蟻群fori=2:(L-1)算法、免疫算法、神經(jīng)網(wǎng)絡(luò)等智能算法得到了一些改進(jìn)而被dis(i-1) = sqr(sum((P,(i)應(yīng)用到路徑優(yōu)化中[41。- circle(j,1))~2 +例如裴振奎等提出了改變變異操作提高差分算法在優(yōu)(P,(i) -circle(j,2))2));化多目標(biāo)VRP問題(優(yōu)化目標(biāo):路徑長度和客戶所需貨物重end物的車輛)中的應(yīng)用'5] ,申曉寧等用引用了刪除,修復(fù)和平滑d(j) = min(dis-R)算子提高了多目標(biāo)路徑優(yōu)化(優(yōu)化目標(biāo):路徑長度,路徑安全性和平滑性)中遺傳算法的搜索效率低并防止出現(xiàn)早熟現(xiàn)fy= - min(d)(2)象[6] ,王振華等采用增強(qiáng)全局搜索能力的改進(jìn)蟻群算法解決其中,K表示障礙物的個(gè)數(shù),circle表示障礙物的圓心坐標(biāo)，了多目標(biāo)無人機(jī)路徑規(guī)劃(優(yōu)化目標(biāo):路徑長度和無人機(jī)選P.P,表示曲線上每個(gè)點(diǎn)的坐標(biāo),L = length(P.)表示曲線上擇該路徑時(shí)所受到的威脅強(qiáng)度)問題[7] , Masehian等提出了用改進(jìn)粒子群優(yōu)化算法解決多目標(biāo)路徑優(yōu)化(優(yōu)化目標(biāo):最點(diǎn)的個(gè)數(shù)fw表示安全性指標(biāo),可以看出,當(dāng)機(jī)器人為安全短路徑和路徑光滑性)問題[8] ,這些研究者及其它- -些沒有情況下行駛,其值為負(fù)值;當(dāng)機(jī)器人與障礙物相撞情況下,其提到的等在多目標(biāo)路徑規(guī)劃中都做出了自己的成就，但由于值為正值。各個(gè)研究者在研究路徑問題時(shí)設(shè)置的場景、障礙物的方式或路徑規(guī)劃描述的是在起點(diǎn)和終點(diǎn)已知的情況下,找到- -者用帕累托最優(yōu)表示的目標(biāo)不同,因此無法對不同研究者進(jìn)個(gè)從起點(diǎn)到終點(diǎn)的和障礙物無碰撞的路徑。用fmnmn 描述路行對比。徑長度,表示方式如下: .本文采用克服了傳統(tǒng)粒子群優(yōu)化算法易于收斂和早熟fmgu=sum(sqr((P.(2:L) -P,(1:L-1))). ^2+(P,現(xiàn)象缺點(diǎn)的動態(tài)多組群粒子群優(yōu)化算法,結(jié)合本文中要用到(2:L) -P,(1:L-1))).2))(3)的多目標(biāo)優(yōu)化思想來解決路徑優(yōu)化問題(多目標(biāo)動態(tài)多組群2.2約束處理粒子群優(yōu)化算法,簡稱MO - DMS- PS0)。同時(shí),用三次在優(yōu)化計(jì)算領(lǐng)域,很多問題被一些因素( 例如:物理,地Bezier 曲線來描述路徑,對技術(shù)指標(biāo)路徑長度和安全性進(jìn)行理等其它限制條件)所約束著。- -般情況下,這類問題可以優(yōu)化。實(shí)驗(yàn)結(jié)果表明:動態(tài)多組群粒子群優(yōu)化算法能夠很好歸納如下":的解決路徑優(yōu)化問題, Pareto最優(yōu)能夠很好的表示相互矛盾最小化的目標(biāo)之間的共存關(guān)系能夠在不同組合的優(yōu)化指標(biāo)下尋求f(x),x= [x,*..*n](4)與障礙物無碰撞的最優(yōu)路線。滿足h,(x)≤0,i = 1,.,.,p;2問題描述(5)2.1技術(shù)指標(biāo)g;(x) =0,j =p+1,"",m在機(jī)器人路徑規(guī)劃中,技術(shù)指標(biāo)(路徑最短、安全性、時(shí)其中x∈[xmn,x..]" ,p是不等式約束的個(gè)數(shù),(m-p)是等間最短路徑光滑性等)是- - 個(gè)非常重要的評價(jià)因素。接下式約束的個(gè)數(shù),為了簡化問題，所有的等式約束均可以轉(zhuǎn)化來要討論的技術(shù)性指標(biāo)是安全性和最短路徑指標(biāo)，依然采用為如下不等式約東:Beier曲線911(]來描述路徑,曲線的參數(shù)方程為:|g;(x)|-s≤0(6)(P。(1-u)3 +3P"u(1-u)2+其中8是允許的誤差,然后所有的約束問題就可以被定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動態(tài)多組群粒子群優(yōu)化算法fne(x) >&nwe(x) > e&fne(x.)