摘 要：針對(duì)復(fù)雜作業(yè)環(huán)境下的工程機(jī)械路徑規(guī)劃問題，提出了一種基于快速擴(kuò)展隨機(jī)樹的路徑規(guī)劃方法。首先分別對(duì)路徑規(guī)劃的目的、約束條件、任務(wù)環(huán)境建模、路徑表述方法以及針對(duì)機(jī)械本體大小的障礙物膨化方法進(jìn)行了分析論述，進(jìn)而介紹了RRT算法的基本原理，并給出了基于RRT的路徑規(guī)劃算法步驟，最后通過仿真試驗(yàn)驗(yàn)證了所提方法的有效性和先進(jìn)性。

關(guān)鍵詞：工程機(jī)械；路徑規(guī)劃；快速擴(kuò)展隨機(jī)樹

DOI：10.16640/j.cnki.37-1222/t.2017.21.248

0 前言

以推土機(jī)、挖掘機(jī)為代表的工程機(jī)械，通常在地面崎嶇、障礙物眾多的復(fù)雜環(huán)境進(jìn)行土石方作業(yè)。傳統(tǒng)的人工駕駛方式是通過車載駕駛?cè)藛T進(jìn)行機(jī)械設(shè)備的現(xiàn)場(chǎng)操作，但是一些特殊領(lǐng)域，工作環(huán)境可能存在地面塌陷、山體垮塌等危險(xiǎn)情況，會(huì)給駕駛?cè)藛T的生命安全帶來威脅。智能化、精準(zhǔn)化、無人化代表了工程機(jī)械行業(yè)未來的發(fā)展方向[1]。通過無人化設(shè)計(jì)，實(shí)現(xiàn)操作人員對(duì)設(shè)備的遠(yuǎn)程遙控或者機(jī)械設(shè)備的任務(wù)級(jí)自主控制，能夠極大的提高工程施工的安全性、拓寬工程機(jī)械的應(yīng)用場(chǎng)合。

路徑規(guī)劃是綜合考慮移動(dòng)主體的運(yùn)動(dòng)學(xué)、動(dòng)力學(xué)約束，以及任務(wù)環(huán)境的地形地貌、障礙分布等情況，為移動(dòng)主體規(guī)劃出從起始位置到目標(biāo)位置的可行路徑或最優(yōu)路徑。路徑規(guī)劃是實(shí)現(xiàn)工程機(jī)械無人化作業(yè)的關(guān)鍵技術(shù)之一。常見的路徑規(guī)劃方法包括基于數(shù)學(xué)規(guī)劃的方法，基于群體智能的規(guī)劃方法、基于啟發(fā)式計(jì)算的方法等[1，2]。其中混合整數(shù)線性規(guī)劃為典型的數(shù)學(xué)規(guī)劃方法，具有嚴(yán)格的數(shù)學(xué)理論依據(jù)，但隨著規(guī)劃問題的增大，其計(jì)算量會(huì)急劇增加，因此只適合于小規(guī)模的路徑規(guī)劃問題。以蟻群算法、遺傳算法、粒子群算法為代表的群體智能優(yōu)化方法具有內(nèi)在的并行機(jī)制，全局優(yōu)化能力強(qiáng)，但存在優(yōu)化時(shí)間長(zhǎng)，有時(shí)可能會(huì)規(guī)劃失敗等不足。人工勢(shì)場(chǎng)方法也是一種常見的路徑規(guī)劃方法，能夠在勢(shì)場(chǎng)引力和勢(shì)場(chǎng)斥力的綜合作用下，將路徑向著目標(biāo)位置延伸，但也存在著存在引力和斥力相同的局部極小點(diǎn)問題，會(huì)導(dǎo)致規(guī)劃失敗。

快速擴(kuò)展隨機(jī)樹算法 （Rapidly-exploring Random Tree，RRT）是一種基于空間采樣的路徑規(guī)劃方法，由美國學(xué)者LaValle于上個(gè)世紀(jì)末提出[3]。RRT在任務(wù)空間內(nèi)采用節(jié)點(diǎn)生長(zhǎng)的方式構(gòu)造隨機(jī)樹，逐步構(gòu)建出連通起始位置與目標(biāo)位置的可行路徑。該算法具有參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)，自算法提出后，逐漸得到的學(xué)術(shù)界的認(rèn)可，已有的研究表明，RRT算法具有比A*算法、隨機(jī)路線圖算法等原有的路徑規(guī)劃算法更高的優(yōu)化效率[4]。

本文采用RRT算法求解復(fù)雜工作環(huán)境下的工程機(jī)械路徑規(guī)劃問題，包括路徑規(guī)劃問題描述與數(shù)學(xué)建模、算法設(shè)計(jì)、仿真試驗(yàn)等內(nèi)容。

