基于多目標遺傳算法的起重機吊裝路徑規劃＊

鄧乾旺，高禮坤，羅正平，李 梟

（湖南大學 汽車車身先進設計制造國家重點實驗室，湖南 長沙 410082）

虛擬場景中起重機無碰撞吊裝路徑規劃屬于環境信息已知的全局路徑規劃問題.全局路徑規劃方法根據已獲知的環境信息，對環境進行建模，為起重機規劃出一條滿足約束條件和目標的吊裝路徑.目前，國內外的研究機構、學者對吊裝路徑規劃做出了大量的研究成果，比如Morad［1］等人基于人工智能的方法開發出一款Path－Finder系統，該系統在Walk－thru環境中運用主動干涉檢測盒啟發式搜索方法來確定真實作業空間中的最優吊裝路徑.Reddy［2］等人采用了C－空間的原理和啟發式搜索算法對起重機的無碰撞吊裝路徑規劃過程進行研究.

起重機空間無碰撞吊裝路徑規劃本質上是一個多性能指標的NP完全問題，這其中需要滿足多個優化參數，例如最短距離、最小時間和最低耗能等，很難為其求解單一的優化解.傳統路徑規劃方法有可視圖法、柵格法和A＊等啟發式算法［3－5］.在解決空間多自由度的路徑規劃問題時，上述算法的搜索速度、精度和解空間不足.近年來，遺傳算法在復雜多目標優化問題中的應用已成為研究的熱點，然而，多數文獻僅對平面路徑規劃問題進行優化［6－7］，針對空間多自由度路徑規劃這一類多關節多約束多目標優化問題的研究較少.Kazuo Sugihara and John Smith［8］用遺傳算法進行路徑規劃的研究具有一定的可行性和有效性，然而該文提出的路徑空間柵格劃分法不能解決規劃速度與規劃精度之間的矛盾：柵格密度小，則搜索精度差；若密度大，則數據計算量大，計算速度低.因此進化較多的搜索過程需要占據較大計算時間和存儲空間.

本文將遺傳算法應用于起重機多目標路徑優化問題，通過分析作業場景模型和起重機位姿空間模型，將路徑空間分割成多個路徑平面，然后對路徑平面進行柵格化處理，建立平面路徑規劃模型，最后應用遺傳算法原理建立吊裝物的路徑點信息模型來確定起重機的多個吊裝路徑.該算法通過為場景模型添加包圍盒屬性來保證路徑空間的搜索精度和路徑的可行性，并添加新的記憶算子來提高計算效率和收斂速度，對于運用遺傳算法求解空間多自由度的路徑規劃問題有一定的指導意義.

1 路徑規劃模型的建立

1.1 作業場景模型

全地面起重機臂架組合形式有主臂、主臂＋輔助臂（副臂、塔臂或動臂）兩種，吊裝運動有回轉、變幅和卷揚3種方式［9］.根據起重機的吊裝運動特點，將吊裝場景劃分成兩個路徑空間，為便于表述將其投影至XOY平面上（如圖1所示）.定義r，R分別為起重機最小和最大的工作半徑，吊裝幅度Fd∈［r，R］，S和T分別為吊裝物的起吊點和目標點，O為起重機回轉中心，OS和OT分別為起始邊和終止邊，其中，Q1為自起始邊沿逆時針（左轉）方向指向終止邊的扇形區域，角度范圍為W1；Q2為自起始邊沿順時針方向（右轉）指向終止邊的扇形區域，角度范圍為W2.

圖1 路徑空間的劃分Fig.1 The division of path space

將三維場景劃分為障礙物靜態空間與起重機動態空間兩部分.計算在工作區域內的M個障礙物的檢測區域，其幅長范圍fi∈［li，Li］和角度范圍γi∈［vi，Vi］，然后自初始位置沿逆時針方向進行排序，依次將檢測區域記為qi（i＝1，2，…，M），若qi在OX正向軸上，則將該障礙物劃分至第一和第四象限兩部分.圖1中障礙物B1的檢測區域q1的幅長范圍f1∈［Ob1，Ob2］，角度范圍γ1∈［θ1，θ2］；障礙物 B3的檢測區域被分成兩部分，γ3∈ ［0，∠b0Ob5］∪γ3∈［∠b0Ob'5，2π）.

起重機當前回轉平面的回轉角為ω，將起重機的動態空間劃分成主臂、輔助臂和吊裝物三個空間，偏移角為θ（設wd，ld為吊裝物的長和寬），令吊裝物空間的最大回轉半徑，主臂空間的最大回轉半徑fL，輔助臂空間的最大回轉半徑fF.

