基于RRTConnect算法的雙履帶起重機路徑規(guī)劃研究論文

1、 PAGE59 / NUMPAGES68碩 士 學(xué) 位 論 文基于RRTConnect算法的雙履帶起重機路徑規(guī)劃研究Path Planning for Two Crawler Cranes Heavy Lifting Based on RRTConnect理工大學(xué)DalianUniversity of Technology理工大學(xué)學(xué)位論文獨創(chuàng)性聲明作者重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下進(jìn)行研究工作所取得的成果。盡我所知，除文中已經(jīng)注明引用容和致的地方外，本論文不包含其他個人或集體已經(jīng)發(fā)表的研究成果，也不包含其他已申請學(xué)位或其他用途使用過的成果。與我一同工作的同志對本研究所做的貢獻(xiàn)均

2、已在論文中做了明確的說明并表示了意。若有不實之處，本人愿意承擔(dān)相關(guān)法律責(zé)任。學(xué)位論文題目：基于RRTConnect算法的雙履帶起重機路徑規(guī)劃研究作 者 簽 名 ： 日期：年月日摘 要被吊設(shè)備、起重機以與吊裝方式的多樣化、復(fù)雜化等特點決定了起重機吊裝是一類高危險性的活動。與單機吊裝作業(yè)相比，兩臺履帶起重機（文中簡稱雙機）協(xié)同吊裝的危險系數(shù)更高。為了安全順利地完成吊裝作業(yè)，合理高效的起重機路徑規(guī)劃就顯得尤為重要。為此，本課題將針對雙機協(xié)同吊裝任務(wù)，抽象問題的數(shù)學(xué)模型，對閉環(huán)約束、非完整約束等開展深入研究，應(yīng)用并改進(jìn)RRTConnect算法，提出可以應(yīng)用于平移和翻轉(zhuǎn)被吊設(shè)備的通用方法，規(guī)劃出滿足無碰

3、撞、實時保證繩偏角、履帶起重機行走特性和起重性能等要求的優(yōu)化路徑。首先，通過對吊裝存在的安全性問題進(jìn)行分析，以與對起重機吊裝路徑規(guī)劃研究現(xiàn)狀進(jìn)行總結(jié)，論述了本課題的研究意義，同時對路徑規(guī)劃方法的特點進(jìn)行研究確定應(yīng)用和改進(jìn)RRTConnect（雙向多步擴展快速隨機搜索樹）算法來解決雙機路徑規(guī)劃問題。其次，在討論機器人路徑規(guī)劃的基礎(chǔ)上，對雙機路徑規(guī)劃問題進(jìn)行深入剖析，構(gòu)建雙機吊裝系統(tǒng)數(shù)學(xué)模型，并對數(shù)學(xué)模型的變量進(jìn)行詳細(xì)說明。再次，對雙機吊裝中兩類常見吊裝任務(wù)即將被吊設(shè)備翻轉(zhuǎn)和將被吊設(shè)備平移，論述了采用RRTConnect算法解決雙機路徑規(guī)劃問題的步驟，同時給出了逆向運動學(xué)確定雙機初始和目標(biāo)位姿的計

4、算過程和對路徑的優(yōu)化處理方法，并用三個典型案例驗證方法的可行性。最后，對RRTConnect算法做改進(jìn)，提出了基于關(guān)鍵位姿的RRTMultiPhrase算法，以解決雙機吊裝中較為復(fù)雜的吊裝任務(wù)路徑規(guī)劃，論述了RRTMultiPhrase算法的原理，同時給出了關(guān)鍵點選擇的一般方法，接著對兩個復(fù)雜案例分別用三種方法進(jìn)行路徑規(guī)劃，說明本文提出算法的可行性。本文分析了雙機吊裝作業(yè)的特點，對給定雙機初始和目標(biāo)位姿的協(xié)同吊裝路徑規(guī)劃問題展開深入的探索和研究，實現(xiàn)了考慮直線行走、轉(zhuǎn)彎、起升、回轉(zhuǎn)和變幅等動作并滿足無碰撞、閉環(huán)約束、非完整約束、不超載等約束的路徑規(guī)劃，解決了前人規(guī)劃方法不適用于需要起重機行走或

5、者使被吊設(shè)備翻轉(zhuǎn)的吊裝任務(wù)的局限性，并且將提出的方法應(yīng)用于典型的吊裝案例，證明其可行性、實用性和高效性。關(guān)鍵詞：路徑規(guī)劃；雙機協(xié)同吊裝；RRTConnect；閉環(huán)約束；非完整約束Path Planning for Two Crawler Cranes Heavy Lifting Based on RRTConnectAbstractNowadays, loads, cranes and lifting methods become more and more diversified and complicated which makes the heavy lifting a high ris

6、k activity. Compared with single crane lifting, two crawler cranes (dual-crane) lifting has a greater risk. To finish the lifting task successfully, it is very important to make a suitable and safe path planning as quickly as possible. So, this paper researches on dual-crane system, abstracts themat

7、hematicalmodel, applies and improves RRTConnect algorithm, proposes general methods which can be used in bothtranslating task and rotating task, and gains an optimized path which fulfillsconstraints such as collision-free, minimum rope-slope requirement, traveling feature of crawler crane and liftin

8、g capacity and so on.Firstly, by analyzing security problem existingin lifting task, and summary current achievement of path planning, we present the purpose and significance of this paper. Moreover, this paper studies on feature of algorithms used in path planning, and chooses RRTConnect (Rapidly-e

9、xploring Random Tree with Multi-step Expanding) as basic method to solve path planning of dual-crane.Secondly, based on the previous researches on robot path planning, this paper makes deep study on heavy lifting of dual-crane, and then builds mathematical model for this path planning problem. Moreo

