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