1.2 起重機位姿空間模型

起重機吊裝過程實際上就是起重機通過調整運動形式將吊裝物從起吊點安全移到目標點的過程.在真實吊裝時，一般不允許臂架跨過車頭所在的區域Q0，若Q0∈Qk（k＝1或2），則將Qk空間定義為禁吊空間.圖2所示為路徑空間Qk（k＝1）內某一吊裝路徑中吊裝物底面中心點運動軌跡，“G1→G2”表示上幅過程，“G2→G3”表示卷揚起升過程，“G3→G4”表示回轉過程，“G4→G5”表示下幅過程.將吊裝物底面中心點運動軌跡中起重機運動形式變化時的拐點視為路徑點，Gi（i＝1，2，…，n，n為路徑點個數）表示吊裝路徑中第i個路徑點，將路徑點所在平面Πj（j＝1，2，…，m，m為路徑平面個數）定義為吊裝路徑中第j個路徑平面.設路徑平面Πj和Πj＋1的回轉角（OXj軸與OX軸沿回轉方向的角度值）分別為wj、wj＋1.其中，每個路徑平面上至少有兩個不重合的路徑點，wj＜wj＋1；G1和Gn分別表示起始點S和目標點T，且各自分布在Π1和Πm路徑平面上；平面Πj上的最后一個路徑點（尾路徑點）Gi與平面Πj＋1上的首路徑點Gi＋1的坐標相同.

圖2 路徑點運動軌跡Fig.2 The movement trajectory of path points

結合起重機運動的位姿空間，將路徑平面Πj進行柵格化處理.取沿Xj軸方向的柵格間隔△a，沿Z軸方向的柵格間隔△b.根據起重機運動形式的大小與方向如圖3所示，△f，△w和△zh分別表示變幅、回轉和卷揚時路徑點的步長.為方便對路徑點進行編碼，令 △zh＝N0×△zf（或△zf＝N0×△zh，N0取正整數），取△a＝△xf，△b＝△zf（或△b＝△zh）.

圖3 路徑點運動方向及步長Fig.3 The movement direction of path points and step size

將起重機動態空間投影至路徑平面上，且柵格線的交點視為路徑點.若起重機動態空間滿足fd∈fi∩ （ω∈γi∪≤θ），則將障礙物qi的檢測區域也投影至該平面上，如圖4所示.當起重機、吊裝物和作業環境（障礙物和地面等）三者之間出現重疊時，則更新重疊部分的包圍盒子節點進行碰撞檢測計算.若Gi在該位置發生碰撞，則將該路徑點視為不可行路徑點.

圖4 起重機位姿空間柵格化Fig.4 The grids of pose space of crane

1.3 多目標問題表述

在起重機三維空間的吊裝路徑中，需要滿足工作區域約束條件G1（P），使吊裝物在可行的區域內進行吊裝；還要滿足無碰撞約束條件G2（P），使吊裝路徑安全無碰撞.為了使吊裝路徑的路程最短，需要對路程度量函數F1（P）進行優化；路徑中每一次的動作改變，必然帶來機構的啟制動，從而造成對起重機的載荷沖擊.為減小這種沖擊，需要對路徑點度量函數F2（P）進行優化［10］.從安全角度來看，當路徑段“Gi→Gi＋1”跨過或靠近某障礙物時，當起重機或吊裝物進入該障礙物的檢測區域時，取在該位置時的中間點Ji.Ji沿圖3中六個方向運動時，可能存在六個發生碰撞的路徑點gt（t＝1，…，6），為減少碰撞的情況，需要對危險性度量函數F3（P）進行優化.

參數設定：

m和n分別代表路徑平面和路徑點個數；

Gi代表路徑點；

P 代表吊裝路徑，P＝ ｛G1，G2，…，Gn｝；

CA起重機包圍盒空間；

CB吊裝物包圍盒空間；

CC作業場景包圍盒空間.

目標函數定義：

1）路程度量函數

式中：d（Gi，Gi＋1）為路徑點Gi和Gi＋1的距離，

2）路徑點度量函數

3）危險性度量函數

約束條件：

1）工作區域約束條件G1（P）：

xi≥r∪xi≤R，xi是路徑點Gi在Xj軸上的坐標值；

2）無碰撞約束條件G2（P）：

（CA∩CB）∪ （CA∩CC）∪ （CB∩CC）＝Φ.

2 基于多目標遺傳算法的路徑規劃

面向起重機空間路徑規劃的多目標遺傳算法是通過遺傳算子產生子代，再根據約束條件和適應度函數選擇有優勢的子代進行繁殖，最終達到逐步逼近最優解的目的.多目標路徑規劃問題描述為：