10、ver, it makes definition and detailed description of the variant relevant to mathematical model. Thirdly,this paper adopts RRTConnect algorithm to search a feasible path. This method can be used in both translating task and rotating task which commonly exist in construction projects. Furthermore, ca

11、lculation of dual-cranes initial and target configuration applying inverse kinematical and optimization method are presented. Besides, three cases verify the method is feasible.Finally,it proposes RRTMultiPhrase algorithm which improves RRTConnect algorithm and bases on key configuration to deal wit

12、h complicated path planning of dual-crane.Whereafter, theory of RRTMultiPhrase algorithm and method of choosing a key configuration are presented. After that, we carry on path planning on two complicated cases with three methods independently. Results indicate the feasibility of proposed methods.Thi

13、s paper analyzes features of dual-crane lifting, makes deep exploration of path planning on condition that initial and target configuration is known. This approach takes cranes traveling, turning, hoisting, slewing and luffing action into consideration, aims to find a path satisfying collision-free,

14、 nonholonomic constraint, loop closure constraint and within lifting capacity and so on. Actual cases are described and corresponding results are listed. By analysis of the typical cases, we conclude that the proposed method is practical and efficient.Key Words：Path Planning; Dual-Crane Heavy Liftin

15、g;RRTConnect;Kinematic Closure Constraints;Nonholonomic Constraints目 錄 TOC o 1-3 h z u HYPERLINK l _Toc327252642摘要 PAGEREF _Toc327252642 h IHYPERLINK l _Toc327252643Abstract PAGEREF _Toc327252643 h IIHYPERLINK l _Toc3272526441 緒論 PAGEREF _Toc327252644 h 1HYPERLINK l _Toc3272526451.1 吊裝路徑規(guī)劃的重要性 PAGER

16、EF _Toc327252645 h 1HYPERLINK l _Toc3272526461.2 吊裝路徑規(guī)劃研究現(xiàn)狀 PAGEREF _Toc327252646 h 2HYPERLINK l _Toc3272526471.3 雙機吊裝路徑規(guī)劃研究現(xiàn)狀 PAGEREF _Toc327252647 h 3HYPERLINK l _Toc3272526481.4 路徑規(guī)劃方法綜述 PAGEREF _Toc327252648 h 4HYPERLINK l _Toc3272526491.5 課題的目的意義與主要工作容 PAGEREF _Toc327252649 h 7HYPERLINK l _Toc3

17、272526502 雙機吊裝路徑規(guī)劃數(shù)學(xué)模型 PAGEREF _Toc327252650 h 9HYPERLINK l _Toc3272526512.1 數(shù)學(xué)模型 PAGEREF _Toc327252651 h 9HYPERLINK l _Toc3272526522.2 名詞定義 PAGEREF _Toc327252652 h 10HYPERLINK l _Toc3272526532.2.1 剛體模型 PAGEREF _Toc327252653 h 10HYPERLINK l _Toc3272526542.2.2 位姿空間 PAGEREF _Toc327252654 h 12HYPERLINK

18、 l _Toc3272526552.2.3 控制輸入集 PAGEREF _Toc327252655 h 14HYPERLINK l _Toc3272526562.2.4 位姿變換 PAGEREF _Toc327252656 h 15HYPERLINK l _Toc3272526572.2.5 距離函數(shù) PAGEREF _Toc327252657 h 16HYPERLINK l _Toc3272526582.3 路徑約束 PAGEREF _Toc327252658 h 17HYPERLINK l _Toc3272526592.3.1 行走非完整約束 PAGEREF _Toc327252659 h

19、 17HYPERLINK l _Toc3272526602.3.2 雙機閉環(huán)約束 PAGEREF _Toc327252660 h 18HYPERLINK l _Toc3272526612.3.3 碰撞檢測 PAGEREF _Toc327252661 h 19HYPERLINK l _Toc3272526622.4 本章小結(jié) PAGEREF _Toc327252662 h 20HYPERLINK l _Toc3272526633 基于RRTConnect算法的雙機路徑規(guī)劃方法 PAGEREF _Toc327252663 h 21HYPERLINK l _Toc3272526643.1 問題描述

20、PAGEREF _Toc327252664 h 21HYPERLINK l _Toc3272526653.2 問題解決 PAGEREF _Toc327252665 h 21HYPERLINK l _Toc3272526663.2.1 RRTConnect算法 PAGEREF _Toc327252666 h 22HYPERLINK l _Toc3272526673.2.2 始末位姿確定 PAGEREF _Toc327252667 h 25HYPERLINK l _Toc3272526683.2.3 路徑優(yōu)化 PAGEREF _Toc327252668 h 26HYPERLINK l _Toc32

21、72526693.3 案例演示與分析 PAGEREF _Toc327252669 h 27HYPERLINK l _Toc3272526703.3.1 案例一 PAGEREF _Toc327252670 h 27HYPERLINK l _Toc3272526713.3.2 案例二 PAGEREF _Toc327252671 h 30HYPERLINK l _Toc3272526723.3.3 案例三 PAGEREF _Toc327252672 h 34HYPERLINK l _Toc3272526733.3.4 案例分析 PAGEREF _Toc327252673 h 37HYPERLINK

22、l _Toc3272526743.4 本章小結(jié) PAGEREF _Toc327252674 h 38HYPERLINK l _Toc3272526754 改進(jìn)RRTConnect算法的雙機路徑規(guī)劃方法 PAGEREF _Toc327252675 h 39HYPERLINK l _Toc3272526764.1 問題描述 PAGEREF _Toc327252676 h 39HYPERLINK l _Toc3272526774.2 問題解決 PAGEREF _Toc327252677 h 39HYPERLINK l _Toc3272526784.2.1 RRTMultiPhrase算法 PAGER