1 問題描述

自動(dòng)地規(guī)劃出工程機(jī)械的行駛路徑，是未來的智能化和無人化工程機(jī)械實(shí)現(xiàn)自主行進(jìn)與施工作業(yè)的重要前提。該路徑規(guī)劃問題可以描述為：

（1）根據(jù)工作環(huán)境和任務(wù)要求，為工程機(jī)械生成從起始位置到目標(biāo)位置的可行路徑。

（2）所得路徑應(yīng)能夠避開已知的障礙物體或危險(xiǎn)區(qū)域，保證設(shè)備的行進(jìn)安全。

（3）所得路徑應(yīng)滿足機(jī)械設(shè)備的運(yùn)動(dòng)學(xué)和動(dòng)力學(xué)約束，比如路徑長(zhǎng)度應(yīng)小于工程機(jī)械的最大行程，轉(zhuǎn)彎半徑應(yīng)符合工程機(jī)械的機(jī)動(dòng)性能。

機(jī)械的行進(jìn)路徑由任務(wù)區(qū)域中一系列的路徑節(jié)點(diǎn)組成，路徑節(jié)點(diǎn)的順序?qū)?yīng)著工程機(jī)械的依次需要到達(dá)的行進(jìn)位置。用直線段連接相鄰的路徑節(jié)點(diǎn)。假設(shè)工程機(jī)械的起始位置為，目標(biāo)位置為，第個(gè)路徑節(jié)點(diǎn)表示為，其中分別為該路徑節(jié)點(diǎn)位置的縱橫向坐標(biāo)，則從起始位置歷經(jīng)個(gè)路徑節(jié)點(diǎn)到達(dá)目標(biāo)位置的路徑可以表示為：

基于上述分析，可以采用二值化的任務(wù)環(huán)境建模方法。將障礙物、危險(xiǎn)區(qū)域、機(jī)動(dòng)性能受限區(qū)域等簡(jiǎn)化為具有同等威脅程度的不可行區(qū)域，即整個(gè)工作環(huán)境區(qū)分為威脅區(qū)域（不可行區(qū)域）和可行區(qū)域兩種情況。威脅區(qū)域完全不可行，規(guī)劃所得路徑不能與威脅區(qū)域有重合。

另外由于工程機(jī)械具有自身的形狀和較大的外形尺寸，在實(shí)際的行駛時(shí)，需要避免車體與周圍物體的碰撞，不能簡(jiǎn)單的將車體看作為沒有尺寸大小的質(zhì)點(diǎn)。在路徑規(guī)劃過程中，可以采用障礙物膨脹的方法，將車體的外形尺寸進(jìn)行等效處理，即根據(jù)工程機(jī)械的車體大小，將障礙物或危險(xiǎn)區(qū)域進(jìn)行等值的膨脹放大處理。經(jīng)膨脹處理之后，不但解決了車體的碰撞問題，而且對(duì)于常見的推土機(jī)、挖掘機(jī)等低速運(yùn)動(dòng)的工程機(jī)械而言，其轉(zhuǎn)彎半徑、爬坡率等運(yùn)動(dòng)學(xué)約束也不用在規(guī)劃過程中單獨(dú)處理。

2 算法設(shè)計(jì)

RRT算法是一種以空間采樣的方式實(shí)現(xiàn)路徑搜索的規(guī)劃算法。假設(shè)任務(wù)區(qū)域?yàn)椋硎酒渲械目尚袇^(qū)域，表示威脅區(qū)域，和同為的子集，并且滿足和。路徑規(guī)劃的起始位置和目標(biāo)位置，起始位置和目標(biāo)位置位于同一連通區(qū)之內(nèi)，路徑規(guī)劃的目的是得到從到的可行路徑。

RRT算法首先通過節(jié)點(diǎn)擴(kuò)展的方式在構(gòu)建隨機(jī)樹，在構(gòu)建過程中，以為根節(jié)點(diǎn)，依照概率選擇目標(biāo)位置或者空間中的隨意一個(gè)位置作為隨機(jī)目標(biāo)點(diǎn)，并從原有的隨機(jī)樹上延伸一個(gè)步長(zhǎng)，拓展出一個(gè)新節(jié)點(diǎn)，當(dāng)隨機(jī)樹延伸到與足夠近的時(shí)候，通過反向搜索，可獲得從到的路徑。RRT算法的步驟如下：

（1）算法初始化；

（2）未到達(dá)目標(biāo)位置則轉(zhuǎn)向步驟（3）；否則轉(zhuǎn)向步驟（7）；