2.1 優勢個體選擇策略

優勢個體選擇策略分為約束占優和目標值占優兩部分內容.

1）設路徑P1和P2的目標值向量F（P1），F（P2）分 別 是 ｛F1（P1），…，FN（P1）｝和 ｛F1（P2），…，FN（P2）｝，若滿足條件：?i∈ （1，2，…，N），有Fi（P1）≤Fi（P2），且 ?i（1，2，…，N），使 Fi（P1）＜Fi（P2），稱路徑P1對路徑P2目標值占優.

2）將滿足約束條件G（P）的路徑設為可行性路徑，否則，為不可行路徑.以下兩個條件有一個成立時，稱路徑P1對路徑P2約束占優：a）路徑P1為可行性路徑，路徑P2為不可行性路徑；b）路徑P1，P2同時為可行性路徑或不可行性路徑時，路徑P1對路徑P2目標值占優［11］.

2.2 編碼、譯碼過程

2.2.1 編 碼

采用鏈表方式表示每一染色體，每個染色體代表一條路徑，鏈表中每一個元素表示路徑中的一個節點，對節點采用路徑點編碼方式建立路徑點模型，如圖5所示，ωj表示路徑平面∏j的回轉角，（xi，yi）表示路徑點Gi在其所在路徑平面的局部坐標.

圖5 路徑點編碼Fig.5 The coding of path points

2.2.2 譯 碼

譯碼就是將一組連續的路徑點編碼信息轉化成起重機具體的運動形式的過程.定義記錄吊裝路徑的矩陣p［u］［v］（u＝1，2，…，n－1），表示起重機的第u個動作在運動形式v（v＝0，1，2，3）時的運動量w，其中，v＝1時表示回轉，當w＞0表示左轉，否則表示右轉；v＝2時表示變幅，當w＞0表示上幅，否則表示下幅；v＝3時表示卷揚，當w＞0表示上升，否則表示下落.初始化p［u］［v］＝0，譯碼步驟如下：

步驟1：讀取路徑點Gu（u＝1），其坐標和所在路徑平面∏j的回轉角分別為（xu，zu），wj.

步驟2：讀取路徑點Gu＋1，若Gu，Gu＋1不在同一個路徑平面∏j內，則令p［u］［1］＝（wj＋1－wj）.若Gu，Gu＋1都在∏j內，當xu＋1≠xu時，表示變幅運動，則令P［u］［2］＝△α×（xu－xu＋1）／△a；當xu＋1＝xu時，表示卷揚運動，則令P［u］［3］＝（zu＋1－zu）.令u＝u＋1，執行下一步.

步驟3：判斷u是否等于n（即Gu是否為目標點），若是，則完成該路徑的譯碼過程；否則，轉到步驟2.

2.3 種群初始化

根據路徑的編碼方式，將種群初始化過程分為兩個部分.一部分是路徑平面的均勻分割，∏j至∏j＋1是由連續的回轉運動聯系起來的，如圖6所示.將路徑空間分割成m個間距為Δw的路徑平面；路徑平面上的路徑點采用啟發式算法隨機產生，首先隨機產生平面∏j上的首尾路徑點Gi和Gi＋1和平面∏j＋1上的尾路徑點，然后在兩路徑點之間運用2.4節的插入算子插入中間點.

圖6 種群初始化Fig.6 Population initialization

2.4 遺傳算子

本算法涉及六個遺傳算子：記憶算子、選擇算子、插入算子、交叉算子、變異算子和刪除算子.

1）記憶算子

為減小算法中的碰撞檢測的時間耗損，需對檢測過程進行簡化.若在∏j平面上某路徑點Gi處，吊裝物或起重機與作業場景發生碰撞，即（CA∩CC）∪（CB∩CC）≠Φ，則記憶該路徑點為平面∏j的不可行節點，在該平面上進行插入和變異操作時要避開平面不可行節點.若吊裝物與臂架發生碰撞，即CA∩CB≠Φ，若路徑點Gt（t＝2，…，n－1）滿足xt≤xi∩zt≥zi，則記憶該路徑點為路徑空間的不可行節點，在該路徑空間內進行插入和變異操作時要避開空間不可行節點.

2）選擇算子

采用兩種不同的選擇算子，第1種算子的功能是選擇優良的個體參與繁殖；第2種算子的功能是選擇較差或發生碰撞的子路徑進行變異.

3）插入算子