23、EF _Toc327252678 h 39HYPERLINK l _Toc3272526794.2.2 關(guān)鍵位姿點選擇 PAGEREF _Toc327252679 h 40HYPERLINK l _Toc3272526804.3 案例演示與分析 PAGEREF _Toc327252680 h 41HYPERLINK l _Toc3272526814.3.1 案例一 PAGEREF _Toc327252681 h 41HYPERLINK l _Toc3272526824.3.2 案例二 PAGEREF _Toc327252682 h 46HYPERLINK l _Toc3272526834.3.

24、3 案例分析 PAGEREF _Toc327252683 h 50HYPERLINK l _Toc3272526844.4 本章小結(jié) PAGEREF _Toc327252684 h 50HYPERLINK l _Toc327252685結(jié)論 PAGEREF _Toc327252685 h 51HYPERLINK l _Toc327252686參考文獻(xiàn) PAGEREF _Toc327252686 h 53HYPERLINK l _Toc327252687附錄A 主要符號的意義 PAGEREF _Toc327252687 h 58HYPERLINK l _Toc327252688攻讀碩士學(xué)位期間發(fā)

25、表學(xué)術(shù)論文情況 PAGEREF _Toc327252688 h 59HYPERLINK l _Toc327252689致 PAGEREF _Toc327252689 h 60HYPERLINK l _Toc327252690理工大學(xué)學(xué)位論文使用授權(quán)書 PAGEREF _Toc327252690 h 611 緒論1.1 吊裝路徑規(guī)劃的重要性本文的研究對象為兩臺履帶起重機，簡稱為雙機。保證安全性是起重機吊裝的首要問題。被吊設(shè)備、起重機以與吊裝方式的多樣化、復(fù)雜化等特點決定了起重機吊裝是一類高危險性的活動。對于單臺起重機吊裝，需確保吊裝過程中不發(fā)生碰撞且起重機負(fù)載率在允許的圍之，因其不需協(xié)同，可控性

26、好，吊裝安全性較易得到保證。然而對于兩臺或多臺起重機協(xié)同吊裝，起重機之間的運動相互影響，一臺起重機的動作引起的多機系統(tǒng)整體位姿變化和載荷重分配難以確定，其吊裝的危險性要比想象嚴(yán)重得多，極容易出現(xiàn)負(fù)載不均引起某臺起重機臂架折斷或整機傾翻，隨后形成多米諾骨牌效應(yīng)，可能會導(dǎo)致所有起重機全部翻車。多機吊裝失敗造成巨大經(jīng)濟(jì)損失，甚至車毀人亡的案例比比皆是。如，1993年在澳大利亞昆士，兩臺Lampson起重機M4100和M4600協(xié)同吊裝一個大跨度的鋼架立片時，因吊裝方案制定階段起重機動作規(guī)劃不當(dāng)，致使實施過程中M4100嚴(yán)重超載，造成此起重機臂架折斷的重大事故，如圖1.1所示。2008年1月美國圣彼德

27、斯堡市，六臺汽車式起重機協(xié)同吊裝一根用于電力的巨大鋼管道時，由于一臺起重機超載致使上車傾翻，造成了人員傷亡和巨大的經(jīng)濟(jì)損失，如圖1.2所示。2009年7月印度新德里，四臺起重機協(xié)同吊起一個巨大鋼梁，由于其中一臺起重機的誤操作致使另外三臺起重機無法承受鋼梁重量而被砸翻，造成至少四至六人受傷的嚴(yán)重后果。而在國也不乏類似的案例。因此，保證安全性是起重機吊裝尤其多機協(xié)同作業(yè)的首要問題。 圖1.1 1993年在澳大利亞昆士蘭事故 圖1.2 2008年在美國圣彼德斯堡事故 Fig. 1.1 Accident in QueenslandAustralia Fig. 1.2 Accident in St Pe

28、tersburgAmerica in 1993in Jan. 2008以上事件的發(fā)生歸根結(jié)底是方案本身不安全和實際執(zhí)行時誤造作并未能與時修正。對于吊裝方案制定，傳統(tǒng)方法存在嚴(yán)重不足，例如：a. 由CAD設(shè)計軟件自身的限制致使關(guān)鍵點的分析和選取不夠全面，難以保證安全性；b. 路徑規(guī)劃涉與碰撞、起重性能、環(huán)境因素等多方面容，制定過程工作非常繁雜，反復(fù)進(jìn)行大量查閱資料和計算任務(wù)，耗時長；c. 關(guān)鍵點之間的路徑規(guī)劃嚴(yán)重依賴于指揮人員的主觀判斷，大大提高對方案制作人員的要求。吊裝路徑規(guī)劃是近年來所采用的保證安全性的新型吊裝技術(shù)，即在有障礙物的環(huán)境，按照一定的評價標(biāo)準(zhǔn)，尋找一條從起吊狀態(tài)（起吊時刻各起重機

29、位姿）到就位狀態(tài)（就位時刻各起重機位姿）的無碰撞優(yōu)化路徑。此處路徑定義為起重機吊裝被吊設(shè)備過程中，按時間順序組成的每臺起重機的動作（起升、變幅、回轉(zhuǎn)、行走）序列。吊裝路徑規(guī)劃具有安全性、高效性、指導(dǎo)性等優(yōu)點，能很好的解決傳統(tǒng)方法存在的不足，在仿真基礎(chǔ)上提出自動尋找路徑的方法，因此，吊裝路徑規(guī)劃是保證安全性的重要手段。1.2 吊裝路徑規(guī)劃研究現(xiàn)狀一直從事起重機吊裝技術(shù)研究的著名專家Koshy Varghese教授與其團(tuán)隊是最早開展移動式起重機路徑規(guī)劃研究的學(xué)者，于1997年Raghunatha Reddy, H在他碩士論文中提出一種基于圖論的單臺起重機路徑規(guī)劃方法 ADDIN NE.Ref.51

