鄧乾旺　高禮坤　羅正平　李梟

摘要：采用改進(jìn)遺傳算子操作策略的遺傳算法以解決起重機(jī)三維空間多目標(biāo)吊裝路徑的規(guī)劃問題.首先建立起重機(jī)作業(yè)場景和位姿空間的數(shù)學(xué)模型，將起重機(jī)的空間多自由度路徑規(guī)劃問題轉(zhuǎn)化成平面路徑點(diǎn)的求解問題.然后確定以吊裝路徑最短、安全性最好和運(yùn)動形式變化最少為優(yōu)化目標(biāo)，通過添加記憶算子為插入算子和變異算子選取合適的方向和步長進(jìn)行多目標(biāo)優(yōu)化操作.實驗證明該算法能綜合考慮多種因素，并能同時提供不同特點(diǎn)的路徑供決策者選擇.

關(guān)鍵詞：多目標(biāo)優(yōu)化；遺傳算法；記憶算子；空間多自由度路徑規(guī)劃

中圖分類號：TH 213.1 文獻(xiàn)標(biāo)識碼：A

虛擬場景中起重機(jī)無碰撞吊裝路徑規(guī)劃屬于環(huán)境信息已知的全局路徑規(guī)劃問題.全局路徑規(guī)劃方法根據(jù)已獲知的環(huán)境信息，對環(huán)境進(jìn)行建模，為起重機(jī)規(guī)劃出一條滿足約束條件和目標(biāo)的吊裝路徑.目前，國內(nèi)外的研究機(jī)構(gòu)、學(xué)者對吊裝路徑規(guī)劃做出了大量的研究成果，比如Morad[1]等人基于人工智能的方法開發(fā)出一款PathFinder系統(tǒng)，該系統(tǒng)在Walkthru環(huán)境中運(yùn)用主動干涉檢測盒啟發(fā)式搜索方法來確定真實作業(yè)空間中的最優(yōu)吊裝路徑.Reddy[2]等人采用了C空間的原理和啟發(fā)式搜索算法對起重機(jī)的無碰撞吊裝路徑規(guī)劃過程進(jìn)行研究.

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

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

1路徑規(guī)劃模型的建立

1.1作業(yè)場景模型

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

4結(jié)論

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

參考文獻(xiàn)

[1]MORAD A A，CLEVELAND A B，BELIVEAU Y J，et al. Pathfinder： Albased 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]. ComputerAided Civil and Infrastructure Engineering，2002，17（6）：439-448.

[3]楊淮清，肖興貴，姚棟. 一種基于可視圖法的機(jī)器人全局路徑規(guī)劃算法[J]. 沈陽工業(yè)大學(xué)學(xué)報，2009，31（2）：226-229.

[4]朱磊，樊繼壯，趙杰，等. 基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障[J]. 中南大學(xué)學(xué)報：自然科學(xué)版，2011，42（11）：3421-3428.

[5]賈慶軒，陳剛，孫漢旭，等. 基于A*算法的空間機(jī)械臂避障路徑規(guī)劃 [J]. 機(jī)械工程學(xué)報，2010，46（13）：109-115.

[6]劉旭紅，張國英，劉玉樹，等. 基于多目標(biāo)遺傳算法的路徑規(guī)劃[J]. 北京理工大學(xué)學(xué)報，2005，25（7）：613-616.

[7]申曉寧，郭毓，陳慶偉，等. 多目標(biāo)遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 南京理工大學(xué)學(xué)報，2006，30（6）：659-663.

[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]杜海巖. 工程機(jī)械概論[M]. 成都：西南交通大學(xué)出版社，2004.

[10]張玉院. 移動式起重機(jī)無碰撞路徑規(guī)劃的設(shè)計與實現(xiàn)[D]. 大連：大連理工大學(xué)，2010.

[11]關(guān)志華. 面向多目標(biāo)優(yōu)化問題的遺傳算法的理論及應(yīng)用研究[D]. 天津：天津大學(xué)，2002.

