【文章內(nèi)容簡介】 提出一種二階段搜索的單臺起重機路徑規(guī)劃方法 [2]，第一階段 結(jié)合爬山策略采用深度優(yōu)先圖遍歷的方法在無碰撞空間中找到一條可行路徑，然后在第二階段對此可行路徑采用啟發(fā)式函數(shù)進行優(yōu)化。該方法特點是在搜索之前需要將起重機的位形空間以一定的步長離散成點，并用碰撞檢測函數(shù)構(gòu)造無碰撞的搜索圖。因構(gòu)造圖需要大量的計算，因而該算法效率較低。為了檢驗基于隨機采樣規(guī)劃方法在起重機路徑規(guī)劃中的性能，王欣等人采用雙向 RRT（ Bidirectional RRT） 規(guī)劃不考慮行走的單臺履帶起重機的吊裝路徑 [3]，該方法考慮了起重機吊鉤旋轉(zhuǎn)自由度，案例表明，該方法求解效率很高且路徑近似最優(yōu)。針對動態(tài)的作業(yè)環(huán)境， Cheng Zhang 提出一種實時的在線單臺起重機吊裝路徑規(guī)劃方法 [4, 5]，在執(zhí)行離線規(guī)劃出來的路徑過程中，算法采用 UWB RTLS系統(tǒng)（ ultra wideband RealTime Location Systems）收集當(dāng)前作業(yè)環(huán)境數(shù)據(jù)、更新環(huán)境模型，然后若有必要則采 用 DRRT規(guī)劃算法（ RRT 的變種）重新規(guī)劃路徑，若規(guī)劃成功則沿著更新后的路徑繼續(xù)工作，直至吊裝任務(wù)完成。該方法結(jié)合環(huán)境感知技術(shù)（傳感器、定位系統(tǒng)等）實現(xiàn)吊裝過程的監(jiān)控和起重機吊裝路徑的實時規(guī)劃，在一定程度上提高了吊裝的安全性。 大連理工大學(xué)碩士學(xué)位論文 3 上海海事大學(xué) 黃有方 課題組對集裝箱吊裝的路徑規(guī)劃做了一定的研究，建立了以最短路徑為目標(biāo)函數(shù)、無碰撞為約束條件的集裝箱裝卸操作最優(yōu)路徑的單目標(biāo)數(shù)學(xué)模型 [6, 7]。 豐橋技術(shù)科學(xué)大 學(xué) 的 Terashima, Kazuhiko、 杜蘭大學(xué) 的 Lee, HoHoon、 okuyamna College of Teclmology 的 Akamatsu, 重機的吊裝進行路徑規(guī)劃進行了大量的研究，主要研究單臺起重機在高速吊裝過程中如何規(guī)劃其動作并進行控制，以實現(xiàn)安全、高效的吊裝 [811]。 另外， Sun Ning 等 臺灣國立大學(xué)土木系的康仕仲課題組提出的基于增量解耦多塔機協(xié)同路徑規(guī)劃 [12, 13]。 雙機吊裝路徑規(guī)劃研究現(xiàn)狀 隨著兩臺 起重機協(xié)同吊裝日趨普遍， Sivakumar, P. A*算法、爬山算法進行雙機協(xié)同吊裝路徑規(guī)劃 [14]，實驗表明爬山算法比 A*算法能快速找到可行路徑但路徑不優(yōu)，而 A*算法能找到較優(yōu)的路徑但耗時長。因 A*算法、爬山算法這類基于幾何構(gòu)造規(guī)劃方法均需要構(gòu)造龐大的無碰撞搜索圖，其計算復(fù)雜度隨著起重機的自由度及空間離散分辨率呈指數(shù)增長，難以勝任帶高自由度的起重機吊裝路徑規(guī)劃。為此， . Ajmal Deen Ali 和 Sivakumar, P. 協(xié)同吊裝提出一種基于遺傳算法（ GA）的路徑規(guī)劃方法 [1519]，該方法采用固定長度的串表示吊裝路徑，根據(jù)位形間的偏移量構(gòu)造適應(yīng)度函數(shù)，應(yīng)用遺傳算法的選擇、交叉、變異等操作不斷演化路徑種群，最終求得較優(yōu)吊裝路徑，從文獻(xiàn)中的實驗可以看到，相比 A*算法，遺傳算法的計算效率提高了 10~20 倍，所得路徑長度相當(dāng)。該方法雖然避免空間的幾何 構(gòu)造而提高了計算性能，但其也存在一些不足，比如路徑必須由數(shù)量固定的位形構(gòu)成（等長的個體）、收斂速度及路徑的質(zhì)量難以控制等。為了克服路徑必須由數(shù)量固定位形構(gòu)成的不足，王欣、張玉院等人采用蟻群算法進行單臺起重機和兩臺起重機路徑規(guī)劃 [20, 21]，該方法將位形間距離、碰撞、起重機動作優(yōu)先級及切換等因素融入路徑點選擇策略和信息素更新中，該方法能找到近似最優(yōu)的路徑且無需要求路徑由確定數(shù)量的位形構(gòu)成。但蟻群算 法中信息素因子 ? 、啟發(fā)式因子 ? 及信息殘留系數(shù) ? 較難選擇，且計算時間長。為了進一步提高吊裝路徑規(guī)劃的計算效率， YuCheng Chang 于 2020 年提出一種基于概率路標(biāo)法（ PRM， Probabilistic roadmaps Method）規(guī)劃單臺起重機和兩臺起重機協(xié)同吊裝的路徑 [22]，該方法先將起重機的回轉(zhuǎn)、變幅自由度作為位形的變量（此時暫未考慮起升自由度），在此位形空間中采用 PRM 規(guī)劃出一條無碰撞的吊裝路徑，然后在此路徑的基礎(chǔ)上進行起重機起升動作的規(guī)劃，從而最終得到一條可行的無碰撞吊裝路徑。實驗顯示這種將自由度分解降維進行分步規(guī)劃的方法可以提高規(guī)劃的效率，相比遺傳算法效率提高了數(shù)十倍，對于一些基于 RRTConnect 算法的雙機路徑規(guī)劃研究 4 相對較為簡單的吊裝環(huán)境，該方法幾乎達(dá)到實時。 針對吊裝路徑的平滑性問題，文獻(xiàn) [23]采用四次樣條光滑遺傳算法得到的兩臺起重機協(xié)同吊裝路徑。 雙機協(xié)同吊裝系統(tǒng)可視為兩個移動式機器人協(xié)同作業(yè)。因此本文研究的問題與 多機器人協(xié)作物體操作 （ Multirobot Cooperative Object Operation） 問題 有一定相似性。然而雙機 路徑規(guī)劃 為多種困難問題的結(jié)合體 ： a. 高維自由度問題； b. 協(xié)同問題 （ 其中的 閉環(huán)約束問題需要進一步的研究和解決 ） ； c. 行走非 完整 約束問題。移動式起重機是一種用于吊裝的剛?cè)狁詈系臋C構(gòu)，可被看成是一種特殊機器人。它與傳統(tǒng)的移動式機械臂相比，從起 重機機構(gòu)和作業(yè)特點上來看，具有剛?cè)峄旌稀C構(gòu)尺寸可變、起升能力敏感等特征。 路徑規(guī)劃方法綜述 （ 1） 路徑規(guī)劃方法分類 作為機器人研究領(lǐng)域的一個基本問題，路徑規(guī)劃經(jīng)歷近二、三十年的發(fā)展，已出現(xiàn)許多規(guī)劃算法，主要分為三類： a. 基于自由空間幾何構(gòu)造的規(guī)劃方法及前向圖搜索算法； b. 智能規(guī)劃方法； c. 基于隨機采樣的規(guī)劃方法。 基于自由空間幾何構(gòu)造的規(guī)劃方法及前向圖搜索算法主要有可視圖 [24, 25]、柵格分解 [2628]、 Voronoi 圖 [28, 29]、 Dijkstra 算法 [30, 31]、 A*算法 [30]以及人工勢場法[32, 33]等等，這些方法對于很多規(guī)劃問題都具備了很強的適應(yīng)性，但當(dāng)面對高自由度機器人路徑規(guī)劃問題時，其計算復(fù)雜度將隨自由度呈指數(shù)增長，而且對對微分約束和復(fù)雜環(huán)境也缺乏較好的解決辦法。 智能規(guī)劃方法主要包括遺傳算法 [3438]、蟻群算法 [39, 40]和人工神經(jīng)網(wǎng)絡(luò)方法[4144]等等，這些方法可以得到最優(yōu)或者近似最優(yōu)路徑，但是收斂速度和有效性難以保證，并且需要設(shè)置的經(jīng)驗參數(shù)太多，不利于自動處理。 基于隨機采樣的規(guī)劃方法是路徑規(guī)劃的新手段。 基于隨機采樣的方法是在隨機采樣理論的基礎(chǔ)上發(fā)展而來的一類路徑規(guī)劃新方 法，其僅僅通過對位形空間或狀態(tài)空間中的采樣點進行碰撞檢測來獲取障礙物信息 , 避免了對空間的建模，且在高維空間中的搜索效率很高，因而這類方法更適合于求解高自由度機器人在復(fù)雜環(huán)境中的規(guī)劃問題，而且對帶有微分約束的規(guī)劃問題也具有較強的解決能力。概率路標(biāo)法（ PRM， Probabilistic Roadmaps Method） [4551]和快速隨機生成樹方法（ RRT， RapidlyExploring Random Trees） [3, 29, 5257]是目前最成功的兩種基于采樣的路徑規(guī)劃方法。 PRM 方法是通過在整個空間內(nèi)采樣得到若干個采樣點，并由這些采樣點構(gòu)成一張概率地圖，最后在地圖中搜索得到合適的路徑，其在高維靜態(tài)空間中具有良好的表現(xiàn)。 RRT 算法遵循控制理論的系統(tǒng)狀態(tài)方程大連理工大學(xué)碩士學(xué)位論文 5 ）（ uxfx ,39。 ? ， 在控制量的作用下增量式地產(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)域的路徑規(guī)劃問題中，并已成為當(dāng)前路徑規(guī)劃研究的熱點。 本文雙機路徑規(guī)劃為 高自由度 問題，并且是典型的非 完整 約束問題，因此采用基于 RRTConnect 算法的方法作為解決手段。 等人于 1998 年提出了一種基于采樣的路徑規(guī)劃方法 —— 快速 隨機 搜索 樹 算 法 （ Rapidlyexploring Random Tree， RRT） ，由于此方法 在高維空間中 具有 突出表現(xiàn)，以及在規(guī)劃 過程中可以引入運動學(xué)約束，因此目前 RRT 被廣泛應(yīng)用 于 許多路徑規(guī)劃問題中。 （ 2） 基本 RRT 算法 設(shè) C 為路徑規(guī)劃問題的狀態(tài)空間， Cfree（ Cfree? C） 為 與障礙物無碰撞的機器人自由空間， Cobst （ Cobst ? C） 為與障礙物發(fā)生 碰撞的機器人碰撞空間， T表示 含有 k 個節(jié)點的隨機樹，且 T? Cfree， Xinit（ Xinit ∈ T） 為 樹的 初始 點即 初始 姿態(tài)， Xgoal（ Xgoal ∈ T） 為樹的 目標(biāo) 點即 目標(biāo) 姿態(tài)。 基本 RRT 算法流程 ： ① BULD_RRT(Xinit) (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, Xrand, Xnear) If (NEW_STATE (Xrand, Xnear, Xnew, u) )then (Xnew)。 (Xnear, Xnew, u)。 Return。 基于 RRTConnect 算法的雙機路徑規(guī)劃研究 6 根據(jù)基本 RRT 算法流程及 圖 的可知，基本 RRT 的算法為首先以 初始點Xinit 作為樹 T 的根節(jié)點；在 Cfree 中用函數(shù) RANDOM_STATE( )隨機選擇一個隨機點 Xrand，即使得 Xrand? Cfree；再用 函數(shù) NEAREST_NEIGHBOR( )搜索樹上離Xrand 最近的節(jié)點用來擴展，這個節(jié)點被稱為 Xnear；用函數(shù) EXTEND( )來擴展樹，即隨機或是根據(jù)給定的標(biāo)準(zhǔn)，選擇一個輸入 u，使得 Xnear 向 Xrand 靠近，這時產(chǎn)生一個新節(jié)點 Xnew，如果檢測沒有碰撞或滿足要求，將 Xnew 加到樹中。如此重復(fù) 直到子節(jié)點集中包含 目標(biāo) 姿態(tài)點 Xgoal 或 子節(jié)點集中有節(jié)點在 目標(biāo) 區(qū)域內(nèi)時終止算法執(zhí)行，此時即找了一條以隨機樹 T 中節(jié)點組成 的 從 初始 姿態(tài) Xinit 到 目標(biāo)姿態(tài) Xgoal的 路徑。 X i n i t X n e a r X n e w X r a n d X g o a l u 圖 隨機樹擴展示意圖 Fig. Diagram of RRT expanding （ 3） 改進 RRT 算法 基本 RRT 主要缺陷在于其為了找到目標(biāo)點需要在整個空間內(nèi)進行搜索，效率很低。為提高搜索的效率，與路徑的質(zhì)量，很多學(xué)者對基本 RRT 進行了改進，形成了一些改進版本的 RRT 算法，這些改進的 RRT 算法通?？煞譃橐韵氯箢悺? ① 改進分支擴展方式的 RRT 改進分支擴展方式的 RRT 包括 RRTGoalBias[58, 59]、 RRTConnect[60, 61]等 。 RRTGoalBias： 此種改進 RRT 方法在擴展過程中不是完全以隨機點作為牽引點而是以一定概率用目標(biāo)點作為的牽引點。 RRTGoalBias 方法可使樹快速向目標(biāo)點增長，但是當(dāng)過多偏向目標(biāo)點時可能會使樹的生長陷入局部最優(yōu)。 RRTConnect： RRTConnect 的基本思想是使單步擴展的距離盡可能遠(yuǎn)，如下圖所 示該算法將基本 RRT 的單步擴展改進為具有貪婪性質(zhì)的多步擴展，直到碰到障礙或到達(dá)目標(biāo)點才結(jié)束一次擴展迭代。應(yīng)用此多步擴展的方式可以有效避免陷入局部最優(yōu)的可能，并且在相對開闊的區(qū)域 RRTConnect 可以快速向未探索的區(qū)域擴展從而可以大大提高生成樹的效率。 大連理工大學(xué)碩士學(xué)位論文 7 ② 增加隨機樹的 數(shù)量 雙棵樹 RRT： 雙棵樹 RRT 方法包括 RRTExtExt、 RRTExtCon、 RRTConCon等，這些方法都是分別以起點和目標(biāo)點作為樹根，分別以單步或多步擴展的方式生長兩棵樹，直到兩棵樹相遇，此時即找到了從起點到終點的路徑。此方法由于采用 兩棵樹同時生長，大大提高了搜索的效率，尤其是雙向都是多步生長的RRTConCon 方法具有很好的搜索特性，廣泛應(yīng)用于各路徑規(guī)劃問題中。 MultiRRT： MultiRRT 采用多棵樹同時生長的方式進行路徑規(guī)劃，此方法除了應(yīng)用 初始 點和 目標(biāo) 點分別為樹根構(gòu)造兩棵樹外，還采用橋測試的方法取到狹窄通道內(nèi)的點，并分別以這些點為樹根分別生成樹，當(dāng)兩棵樹相遇則將這兩棵樹合并成一棵樹，直到某一棵樹中即包含了 初始 點 又 包含 目標(biāo) 點此時意味著已經(jīng)找到了從 初始 點到 目標(biāo) 點的路徑。此方法因為增加了在狹窄通道內(nèi)生長的樹，使得該方法應(yīng)用于多狹窄通 道的問題時具有十分好的特性。 ③ 應(yīng)用 RRT 的搜索信息 VLRRT： 此方法是將樹中的每個節(jié)點都關(guān)聯(lián)一個關(guān)于生長步長的參數(shù) r，每次生長的步長都由生長點的 r 值決定，并且 r 的值會根據(jù)此生長點是否可以成 功生長而實時變化。如當(dāng) node1（ r = 2）為生長點時，以 node1 為生長點以 2 為步長生