30、0AC75D-3D8C-4CFD-80E0-7C8E8B22BBA61。于2002年他提出一種二階段搜索的單臺起重機路徑規(guī)劃方法 ADDIN NE.Ref.CCE1A585-C1C0-4894-AAD8-97C959D6389A2，第一階段結(jié)合爬山策略采用深度優(yōu)先圖遍歷的方法在無碰撞空間中找到一條可行路徑，然后在第二階段對此可行路徑采用啟發(fā)式函數(shù)進(jìn)行優(yōu)化。該方法特點是在搜索之前需要將起重機的位形空間以一定的步長離散成點，并用碰撞檢測函數(shù)構(gòu)造無碰撞的搜索圖。因構(gòu)造圖需要大量的計算，因而該算法效率較低。為了檢驗基于隨機采樣規(guī)劃方法在起重機路徑規(guī)劃中的性能，王欣等人采用雙向RRT（Bi-direct

31、ional RRT）規(guī)劃不考慮行走的單臺履帶起重機的吊裝路徑 ADDIN NE.Ref.B365ED53-72BA-45E1-8C25-B58D3FFE4A143，該方法考慮了起重機吊鉤旋轉(zhuǎn)自由度，案例表明，該方法求解效率很高且路徑近似最優(yōu)。針對動態(tài)的作業(yè)環(huán)境，Cheng Zhang提出一種實時的在線單臺起重機吊裝路徑規(guī)劃方法 ADDIN NE.Ref.52354DEA-6B16-47F3-970D-C767746D544A4, 5，在執(zhí)行離線規(guī)劃出來的路徑過程中，算法采用UWB RTLS系統(tǒng)（ultra wideband Real-Time Location Systems）收集當(dāng)前作業(yè)環(huán)境

32、數(shù)據(jù)、更新環(huán)境模型，然后若有必要則采用DRRT規(guī)劃算法（RRT的變種）重新規(guī)劃路徑，若規(guī)劃成功則沿著更新后的路徑繼續(xù)工作，直至吊裝任務(wù)完成。該方法結(jié)合環(huán)境感知技術(shù)（傳感器、定位系統(tǒng)等）實現(xiàn)吊裝過程的監(jiān)控和起重機吊裝路徑的實時規(guī)劃，在一定程度上提高了吊裝的安全性。海事大學(xué)黃有方課題組對集裝箱吊裝的路徑規(guī)劃做了一定的研究，建立了以最短路徑為目標(biāo)函數(shù)、無碰撞為約束條件的集裝箱裝卸操作最優(yōu)路徑的單目標(biāo)數(shù)學(xué)模型 ADDIN NE.Ref.88A45948-F022-4FD7-9015-1A91BF219B0E6, 7。豐橋技術(shù)科學(xué)大學(xué)的 HYPERLINK :/ engineeringvillage /

33、controller/servlet/Controller?CID=expertSearchCitationFormat&searchWord1=%7bTerashima%2C+Kazuhiko%7d+WN+AU&database=1&yearselect=yearrange&searchtype=Expert&sort=yr Terashima, Kazuhiko、杜蘭大學(xué)的 HYPERLINK :/ engineeringvillage /controller/servlet/Controller?CID=expertSearchCitationFormat&searchWord1=%7b

34、Lee%2C+Ho-Hoon%7d+WN+AU&database=1&yearselect=yearrange&searchtype=Expert&sort=yr Lee, Ho-Hoon、okuyamna College of Teclmology的Akamatsu, T.等人對橋式起重機的吊裝進(jìn)行路徑規(guī)劃進(jìn)行了大量的研究，主要研究單臺起重機在高速吊裝過程中如何規(guī)劃其動作并進(jìn)行控制，以實現(xiàn)安全、高效的吊裝 ADDIN NE.Ref.F3659571-FB84-4692-90C0-E22412AB38BB8-11。另外，SunNing等國立大學(xué)土木系的康仕仲課題組提出的基于增量解耦多塔機協(xié)同路

35、徑規(guī)劃 ADDIN NE.Ref.3EF1F992-40F2-4E9E-8933-A87F7869FE9112, 13。1.3 雙機吊裝路徑規(guī)劃研究現(xiàn)狀隨著兩臺起重機協(xié)同吊裝日趨普遍， Sivakumar, P. L.應(yīng)用A*算法、爬山算法進(jìn)行雙機協(xié)同吊裝路徑規(guī)劃 ADDIN NE.Ref.F5D05B76-BA7C-4BBF-8414-067FABA12FD214，實驗表明爬山算法比A*算法能快速找到可行路徑但路徑不優(yōu)，而A*算法能找到較優(yōu)的路徑但耗時長。因A*算法、爬山算法這類基于幾何構(gòu)造規(guī)劃方法均需要構(gòu)造龐大的無碰撞搜索圖，其計算復(fù)雜度隨著起重機的自由度與空間離散分辨率呈指數(shù)增長，難以勝

36、任帶高自由度的起重機吊裝路徑規(guī)劃。為此，M.S.Ajmal Deen Ali和Sivakumar, P. L.等人面向兩臺起重機協(xié)同吊裝提出一種基于遺傳算法（GA）的路徑規(guī)劃方法 ADDIN NE.Ref.9F4695A6-F634-4DEE-8C5C-258322F0ECA615-19，該方法采用固定長度的串表示吊裝路徑，根據(jù)位形間的偏移量構(gòu)造適應(yīng)度函數(shù)，應(yīng)用遺傳算法的選擇、交叉、變異等操作不斷演化路徑種群，最終求得較優(yōu)吊裝路徑，從文獻(xiàn)中的實驗可以看到，相比A*算法，遺傳算法的計算效率提高了1020倍，所得路徑長度相當(dāng)。該方法雖然避免空間的幾何構(gòu)造而提高了計算性能，但其也存在一些不足，比如路