摘要：采用改進(jìn)遺傳算子操作策略的遺傳算法以解決起重機(jī)三維空間多目標(biāo)吊裝路徑的規(guī)劃問題.首先建立起重機(jī)作業(yè)場景和位姿空間的數(shù)學(xué)模型，將起重機(jī)的空間多自由度路徑規(guī)劃問題轉(zhuǎn)化成平面路徑點(diǎn)的求解問題.然后確定以吊裝路徑最短、安全性最好和運(yùn)動形式變化最少為優(yōu)化目標(biāo)，通過添加記憶算子為插入算子和變異算子選取合適的方向和步長進(jìn)行多目標(biāo)優(yōu)化操作.實驗證明該算法能綜合考慮多種因素，并能同時提供不同特點(diǎn)的路徑供決策者選擇.

關(guān)鍵詞：多目標(biāo)優(yōu)化；遺傳算法；記憶算子；空間多自由度路徑規(guī)劃

中圖分類號：TH 213.1 文獻(xiàn)標(biāo)識碼：A

虛擬場景中起重機(jī)無碰撞吊裝路徑規(guī)劃屬于環(huán)境信息已知的全局路徑規(guī)劃問題.全局路徑規(guī)劃方法根據(jù)已獲知的環(huán)境信息，對環(huán)境進(jìn)行建模，為起重機(jī)規(guī)劃出一條滿足約束條件和目標(biāo)的吊裝路徑.目前，國內(nèi)外的研究機(jī)構(gòu)、學(xué)者對吊裝路徑規(guī)劃做出了大量的研究成果，比如Morad[1]等人基于人工智能的方法開發(fā)出一款PathFinder系統(tǒng)，該系統(tǒng)在Walkthru環(huán)境中運(yùn)用主動干涉檢測盒啟發(fā)式搜索方法來確定真實作業(yè)空間中的最優(yōu)吊裝路徑.Reddy[2]等人采用了C空間的原理和啟發(fā)式搜索算法對起重機(jī)的無碰撞吊裝路徑規(guī)劃過程進(jìn)行研究.

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

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

1路徑規(guī)劃模型的建立

1.1作業(yè)場景模型

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

4結(jié)論

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

參考文獻(xiàn)

[1]MORAD A A，CLEVELAND A B，BELIVEAU Y J，et al. Pathfinder： Albased 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]. ComputerAided Civil and Infrastructure Engineering，2002，17（6）：439-448.

[3]楊淮清，肖興貴，姚棟. 一種基于可視圖法的機(jī)器人全局路徑規(guī)劃算法[J]. 沈陽工業(yè)大學(xué)學(xué)報，2009，31（2）：226-229.

[4]朱磊，樊繼壯，趙杰，等. 基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障[J]. 中南大學(xué)學(xué)報：自然科學(xué)版，2011，42（11）：3421-3428.

[5]賈慶軒，陳剛，孫漢旭，等. 基于A*算法的空間機(jī)械臂避障路徑規(guī)劃 [J]. 機(jī)械工程學(xué)報，2010，46（13）：109-115.

[6]劉旭紅，張國英，劉玉樹，等. 基于多目標(biāo)遺傳算法的路徑規(guī)劃[J]. 北京理工大學(xué)學(xué)報，2005，25（7）：613-616.

[7]申曉寧，郭毓，陳慶偉，等. 多目標(biāo)遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 南京理工大學(xué)學(xué)報，2006，30（6）：659-663.

[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]杜海巖. 工程機(jī)械概論[M]. 成都：西南交通大學(xué)出版社，2004.

[10]張玉院. 移動式起重機(jī)無碰撞路徑規(guī)劃的設(shè)計與實現(xiàn)[D]. 大連：大連理工大學(xué)，2010.

[11]關(guān)志華. 面向多目標(biāo)優(yōu)化問題的遺傳算法的理論及應(yīng)用研究[D]. 天津：天津大學(xué)，2002.