對于同一路徑平面上的某兩個相鄰可行性路徑點Gi，Gi＋1，若沿±△f，±△zh四個方向Gi與Gi＋1之間無法形成路徑或Gi與Gi＋1之間形成的路徑與障礙物發生碰撞時，可能需要插入nt（nt≥0）個可行性路徑點.若插入的路徑點或新路徑點產生的新路徑不可行，則重新選取插入量（改變倍率值κ1，κ2）和插入方向再進行計算判斷.則插入原則滿足：

其中，K1∈N∪K2∈N，κ1表示沿變幅方向插入的新路徑點相對于Gi的步進倍率，且κ2＝0上幅時f＝－1，κ1＜0，下幅時f＝1，κ1＞0；κ2表示沿卷揚方向插入的新路徑點相對于Gi步進的倍率，且κ1＝0，起升時κ2＞0，下落時κ2＜0.

4）交叉算子

等概率地從兩父代個體中隨機選擇兩個路徑點（起點和終點除外）或兩個路徑平面，交換兩個體在交叉處的部分染色體.

5）變異算子

規定路徑點沿圖中上幅、下幅、卷揚和下落四個方向進行變異.

a）當路徑可行時，隨機選擇路徑中的幾個路徑平面，任意一組相鄰路徑平面的路徑點之間形成一條子路徑段，計算這些子路徑段的每一個目標值和約束值，選擇較差的子路段所對應的路徑點進行變異；如果所有的子路段都互不占優，則隨機選擇一段進行變異，并保證變異后的路徑仍為可行性路徑.

b）當路徑點不可行時，對該路徑點坐標依概率進行較大范圍調整.根據圖中吊裝物與障礙物的相對位置，使其變異到障礙物余量范圍ε之外；否則，在兩端點中隨機選擇一點進行變異.若變異后的路徑點為可行性路徑點，變異后產生的新路徑為可行性路徑，則用偏移后的新節點替換變異節點；否則重新選取變異量（改變倍率值κ3和κ4）和變異方向再進行計算判斷.變異公式如下：

xi＝xi＋f×κ3×Δxf，

zi＝zi＋f×κ3×Δzf＋κ4×Δzh.

其中，κ3，κ4分別表示沿變幅和卷揚方向的變異倍率，取值規律同κ1和κ2一致.

6）刪除算子

刪除算子主要分4種：圖7（a）中A和C，C和E都直接可達，則刪除B和D 路徑點；圖7（a）中路徑點C在路徑中出現了兩次，則需刪除位于相同路徑點間的所有點；圖7（b）中節點B和C是直接可達的，則刪除位于B和C之間的所有路徑點；若∏j－1上的尾路徑點和∏j＋1上的首路徑點是直接可達的，則刪除路徑平面∏j及其路徑點.

圖7 刪除算子Fig.7 Delete operator

3 實例驗證

在全地面起重機大型工程吊裝方案規劃系統上運用OSG與VC＋＋9.0實現了該算法.以圖8火電吊裝場景為例，作業場景為100m×100m的平面，選取“主臂＋副臂”工況的全地面起重機，主臂長為48.4m，副臂長為16.0m，主輔臂夾角為15°，吊裝幅度fd∈［16，52］（m）；Q1為可吊裝區域.圖8為起重機在起吊點時的姿態，黃色區域為目標點位置；初始化路徑平面間夾角Δw＝5°；令△α＝1°，起重機每變幅1°使吊裝物上升0.80m，設置路徑點步長△f＝1.12m，△xf＝0.78m，△zf＝0.80m，△zh＝0.80m，則柵格間距△a＝0.78m，△b＝0.80m.

圖8 吊裝作業場景Fig.8 The lifting operation scene

本文算法的運行參數為：群體規模為50，最大進化代數T＝80.前T／2代中，交叉概率Pc＝0.5，變異概率Pm＝0.5，刪除概率Pd＝0.8；后T／2代中，Pc＝0.2，Pm＝0.1，Pd＝0.4.算法結束后，收集所有結果中與三個目標函數相對應的較優路徑作為Pareto解集的一個逼近解集，相關較優路徑矩陣對應目標函數值解集分布如圖9所示.針對三個目標函數挑出三條路徑依次為：

圖9 Pareto解集對應目標函數值分布Fig.9 Distribution of objective function value of Pareto solution set

1）路徑最短：上幅16°→起升8m→上幅14°→左轉116.57°→下幅39°；其吊裝路徑矩陣為：

2）拐點最少：起升8m→上幅28°→左轉116.57°→ 下幅37°；其吊裝路徑矩陣為：

3）危險最小：起升16m→上幅26°→左轉30°→起升6.4m→左轉86.57°→下幅32°→下落15.2 m；吊裝路徑矩陣為：