37、徑必須由數(shù)量固定的位形構(gòu)成（等長的個體）、收斂速度與路徑的質(zhì)量難以控制等。為了克服路徑必須由數(shù)量固定位形構(gòu)成的不足，王欣、玉院等人采用蟻群算法進(jìn)行單臺起重機和兩臺起重機路徑規(guī)劃 ADDIN NE.Ref.AD1C54A3-5566-4986-AD53-C044FAE5AA4420, 21，該方法將位形間距離、碰撞、起重機動作優(yōu)先級與切換等因素融入路徑點選擇策略和信息素更新中，該方法能找到近似最優(yōu)的路徑且無需要求路徑由確定數(shù)量的位形構(gòu)成。但蟻群算法息素因子、啟發(fā)式因子與信息殘留系數(shù)較難選擇，且計算時間長。為了進(jìn)一步提高吊裝路徑規(guī)劃的計算效率，Yu-Cheng Chang于2012年提出一種基于概

38、率路標(biāo)法（PRM，Probabilistic roadmaps Method）規(guī)劃單臺起重機和兩臺起重機協(xié)同吊裝的路徑 ADDIN NE.Ref.EFDCEE86-9DC6-4C3F-9A39-3FF1AEEC0C7522，該方法先將起重機的回轉(zhuǎn)、變幅自由度作為位形的變量（此時暫未考慮起升自由度），在此位形空間中采用PRM規(guī)劃出一條無碰撞的吊裝路徑，然后在此路徑的基礎(chǔ)上進(jìn)行起重機起升動作的規(guī)劃，從而最終得到一條可行的無碰撞吊裝路徑。實驗顯示這種將自由度分解降維進(jìn)行分步規(guī)劃的方法可以提高規(guī)劃的效率，相比遺傳算法效率提高了數(shù)十倍，對于一些相對較為簡單的吊裝環(huán)境，該方法幾乎達(dá)到實時。針對吊裝路徑的平

39、滑性問題，文獻(xiàn) ADDIN NE.Ref.047CEBAD-BF8B-4719-AC08-04B181CA2CD223采用四次樣條光滑遺傳算法得到的兩臺起重機協(xié)同吊裝路徑。雙機協(xié)同吊裝系統(tǒng)可視為兩個移動式機器人協(xié)同作業(yè)。因此本文研究的問題與多機器人協(xié)作物體操作（Multi-robot Cooperative Object Operation）問題有一定相似性。然而雙機路徑規(guī)劃為多種困難問題的結(jié)合體：a. 高維自由度問題；b. 協(xié)同問題（其中的閉環(huán)約束問題需要進(jìn)一步的研究和解決）；c. 行走非完整約束問題。移動式起重機是一種用于吊裝的剛?cè)狁詈系臋C構(gòu)，可被看成是一種特殊機器人。它與傳統(tǒng)的移動式機械

40、臂相比，從起重機機構(gòu)和作業(yè)特點上來看，具有剛?cè)峄旌稀C構(gòu)尺寸可變、起升能力敏感等特征。1.4 路徑規(guī)劃方法綜述（1） 路徑規(guī)劃方法分類作為機器人研究領(lǐng)域的一個基本問題，路徑規(guī)劃經(jīng)歷近二、三十年的發(fā)展，已出現(xiàn)許多規(guī)劃算法，主要分為三類：a. 基于自由空間幾何構(gòu)造的規(guī)劃方法與前向圖搜索算法；b. 智能規(guī)劃方法；c. 基于隨機采樣的規(guī)劃方法?；谧杂煽臻g幾何構(gòu)造的規(guī)劃方法與前向圖搜索算法主要有可視圖 ADDIN NE.Ref.D8946B9E-BAFD-4986-A062-8F05731D2B2324, 25、柵格分解 ADDIN NE.Ref.B466A019-DA84-4857-A346-C1C

41、B05441EE126-28、Voronoi圖 ADDIN NE.Ref.F44B2936-2C09-4DF7-9057-B1C79690222228, 29、Dijkstra算法 ADDIN NE.Ref.2192CF72-5091-4ABC-99F0-DD2C59B7B15A30, 31、A*算法 ADDIN NE.Ref.A9D41578-F4D8-4929-98B5-C2AEB9E0BD8B30以與人工勢場法 ADDIN NE.Ref.988581DB-0DB5-4ADB-82FC-AFDAF796FD5632, 33等等，這些方法對于很多規(guī)劃問題都具備了很強的適應(yīng)性，但當(dāng)面對高自由度

42、機器人路徑規(guī)劃問題時，其計算復(fù)雜度將隨自由度呈指數(shù)增長，而且對對微分約束和復(fù)雜環(huán)境也缺乏較好的解決辦法。智能規(guī)劃方法主要包括遺傳算法 ADDIN NE.Ref.02B21AB0-9764-4D24-B121-BCE147BE06DD34-38、蟻群算法 ADDIN NE.Ref.D052B850-9288-4EE3-B255-C42D5AFF9A8B39, 40和人工神經(jīng)網(wǎng)絡(luò)方法 ADDIN NE.Ref.9C84C3B4-F578-401A-AFF8-ED3992EC8A9541-44等等，這些方法可以得到最優(yōu)或者近似最優(yōu)路徑，但是收斂速度和有效性難以保證，并且需要設(shè)置的經(jīng)驗參數(shù)太多，不利于