（3）生成隨機(jī)數(shù)，若，則轉(zhuǎn)向步驟（4），否則轉(zhuǎn)向步驟（5）；

（4）以作為，確定臨近節(jié)點(diǎn)，進(jìn)而得到，轉(zhuǎn)向步驟（6）；

（5）在任務(wù)區(qū)域內(nèi)隨機(jī)生成，計(jì)算對(duì)應(yīng)的；

（6）判斷與之間是否存在威脅，若無威脅則將添加到隨機(jī)樹之中，實(shí)現(xiàn)隨機(jī)樹的擴(kuò)展，并轉(zhuǎn)向步驟2），若存在威脅則轉(zhuǎn)向步驟3）；

（7）從開始反向搜索父節(jié)點(diǎn)，直至找到起始節(jié)點(diǎn)，完成路徑規(guī)劃。

3 仿真試驗(yàn)

采用RRT算法進(jìn)行復(fù)雜任務(wù)環(huán)境中的路徑規(guī)劃仿真試驗(yàn)，仿真軟件平臺(tái)為MATLAB2009。假設(shè)任務(wù)環(huán)境為的無量綱二維區(qū)域，任務(wù)環(huán)境內(nèi)共有100個(gè)不可行的威脅區(qū)域。每個(gè)威脅區(qū)域的位置和覆蓋半徑都隨機(jī)產(chǎn)生。路徑規(guī)劃的起始位置坐標(biāo)為（0，0），目標(biāo)位置坐標(biāo)為（100，100），設(shè)置RRT算法的參數(shù)為和。endprint

圖1為通過RRT算法得到路徑結(jié)果。由圖可知，所得路徑避開了所有的已知威脅區(qū)域，生成了從起始位置到目標(biāo)位置的可行。在隨機(jī)樹在生長(zhǎng)過程中產(chǎn)生了很多分支，這是由于對(duì)于復(fù)雜的任務(wù)環(huán)境，RRT算法必須通過不斷的在整個(gè)任務(wù)區(qū)域內(nèi)容進(jìn)行拓展搜索，以圖找到潛在的路徑。算法具有良好的時(shí)效性，仿真運(yùn)行時(shí)間0.38秒，能夠滿足實(shí)際的工程機(jī)械路徑規(guī)劃的快速性要求。RRT算法在規(guī)劃過程中總共擴(kuò)展出258個(gè)節(jié)點(diǎn)，其中所得路徑的長(zhǎng)度175.3，這說明算法具有較好的方向性，沒有產(chǎn)生過多的迂回曲折。

4 結(jié)束語

以推土機(jī)、挖掘機(jī)、鏟車為代表的工程機(jī)械在工程施工領(lǐng)域有著不可替代的重要作用，隨著科技的發(fā)展，智能化、無人化代表了工程機(jī)械的發(fā)展方向。針對(duì)復(fù)雜作業(yè)環(huán)境下的工程機(jī)械路徑規(guī)劃問題，本文提出了一種基于快速擴(kuò)展隨機(jī)樹的路徑規(guī)劃方法。首先對(duì)工程機(jī)械路徑規(guī)劃問題的目的、約束條件、任務(wù)環(huán)境建模、路徑表述以及障礙物膨化處理方法進(jìn)行了分析論述，進(jìn)而給出了基于RRT算法的路徑規(guī)劃方法，通過仿真試驗(yàn)對(duì)所提方法的有效性和先進(jìn)性進(jìn)行了驗(yàn)證。結(jié)果表明RRT算法是一種高效的路徑規(guī)劃方法，在工程機(jī)械路徑規(guī)劃領(lǐng)域有廣泛的應(yīng)用前景。

參考文獻(xiàn)：

[1]朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010，25（07）：961-967.

[2]孫梅.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].山東工業(yè)技術(shù)，2016（21）：164.

[3]LaValle S M，Kuffner J J.Donald B R，et al.Rapidly-exploring random trees：Progress and prospects[J].Algorithmic and Computational Robotics：New Directions，Wellesley，2001： 293-308.

[4]David B.Comparison of A*and RRT-connect motion planning techniques for self-reconfiguration planning[C]. International Conference on Intelligent Robots and Systems， Beijing，2006：892-897.

本論文來源于山東省重大科技創(chuàng)新工程項(xiàng)目，項(xiàng)目名稱《基于工業(yè)物聯(lián)網(wǎng)的工程機(jī)械智能裝配數(shù)據(jù)采集與處理關(guān)鍵技術(shù)研究與應(yīng)用》，項(xiàng)目編號(hào)：2017CXGC0603

作者簡(jiǎn)介：田從豐（1985-），男，山東微山人，工學(xué)碩士，工程師，研究方向：工程機(jī)械自動(dòng)控制。endprint