各路徑的度量函數值如表1所示.

表1 各路徑的目標函數值Tab.1 Object function value of paths

本文還將其與經典遺傳算法（即沒有記憶算子與刪除算子）進行了比較.相關目標函數收斂對比如圖10所示.其中改進遺傳算法與經典遺傳算法均能獲得較好的Pareto解集，但是改進遺傳算法有利于提高收斂速率，減少計算時間.

圖10 度量值的收斂對比Fig.10 Comparison of convergence of measurement value

4 結 論

針對起重機空間多自由度的吊裝路徑規劃問題，提出了一種基于多目標遺傳算法的路徑規劃方法.該算法根據起重機吊裝運動特點，設計了三維空間的路徑點編碼機制和適合于路徑規劃的具有啟發作用的遺傳算子，且綜合考慮了起重機吊裝路徑的多個目標，能夠同時提供不同特點的多條路徑.最后通過實例驗證，表明了該算法的有效性.

［1］MORAD A A，CLEVELAND A B，BELIVEAU Y J，et al.Path－finder：Al－based path planning system［J］.Journal of Computing in Civil Engineering，1992，6（2）：114－128.

［2］REDDY H R，VARGHESE K.Automated path planning for mobile crane lifts［J］.Computer－Aided Civil and Infrastructure Engineering，2002，17（6）：439－448.

［3］楊淮清，肖興貴，姚棟.一種基于可視圖法的機器人全局路徑規劃算法［J］.沈陽工業大學學報，2009，31（2）：226－229.YANG Huai－qing，XIAO Xing－gui，YAO Dong.A V－graph based global path planning algorithm for mobile robot［J］.Journal of Shenyang University of Technology，2009，31（2）：226－229.（In Chinese）

［4］朱磊，樊繼壯，趙杰，等.基于柵格法的礦難搜索機器人全局路徑規劃與局部避障［J］.中南大學學報：自然科學版，2011，42（11）：3421－3428.ZHU Lei，FAN Ji－zhuang，ZHAO Jie，et al.Global path planning and local obstacle avoidance of searching robot in mine disasters based on grid method［J］.Journal of Central South University：Science and Technology，2011，42（11）：3421－3428.（In Chinese）

［5］賈慶軒，陳剛，孫漢旭，等.基于A＊算法的空間機械臂避障路徑規劃 ［J］.機械工程學報，2010，46（13）：109－115.JIA Qing－xuan，CHEN Gang，SUN Han－xu，et al.Path planning for space manipulator to avoid obstacle based on A＊algorithm［J］.Chinese Journal of Mechanical Engineering，2010，46（13）：109－115.（In Chinese）

［6］劉旭紅，張國英，劉玉樹，等.基于多目標遺傳算法的路徑規劃［J］.北京理工大學學報，2005，25（7）：613－616.LIU Xu－hong，ZHANG Guo－ying，LIU Yu－shu，et al.Path planning based on multi－objective genetic algorithm［J］.Journal of Beijing Institute of Technology，2005，25（7）：613－616.（In Chinese）

［7］申曉寧，郭毓，陳慶偉，等.多目標遺傳算法在機器人路徑規劃中的應用［J］.南京理工大學學報，2006，30（6）：659－663.SHEN Xiao－ning，GUO Yu，CHEN Qing－wei，et al.Application of multi－objective optimization genetic algorithm to robot path planning［J］.Journal of Nanjing University of Science and Technology，2006，30（6）：659－663.（In Chinese）

［8］KAZUO SUGIBARA，JOHN SMITH.Genetic algorithms for adaptive motion planning of an autonomous mobile robot［C］／／Computational Intelligence in Robotics and Automation：1997 IEEE International Symposium，Monterey，USA，1997.

［9］杜海巖.工程機械概論［M］.成都：西南交通大學出版社，2004.DU Hai－yan.Introduction to mechanical engineering［M］.Chengdu：Southwest Jiaotong University Press，2004.（In Chinese）

［10］張玉院.移動式起重機無碰撞路徑規劃的設計與實現［D］.大連：大連理工大學，2010.ZHANG Yu－yuan.Design and implementation of collision－free path planning for mobile crane［D］.Dalian：Dalian University of Technology，2010.（In Chinese）

［11］關志華.面向多目標優化問題的遺傳算法的理論及應用研究［D］.天津：天津大學，2002.GUAN Zhi－hua.Research on the theory and application of genetic algorithm for multi－objective optimization problems［D］.Tianjing：Tianjing University，2002.（In Chinese）