43、自動處理?；陔S機采樣的規(guī)劃方法是路徑規(guī)劃的新手段?；陔S機采樣的方法是在隨機采樣理論的基礎(chǔ)上發(fā)展而來的一類路徑規(guī)劃新方法，其僅僅通過對位形空間或狀態(tài)空間中的采樣點進(jìn)行碰撞檢測來獲取障礙物信息, 避免了對空間的建模，且在高維空間中的搜索效率很高，因而這類方法更適合于求解高自由度機器人在復(fù)雜環(huán)境中的規(guī)劃問題，而且對帶有微分約束的規(guī)劃問題也具有較強的解決能力。概率路標(biāo)法（PRM，Probabilistic Roadmaps Method） ADDIN NE.Ref.7E95619C-C936-4890-8433-CCF1106CF9ED45-51和快速隨機生成樹方法（RRT，Rapidly-Exp

44、loring Random Trees） ADDIN NE.Ref.784AD3D7-AFF9-47F3-BCB4-19B20C218B933, 29, 52-57是目前最成功的兩種基于采樣的路徑規(guī)劃方法。PRM方法是通過在整個空間采樣得到若干個采樣點，并由這些采樣點構(gòu)成一概率地圖，最后在地圖中搜索得到合適的路徑，其在高維靜態(tài)空間中具有良好的表現(xiàn)。RRT算法遵循控制理論的系統(tǒng)狀態(tài)方程，在控制量的作用下增量式地產(chǎn)生新狀態(tài)直至到達(dá)目標(biāo), 這使它很容易滿足系統(tǒng)運動動力學(xué)約束方面的要求，且適用于動態(tài)環(huán)境?；陔S機采樣的規(guī)劃方法因其優(yōu)良的特性已被廣泛應(yīng)用于機器人學(xué)、計算機動畫、工業(yè)設(shè)計、生物計算等各領(lǐng)域

45、的路徑規(guī)劃問題中，并已成為當(dāng)前路徑規(guī)劃研究的熱點。本文雙機路徑規(guī)劃為高自由度問題，并且是典型的非完整約束問題，因此采用基于RRTConnect算法的方法作為解決手段。S.M.LaVall等人于1998年提出了一種基于采樣的路徑規(guī)劃方法快速隨機搜索樹算法（Rapidly-exploring RandomTree，RRT），由于此方法在高維空間中具有突出表現(xiàn)，以與在規(guī)劃過程中可以引入運動學(xué)約束，因此目前RRT被廣泛應(yīng)用于許多路徑規(guī)劃問題中。（2） 基本RRT算法設(shè)C為路徑規(guī)劃問題的狀態(tài)空間，Cfree（CfreeC）為與障礙物無碰撞的機器人自由空間，Cobst （CobstC）為與障礙物發(fā)生碰撞的

46、機器人碰撞空間，T表示含有k個節(jié)點的隨機樹，且TCfree，Xinit（Xinit T）為樹的初始點即初始姿態(tài)，Xgoal（Xgoal T）為樹的目標(biāo)點即目標(biāo)姿態(tài)。基本RRT算法流程：BULD_RRT(Xinit)T.init (Xinit);While(Xgoal not in T )Xrand, Xnear SELECT_NODE(T);EXTEND( T, Xrand, Xnear);Return T;SELECT_NODE(T)Xrand RANDOM_STATE();Xnear NEAREST_NEIGHBOR(X,T);return Xrand,Xnear ;EXTEND(T, X

47、rand,Xnear)If (NEW_STATE (Xrand,Xnear,Xnew,u) )thenT.add_vertex (Xnew);T.add_edge (Xnear,Xnew, u);Return;根據(jù)基本RRT算法流程與圖1.3的可知，基本RRT的算法為首先以初始點Xinit作為樹T的根節(jié)點；在Cfree中用函數(shù)RANDOM_STATE( )隨機選擇一個隨機點Xrand，即使得XrandCfree；再用函數(shù)NEAREST_NEIGHBOR( )搜索樹上離Xrand最近的節(jié)點用來擴展，這個節(jié)點被稱為Xnear；用函數(shù)EXTEND( )來擴展樹，即隨機或是根據(jù)給定的標(biāo)準(zhǔn)，選擇一個輸入

48、u，使得Xnear向Xrand靠近，這時產(chǎn)生一個新節(jié)點Xnew，如果檢測沒有碰撞或滿足要求，將Xnew加到樹中。如此重復(fù)直到子節(jié)點集中包含目標(biāo)姿態(tài)點Xgoal或子節(jié)點集中有節(jié)點在目標(biāo)區(qū)域時終止算法執(zhí)行，此時即找了一條以隨機樹T中節(jié)點組成的從初始姿態(tài)Xinit到目標(biāo)姿態(tài)Xgoal的路徑。圖1.3 隨機樹擴展示意圖Fig. 1.3Diagram of RRT expanding（3） 改進(jìn)RRT算法基本RRT主要缺陷在于其為了找到目標(biāo)點需要在整個空間進(jìn)行搜索，效率很低。為提高搜索的效率，與路徑的質(zhì)量，很多學(xué)者對基本RRT進(jìn)行了改進(jìn)，形成了一些改進(jìn)版本的RRT算法，這些改進(jìn)的RRT算法通常可分為以下

49、三大類。 改進(jìn)分支擴展方式的RRT改進(jìn)分支擴展方式的RRT包括RRTGoalBias ADDIN NE.Ref.58546FCD-5B63-4D8F-B4FE-CF17D5CE0F5458, 59、RRTConnect ADDIN NE.Ref.92C9F81F-EBFB-4844-A857-0FF7DB82A0E860, 61等。RRTGoalBias：此種改進(jìn)RRT方法在擴展過程中不是完全以隨機點作為牽引點而是以一定概率用目標(biāo)點作為的牽引點。RRTGoalBias方法可使樹快速向目標(biāo)點增長，但是當(dāng)過多偏向目標(biāo)點時可能會使樹的生長陷入局部最優(yōu)。RRTConnect：RRTConnect的基本