摘要：采用改進(jìn)遺傳算子操作策略的遺傳算法以解決起重機(jī)三維空間多目標(biāo)吊裝路徑的規(guī)劃問題.首先建立起重機(jī)作業(yè)場景和位姿空間的數(shù)學(xué)模型，將起重機(jī)的空間多自由度路徑規(guī)劃問題轉(zhuǎn)化成平面路徑點(diǎn)的求解問題.然后確定以吊裝路徑最短、安全性最好和運(yùn)動形式變化最少為優(yōu)化目標(biāo)，通過添加記憶算子為插入算子和變異算子選取合適的方向和步長進(jìn)行多目標(biāo)優(yōu)化操作.實驗證明該算法能綜合考慮多種因素，并能同時提供不同特點(diǎn)的路徑供決策者選擇.

關(guān)鍵詞：多目標(biāo)優(yōu)化；遺傳算法；記憶算子；空間多自由度路徑規(guī)劃

中圖分類號：TH 213.1 文獻(xiàn)標(biāo)識碼：A

虛擬場景中起重機(jī)無碰撞吊裝路徑規(guī)劃屬于環(huán)境信息已知的全局路徑規(guī)劃問題.全局路徑規(guī)劃方法根據(jù)已獲知的環(huán)境信息，對環(huán)境進(jìn)行建模，為起重機(jī)規(guī)劃出一條滿足約束條件和目標(biāo)的吊裝路徑.目前，國內(nèi)外的研究機(jī)構(gòu)、學(xué)者對吊裝路徑規(guī)劃做出了大量的研究成果，比如Morad[1]等人基于人工智能的方法開發(fā)出一款PathFinder系統(tǒng)，該系統(tǒng)在Walkthru環(huán)境中運(yùn)用主動干涉檢測盒啟發(fā)式搜索方法來確定真實作業(yè)空間中的最優(yōu)吊裝路徑.Reddy[2]等人采用了C空間的原理和啟發(fā)式搜索算法對起重機(jī)的無碰撞吊裝路徑規(guī)劃過程進(jìn)行研究.

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

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

1路徑規(guī)劃模型的建立

1.1作業(yè)場景模型

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

4結(jié)論

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

參考文獻(xiàn)

[1]MORAD A A，CLEVELAND A B，BELIVEAU Y J，et al. Pathfinder： Albased 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]. ComputerAided Civil and Infrastructure Engineering，2002，17（6）：439-448.

[3]楊淮清，肖興貴，姚棟. 一種基于可視圖法的機(jī)器人全局路徑規(guī)劃算法[J]. 沈陽工業(yè)大學(xué)學(xué)報，2009，31（2）：226-229.

[4]朱磊，樊繼壯，趙杰，等. 基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障[J]. 中南大學(xué)學(xué)報：自然科學(xué)版，2011，42（11）：3421-3428.

[5]賈慶軒，陳剛，孫漢旭，等. 基于A*算法的空間機(jī)械臂避障路徑規(guī)劃 [J]. 機(jī)械工程學(xué)報，2010，46（13）：109-115.

[6]劉旭紅，張國英，劉玉樹，等. 基于多目標(biāo)遺傳算法的路徑規(guī)劃[J]. 北京理工大學(xué)學(xué)報，2005，25（7）：613-616.

[7]申曉寧，郭毓，陳慶偉，等. 多目標(biāo)遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J]. 南京理工大學(xué)學(xué)報，2006，30（6）：659-663.

[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]杜海巖. 工程機(jī)械概論[M]. 成都：西南交通大學(xué)出版社，2004.

[10]張玉院. 移動式起重機(jī)無碰撞路徑規(guī)劃的設(shè)計與實現(xiàn)[D]. 大連：大連理工大學(xué)，2010.

[11]關(guān)志華. 面向多目標(biāo)優(yōu)化問題的遺傳算法的理論及應(yīng)用研究[D]. 天津：天津大學(xué)，2002.