50、思想是使單步擴展的距離盡可能遠(yuǎn)，如下圖所示該算法將基本RRT的單步擴展改進(jìn)為具有貪婪性質(zhì)的多步擴展，直到碰到障礙或到達(dá)目標(biāo)點才結(jié)束一次擴展迭代。應(yīng)用此多步擴展的方式可以有效避免陷入局部最優(yōu)的可能，并且在相對開闊的區(qū)域RRTConnect可以快速向未探索的區(qū)域擴展從而可以大大提高生成樹的效率。 增加隨機樹的數(shù)量雙棵樹RRT：雙棵樹RRT方法包括RRTExtExt、RRTExtCon、RRTConCon等，這些方法都是分別以起點和目標(biāo)點作為樹根，分別以單步或多步擴展的方式生長兩棵樹，直到兩棵樹相遇，此時即找到了從起點到終點的路徑。此方法由于采用兩棵樹同時生長，大大提高了搜索的效率，尤其是雙向都是多

51、步生長的RRTConCon方法具有很好的搜索特性，廣泛應(yīng)用于各路徑規(guī)劃問題中。MultiRRT：MultiRRT采用多棵樹同時生長的方式進(jìn)行路徑規(guī)劃，此方法除了應(yīng)用初始點和目標(biāo)點分別為樹根構(gòu)造兩棵樹外，還采用橋測試的方法取到狹窄通道的點，并分別以這些點為樹根分別生成樹，當(dāng)兩棵樹相遇則將這兩棵樹合并成一棵樹，直到某一棵樹中即包含了初始點又包含目標(biāo)點此時意味著已經(jīng)找到了從初始點到目標(biāo)點的路徑。此方法因為增加了在狹窄通道生長的樹，使得該方法應(yīng)用于多狹窄通道的問題時具有十分好的特性。 應(yīng)用RRT的搜索信息VLRRT：此方法是將樹中的每個節(jié)點都關(guān)聯(lián)一個關(guān)于生長步長的參數(shù)r，每次生長的步長都由生長點的r值

52、決定，并且r的值會根據(jù)此生長點是否可以成功生長而實時變化。如當(dāng)node1（r = 2）為生長點時，以node1為生長點以2為步長生長新的的節(jié)點node2，如成功生長則將node2的r值設(shè)為2，并增大node1的r值，如生長失敗則減小node1的r值。應(yīng)用此方法可以根據(jù)環(huán)境的特點實時調(diào)整生長的步長，使步長的選擇更加合理。1.5 課題的目的意義與主要工作容從以上的發(fā)展現(xiàn)狀可以看出，面向雙機協(xié)同吊裝的路徑規(guī)劃是具有明確的應(yīng)用背景和相當(dāng)研究難度的研究課題，傳統(tǒng)的技術(shù)和方法很難適應(yīng)實際問題的需求，因而需要開展進(jìn)一步的探索工作，吊裝方案制定的安全性、合理性和高效性亟待提高，計算機輔助路徑規(guī)劃將成為重要的手

53、段。然而，關(guān)于起重機路徑規(guī)劃的相關(guān)研究在國尚未較好的展開，國外雖然針對吊裝行業(yè)有較多的相關(guān)研究，但應(yīng)用輔助吊裝方案制作的并不多見，因此把路徑規(guī)劃應(yīng)用于輔助吊裝方案制作有著重要的工程應(yīng)用意義和先進(jìn)性，并且由路徑規(guī)劃展開的研究多針對單機。目前關(guān)于雙機路徑規(guī)劃的研究一般只考慮起升、回轉(zhuǎn)和變幅三個動作，且只針對平移搬運設(shè)備的吊裝任務(wù)。而在一些實際吊裝項目中起重機直線行走和轉(zhuǎn)彎必不可少，否則無法完成吊裝任務(wù)；并且建筑工程中同時存在將被吊設(shè)備平移搬運以與將被吊設(shè)備從水平狀態(tài)豎直并安裝的任務(wù)?？梢妼﹄p機路徑規(guī)劃作進(jìn)一步研究非常必要，對路徑規(guī)劃中存在的高自由度、閉環(huán)約束、行走非完整約束等問題進(jìn)行研究解決，具有

54、一定的科學(xué)意義。本文以提高吊裝方案制定的合理性，高效性和可靠性為目標(biāo)，以兩臺移動式起重機吊裝作業(yè)為基礎(chǔ)，著重對雙機吊裝系統(tǒng)研究對象進(jìn)行分析，構(gòu)建幾何和問題模型以應(yīng)用RRTConnect算法進(jìn)行尋路，并提出RRTMultiPhrase算法解決了雙機路徑規(guī)劃更復(fù)雜的問題，實現(xiàn)在給定雙機初始和目標(biāo)位姿信息的情況下，在C空間中搜索到滿足無碰撞、實時保證繩偏角要求、起重性能和履帶起重機行走特性等約束的路徑。該方法適用于雙機平移設(shè)備和翻轉(zhuǎn)設(shè)備兩種吊裝任務(wù)，同時，雙機均可以通過直線行走、轉(zhuǎn)彎、起升、變幅、回轉(zhuǎn)等動作完成。本文的主要研究工作：（1） 研究當(dāng)前機器人和起重機路徑規(guī)劃的研究成果，總結(jié)路徑規(guī)劃算法。

55、（2） 研究雙機吊裝系統(tǒng)結(jié)構(gòu)，分析履帶起重機的動作特點，將雙機簡化為具有十二個自由度的機器人，建立幾何模型和可視化模型。（3） 分析吊裝路徑需要滿足的約束，重點研究了滿足行走非完整約束和閉環(huán)約束的實現(xiàn)方法，構(gòu)建適用于RRTConnect算法解決的數(shù)學(xué)模型，并根據(jù)雙機研究對象對數(shù)學(xué)模型中的名詞變量做了具體定義。（4） 實現(xiàn)用RRTConnect算法解決雙機路徑規(guī)劃問題，設(shè)計三個典型吊裝案例并分析用該方法進(jìn)行路徑規(guī)劃的結(jié)果，證實其可行性。（5） 改進(jìn)RRTConnect算法，提出基于關(guān)鍵位姿點的RRTMultiPhrase算法，設(shè)計兩個復(fù)雜的吊裝案例，對比三種不同方法分別進(jìn)行路徑規(guī)劃的結(jié)果，說明提

56、出算法的優(yōu)缺點和可行性。本文的容大致安排如下：第一章對吊裝路徑規(guī)劃的重要性，以與吊裝路徑規(guī)劃尤其雙機吊裝路徑規(guī)劃以與路徑規(guī)劃方法進(jìn)行概述，提出本文的研究目的和意義。第二章對雙機路徑規(guī)劃問題進(jìn)行深入剖析，構(gòu)建雙機吊裝數(shù)學(xué)模型，并對模型中相關(guān)變量進(jìn)行定義，說明了路徑滿足約束的方法。第三章對論述了采用RRTConnect算法解決雙機路徑規(guī)劃問題的過程，通過典型的實例分析，證實了該方法的可行性、靈活性和可控性。第四章提出了基于關(guān)鍵位姿的RRTMultiPhrase算法，以解決雙機吊裝中較為復(fù)雜的吊裝任務(wù)路徑規(guī)劃，接著對比分析了同一個問題用三種方法得到的結(jié)果，驗證其有效性。最后總結(jié)全文，并給出需進(jìn)一步展

57、開研究的方向和容。2 雙機吊裝路徑規(guī)劃數(shù)學(xué)模型雙機吊裝主要有兩種形式：一種為兩臺起重機協(xié)同完成被吊設(shè)備的轉(zhuǎn)移，在此過程中設(shè)備不翻轉(zhuǎn)，一般使用兩臺完全一樣的起重機，并且雙機的位姿、動作是對稱的，后文中用起重機A和起重機B表示；一種為兩臺起重機協(xié)同將設(shè)備翻轉(zhuǎn)，一臺完成主要的起升任務(wù)，稱為主起重機，用起重機A表示，另一臺通過簡單的配合動作直到設(shè)備豎直，稱為溜尾起重機，用起重機B表示，起重機B與設(shè)備脫離后完成雙機吊裝任務(wù)，之后由起重機A轉(zhuǎn)移并安裝設(shè)備以完成整個吊裝任務(wù)。本文研究的路徑規(guī)劃即針對以上兩種情況的雙機吊裝過程。2.1 數(shù)學(xué)模型雙機路徑規(guī)劃是指已知雙機的初始和目標(biāo)位姿以與吊裝現(xiàn)場的環(huán)境設(shè)施，找

58、到從初始位姿到目標(biāo)位姿的的滿足約束的雙機動作序列，即按時間順序依次執(zhí)行的動作類型和動作量。因此，對雙機路徑規(guī)劃問題數(shù)學(xué)描述如下： P = ， （2.1）式中，位姿空間，用雙機的各自由度與其取值圍描述；雙機的初始位姿；雙機的目標(biāo)位姿；每一步可選擇的輸入集；位姿空間約束，雙機的各個自由度在其取值圍；起重性能約束，雙機均滿足一定的負(fù)載率要求；無碰撞約束，吊裝過程中起重機、被吊設(shè)備和環(huán)境三者之間無碰撞；閉環(huán)約束，雙機、被吊設(shè)備和地面組成閉環(huán)，允許起重機動作時吊索具的偏角在設(shè)定的圍；行走特性約束，履帶起重機行走為差分運動形式，需滿足非完整約束；路徑長度約束，即期望兩吊點在吊裝過程中運動軌跡長度最短。本文

59、提出的算法需滿足以下假設(shè)：（1） 吊裝過程中環(huán)境為靜止的，起重機的下車、轉(zhuǎn)臺、臂架以與被吊設(shè)備模型均簡化為長方體；（2） 被吊設(shè)備重心在兩個吊點連線上，因此整個吊裝過程中分配到兩臺起重機上的重量不變，將臂架仰角限定在一定圍可滿足負(fù)載率約束，即轉(zhuǎn)化為位姿空間的約束。2.2 名詞定義2.2.1 剛體模型研究雙機路徑規(guī)劃問題首先要對雙機、被吊設(shè)備與場地中的障礙物建立三維模型。本文將這些真實的物理模型進(jìn)行抽象，建立相應(yīng)的簡單剛體模型。將雙機和設(shè)備簡化為9個剛體，包括雙機的下車、轉(zhuǎn)臺、臂架、吊索具以與被吊設(shè)備，除了吊索具以外的7個剛體為由6個面包圍的長方體，如圖2.1所示。本文中障礙物剛體模型也簡化為長

60、方體。由于本文研究的是靜態(tài)環(huán)境下的雙機路徑規(guī)劃，障礙物為靜態(tài)物體，雙機和被吊設(shè)備為運動物體。因此，障礙物的建模需要各自的位置和尺寸信息，而雙機和設(shè)備隨時間變化位姿不斷轉(zhuǎn)變，其建模相對復(fù)雜，需要各個剛體的尺寸信息即雙機和設(shè)備固有的尺寸信息包括9個長方體的長寬高，并且需要剛體間的相對位置數(shù)據(jù)。0：起重機A下車；1：起重機A轉(zhuǎn)臺；2：起重機A臂架；3：起重機A吊索具；4：起重機B下車；5：起重機B轉(zhuǎn)臺；6：起重機B臂架；7：起重機B吊索具；8：被吊設(shè)備圖2.1 雙機和設(shè)備模型Fig. 2.1 Model of dual-crane system建立了表示雙機和設(shè)備各個部分的剛體模型，我們需要通過剛體