礦區(qū)廢棄地移動機器人全覆蓋路徑規(guī)劃

周林娜，汪 蕓，張 鑫，楊春雨

中國礦業(yè)大學信息與控制工程學院，徐州 221000?通信作者，E-mail：chunyuyang@cumt.edu.cn

土地資源是人類生存和發(fā)展的載體，是進行農(nóng)業(yè)生產(chǎn)和工業(yè)建設的基礎物質條件，但我國人口眾多，人均用地嚴重不足，人地矛盾是我國面臨的主要矛盾之一. 改革開放以來，煤炭的過度開采占用大量土地，礦區(qū)周邊土壤質量惡劣. 大量數(shù)據(jù)表明：礦區(qū)廢棄地復墾是緩解農(nóng)業(yè)用地、改善礦區(qū)生態(tài)環(huán)境的重要途徑[1]. 礦區(qū)廢棄地環(huán)境復雜，土地復墾存在很大難度，土地復墾的前提是對礦區(qū)土壤的全覆蓋采樣. 移動機器人由于具備環(huán)境感知、行為決策及運動控制等能力，被廣泛用于智能清潔、農(nóng)田作業(yè)、軍事探測等領域的全覆蓋作業(yè)[2].為推進煤礦安全發(fā)展，國家煤礦安全監(jiān)察局于2019年提出了大力研發(fā)應用煤礦機器人的目標.本文面向礦區(qū)廢棄地復墾的國家需求，研究移動機器人全覆蓋路徑規(guī)劃問題.

礦區(qū)廢棄地土壤質量惡化，面臨嚴重的生態(tài)問題，其非結構化的環(huán)境基礎對移動機器人全覆蓋路徑規(guī)劃提出挑戰(zhàn). 全覆蓋路徑規(guī)劃是指機器人按照一定工作方式，在具有障礙物的環(huán)境中，無碰撞地遍歷除障礙物以外的全部區(qū)域[3]. 根據(jù)對環(huán)境信息的已知程度，全覆蓋路徑規(guī)劃可分為信息已知的全局路徑規(guī)劃和信息未知的局部路徑規(guī)劃[4]. 未知環(huán)境下的完全遍歷路徑規(guī)劃方法主要包括隨機遍歷法、漫步式探測法和沿邊規(guī)劃策略.隨機遍歷法是一種基于無環(huán)境模型的路徑規(guī)劃方法，該方法清掃過程簡單但會造成重復率高及清掃時間過長等問題. 漫步式探測方法主要包括動態(tài)窗口法，該方法能夠完成避障，實現(xiàn)環(huán)境的完全覆蓋，但時間成本高. 沿邊規(guī)劃策略首先采用沿邊學習建立環(huán)境模型，然后與局部路徑規(guī)劃相結合遍歷整個未知環(huán)境，生物激勵神經(jīng)網(wǎng)絡（Biologically inspired neural network, BINN）算法[5?7]是一種基于沿邊規(guī)劃策略的方法，可以很好地應用于動態(tài)未知環(huán)境.

礦區(qū)廢棄地的先驗環(huán)境信息通過遙感衛(wèi)星系統(tǒng)獲得，移動機器人的主要任務是對礦區(qū)實施全覆蓋從而獲得土壤采樣信息，基于以上特點，本文研究已知礦區(qū)環(huán)境全覆蓋路徑規(guī)劃問題. 已知環(huán)境下的完全遍歷路徑規(guī)劃算法主要包括模板模型法[8]和單元分解法[9]. 模板模型法通過將獲取的環(huán)境信息與各個模板匹配來完成遍歷，對環(huán)境缺乏整體規(guī)劃，難以適應變化的環(huán)境. 單元分解法將整個環(huán)境的復雜度簡化為子區(qū)域內(nèi)環(huán)境的復雜度，在大型已知環(huán)境下被廣泛應用，主要包括梯形單元分解法[10?11]、牛耕式單元分解(Boustrophedon cellular decomposition, BCD)法[12]和莫爾斯單元分解法[13]. BCD方法分解完成之后的子區(qū)域較少，本文采用BCD方法對環(huán)境做區(qū)域分解. 單元分解完成之后需要確定子區(qū)域內(nèi)部覆蓋方式，為應對未知障礙物的出現(xiàn)，本文采用BINN算法完成移動機器人對子區(qū)域內(nèi)部的覆蓋. 移動機器人在當前子區(qū)域內(nèi)部覆蓋完成之后需要轉移到下一子區(qū)域，點對點路徑規(guī)劃具有巨大作用. Wang等[14]將Dijkstra算法應用到機器人路徑規(guī)劃算法方面，該算法在迷宮環(huán)境中能夠獲得兩點間的最短路徑.Fu等[15]對A*算法進行改進并應用于工業(yè)機械臂，該改進A*算法能夠縮短路徑規(guī)劃距離. Wei和Ren[16]在機械臂上采用快速搜索隨機樹(Rapidlyexploring random trees, RRT)算法，可以完成靜態(tài)障礙物和動態(tài)障礙物的避障，但并不能獲得最短路徑. Rashid等[17]采用蟻群算法解決簡單環(huán)境地圖和復雜環(huán)境地圖中的移動機器人路徑規(guī)劃問題.張超等[18]提出了一種新的基于粒子群的改進蟻群算法，該算法采用全局異步與精英策略相結合方法更新信息素，減少了路徑規(guī)劃時間. 群智能優(yōu)化算法能夠解決移動機器人路徑規(guī)劃問題，但是此類算法產(chǎn)生的路徑平滑性較差. 近年來，BINN算法逐漸被應用到移動機器人路徑規(guī)劃方面，王耀南等[6]通過在邊界附近和障礙物之間增加假想非障礙物臨近點改進BINN算法，修改路徑?jīng)Q策方法，優(yōu)化了路徑質量. Zhu等[7]將BINN算法應用到水下機器人方面，解決了多機器人的任務分配和路徑規(guī)劃問題. 以上文獻中的BINN算法均可以被有效應用于移動機器人路徑規(guī)劃方面，但是沒有充分利用已知環(huán)境信息.

本文根據(jù)礦區(qū)廢棄地先驗環(huán)境信息，采用BCD結合BINN方法解決移動機器人對礦區(qū)廢棄地的全覆蓋路徑規(guī)劃問題，既包括子區(qū)域內(nèi)部全覆蓋路徑規(guī)劃又包括子區(qū)域間路徑轉移. 首先采用BCD方法劃分整個非結構化的環(huán)境，然后通過深度優(yōu)先搜索（Depth first search, DFS）算法確定子區(qū)域間遍歷順序，最后采用BINN算法完成子區(qū)域內(nèi)部覆蓋和子區(qū)域間路徑轉移，從而實現(xiàn)礦區(qū)全覆蓋.

1 礦區(qū)廢棄地基本環(huán)境及假設

礦區(qū)廢棄地是指礦山開采過程中失去經(jīng)濟利用價值的土地，也指在采礦期間任何沒有經(jīng)過人為修復的土地. 礦區(qū)廢棄地存在大量煤矸山、廢棄廠區(qū)以及踩空塌陷區(qū)和積水區(qū)等，這些特點造成了礦區(qū)廢棄地環(huán)境的復雜性. 圖1為國內(nèi)某礦區(qū)廢棄地現(xiàn)狀圖，礦區(qū)廢棄地的先驗環(huán)境信息由遙感衛(wèi)星系統(tǒng)獲得，但是環(huán)境中可能存在部分未被感知區(qū)域，導致礦區(qū)廢棄地環(huán)境復雜. 圖2為礦區(qū)廢棄地復雜障礙圖.

圖1 廢棄礦區(qū)現(xiàn)狀Fig.1 Status of abandoned mine land

圖2 廢棄礦區(qū)復雜環(huán)境. （a）積水區(qū)；（b）廢棄廠區(qū)；（c）尾礦、煤矸石的堆占；（d）周邊土壤現(xiàn)狀Fig.2 Complex environment of abandoned mine land: (a) pools zone;(b) abandoned factory; (c) heap of tailings and gangue; (d) status of surrounding soil

為了實現(xiàn)非結構化礦區(qū)廢棄地環(huán)境移動機器人全覆蓋路徑規(guī)劃的遍歷且減少重復覆蓋，根據(jù)以上實際情況，對環(huán)境做如下假定：

（1）假定該礦區(qū)廢棄地環(huán)境全局信息已知；

（2）假定環(huán)境中的障礙物存在復雜性，即同時存在規(guī)則障礙物和非規(guī)則障礙物；

（3）在做仿真實驗時，假定煤矸山為三角形障礙物，廢棄廠區(qū)為多邊形障礙物，礦區(qū)積水區(qū)及其他復雜障礙物以非規(guī)則障礙物表示.

2 礦區(qū)廢棄地全覆蓋路徑規(guī)劃

礦區(qū)廢棄地為室外大型非結構化環(huán)境，移動機器人對該環(huán)境的路徑規(guī)劃存在較大難度. 目前礦區(qū)環(huán)境下的移動機器人研究任務多為點對點路徑規(guī)劃[19?20]，本文將采用區(qū)域分解法[21?22]實現(xiàn)全覆蓋路徑規(guī)劃，主要包括三個部分：目標區(qū)域分解、子區(qū)域規(guī)劃和各子區(qū)域遍歷. 具體流程如圖3所示.

圖3 全覆蓋路徑規(guī)劃流程圖Fig.3 Flow chart of complete coverage path planning

2.1 目標區(qū)域分解

單元分解法[9]是一種運動規(guī)劃技術，該方法將所有自由支配空間分解為多個單元，使得所有單元聯(lián)合起來是原始自由空間. 傳統(tǒng)單元分解法是梯形單元分解法[10]，BCD方法[12]在梯形單元分解法上進行改進，該方法假設一條垂直線（被稱作切片）從左到右掃過一個充滿多邊形障礙的有界環(huán)境，每遇到頂點可上下延伸的臨界點便進行分割，最終環(huán)境被分割為多個不含障礙物的子區(qū)域. 相比梯形單元分解法，BCD方法產(chǎn)生更少的子區(qū)域，可以減少機器人的路徑冗余，進一步降低能源消耗和時間損耗. 因此，BCD方法適合礦區(qū)廢棄地環(huán)境. 表1給出了BCD方法的步驟.

表 1 BCD 方法步驟Table 1 BCD method steps

圖4（a）為礦區(qū)廢棄地仿真環(huán)境，該環(huán)境具有復雜性，包括規(guī)則幾何障礙物和非規(guī)則障礙物，采用BCD方法對該環(huán)境做區(qū)域分解，分解結果如圖 4（b）所示. 其中，C1～C10 為分解后的 10 個子區(qū)域.

圖4 礦區(qū)廢棄地仿真圖. （a）仿真環(huán)境；（b）區(qū)域分解圖Fig.4 Simulation map of abandoned mine land: (a) simulation environment; (b) regional decomposition map

本文所使用的BCD方法能夠有效分解具有綜合復雜性的環(huán)境. 實驗證明，該方法可以被廣泛應用于礦區(qū)廢棄地等復雜室外環(huán)境，它能夠有效減少機器人在室外做全覆蓋路徑規(guī)劃的難度.

2.2 子區(qū)域規(guī)劃

區(qū)域分解完成之后，機器人可通過兩個步驟完成對整個區(qū)域的覆蓋：（1）在鄰接圖中找到一個詳盡的行走順序，該覆蓋順序可以指導機器人到達工作空間中所有可到達的子區(qū)域；（2）完成子區(qū)域內(nèi)部覆蓋以及區(qū)域間的轉移. 本模塊主要完成子區(qū)域遍歷順序規(guī)劃，采用的算法為DFS算法.

DFS算法[23]是圖論中最著名的一種搜索算法，該算法經(jīng)常被用來遍歷圖中所有點，找到一條可供行駛的詳盡覆蓋路徑. 表2為該算法步驟.

表 2 DFS 算法步驟Table 2 DFS algorithm steps

圖5 子區(qū)域連接圖. （a）鄰接圖；（b）轉移序列圖Fig.5 Connection diagram of subregions: (a) adjacency map; (b)transfer order map

將BCD 方法中切片的運行方向定義為從左往右，圖5（a）為區(qū)域分解完成之后的子區(qū)域構成的鄰接圖，根據(jù)切片運行方向，將A設置為起始點，圖5（b）即為使用DFS算法規(guī)劃的子區(qū)域順序結果圖. 圖5（b）中，A為機器人遍歷的第一個子區(qū)域，當A遍歷結束時機器人從該區(qū)域結點到轉移下一個子區(qū)域B的起始點，對B區(qū)域內(nèi)部進行全覆蓋遍歷，以此類推，直至到達最后一個子區(qū)域C的結點.

2.3 各子區(qū)域遍歷

2.3.1 BINN 算法

BINN算法是一種在線規(guī)劃算法，該算法將每個柵格看作一個神經(jīng)元，整個柵格地圖變?yōu)橛缮窠?jīng)網(wǎng)絡組成的拓撲狀態(tài)空間，其中神經(jīng)元的活性值由下式表示：

式（1）為分流方程[24]，通過該方程可以計算出柵格地圖中每個神經(jīng)元的活性值. 式中：為 第i個神經(jīng)元的活性值；t是時間量；、和為非負常數(shù)，其中代 表衰減率，代表神經(jīng)元活性狀態(tài)的上限，代表神經(jīng)元活性狀態(tài)的下限；為與第i個神經(jīng)元直接連接神經(jīng)元的個數(shù)；為外部輸入，可定義為：

其中：E是一個遠遠大于B的正常數(shù)；和分別表示興奮輸入和抑制輸入是第i個神經(jīng)元與第個神經(jīng)元所在位置處在狀態(tài)空間中的歐幾里得距離，為任意的單調減函數(shù)，可定義為

BINN算法既可以完成點對點路徑規(guī)劃又可以完成全覆蓋路徑規(guī)劃. 機器人生成點對點的路徑為：

該路徑生成過程為：機器人在當前位置選擇鄰接神經(jīng)元中具有最大活性值的神經(jīng)元柵格作為下一位置，到達下一位置后，下一位置成為新的當前位置，以此類推，直到到達目標點柵格. 如果周邊8個鄰接神經(jīng)元的活性值都不大于當前柵格的神經(jīng)元活性，則機器人待在原地保持不動，機器人陷入死區(qū).

機器人生成全覆蓋的路徑為：

圖6 BINN 算法流程圖Fig.6 Flow chart of BINN algorithm

2.3.2 子區(qū)域內(nèi)部遍歷

在區(qū)域分解和子區(qū)域遍歷順序確定后，關鍵步驟是完成對子區(qū)域內(nèi)部的遍歷. BINN算法是一種在線規(guī)劃算法，不需要學習過程，適合處理未知情況. 由于礦區(qū)廢棄地結構復雜，環(huán)境中可能存在未知障礙物或移動障礙物等一系列現(xiàn)象，為了在后期的工作中能夠較好地應對突發(fā)狀況，本文采用BINN算法完成對每個子區(qū)域內(nèi)部全覆蓋.

2.3.3 區(qū)域路徑轉移

當前子區(qū)域內(nèi)部覆蓋完成之后到下一子區(qū)域內(nèi)部覆蓋之前需要子區(qū)域間的路徑轉移，從而使移動機器人按照子區(qū)域規(guī)劃序列完成對所有子區(qū)域的覆蓋. 針對該問題，本節(jié)主要使用BINN算法規(guī)劃從上一個子區(qū)域遍歷終點到下一個子區(qū)域遍歷起點的最短路徑搜索，并計算該算法在最短路徑和時間消耗方面的總代價. 因此，定義一系列由點組成的轉移路徑：

其中，a代表神經(jīng)元的橫坐標，b代表神經(jīng)元的縱坐標.

本文所提出方法同樣適應于室內(nèi)具有綜合復雜性的環(huán)境.

3 仿真實驗

本文的內(nèi)容應用于移動機器人礦區(qū)廢棄地環(huán)境路徑規(guī)劃. 本節(jié)分別對子區(qū)域內(nèi)部遍歷和子區(qū)域間路徑轉移進行仿真實驗，其中路徑轉移實驗中BINN算法和其他路徑規(guī)劃算法同時進行. 實驗方案規(guī)劃：首先，對工作環(huán)境進行柵格地圖建模，建立分區(qū)之后的環(huán)境模型；其次，采用DFS算法規(guī)劃子區(qū)域遍歷序列；最后，采用BINN算法完成對每個子區(qū)域內(nèi)部的覆蓋以及子區(qū)域間路徑轉移，并與其他路徑規(guī)劃算法做對比仿真實驗. 仿真實驗如下所示.

3.1 參數(shù)設置與仿真環(huán)境

為了驗證BINN算法做全覆蓋路徑規(guī)劃時的效果，設計相關仿真實驗，合理參數(shù)設置和仿真實驗環(huán)境設定是確保實驗成功的重要環(huán)節(jié)，本文參數(shù)設置環(huán)節(jié)依據(jù)文獻[25]，并根據(jù)實驗環(huán)境做了相應調整. 本文設定柵格地圖，在該柵格地圖中自由柵格值為1，障礙柵格值為，和代表的是神經(jīng)活性上界與下界，和取1和；代表外部輸入，遠遠大于和，將的取值設為；代表神經(jīng)元活性衰減速率，本文??；代表方向權重的選擇，在全覆蓋路徑規(guī)劃中，的選擇會影響機器人路徑?jīng)Q策，為平滑機器人的路徑，將的值取為1；代 表當前神經(jīng)元與周邊神經(jīng)元活性之間側向連接，對當前神經(jīng)元的活性值有較大影響，在做全覆蓋路徑規(guī)劃時為獲得規(guī)則路徑，值 取1，在做點對點路徑規(guī)劃時考慮到目標神經(jīng)元的導向作用，根據(jù)不同環(huán)境重新設定.

本文中的仿真實驗均在Matlab R2017b中進行，7.9 GB 計算機內(nèi)存，3.41 GHz CPU 速度.

圖7 子區(qū)域遍歷結果. （a）全覆蓋結果；（b）路徑轉移結果Fig.7 Coverage results of subregions: (a) complete coverage result; (b) path transition result

3.2 子區(qū)域遍歷實驗

在圖7（a）中，環(huán)境中的障礙物形狀各異，機器人從初始位置（2,2）開始運動，根據(jù)仿真結果可知，該算法能夠在這種復雜環(huán)境下做出相應的路徑選擇策略，并且在每一個子區(qū)域內(nèi)部完成全覆蓋. 本例子中區(qū)域重復覆蓋率為0，總覆蓋面積達到100%，有效證明了該算法的可行性. 從圖 7（a）中可以看到虛線經(jīng)過了障礙物柵格，路徑轉移算法需要完成避障功能. 三個部分路徑轉移的實施離不開點對點路徑規(guī)劃算法，本模塊BINN算法在做點對點路徑規(guī)劃時，在目標點處增加了神經(jīng)元活性值，并在三個區(qū)域轉移部分分別設置不同的來減少路徑的轉折，優(yōu)化算法的搜索路徑. 實驗結果證明算法實現(xiàn)了自主避障并有效搜索到了目標點，路徑?jīng)]有出現(xiàn)跨越和迷失現(xiàn)象，該算法在點對點路徑規(guī)劃中具有高效性.

3.3 對比實驗

為證明BINN算法在區(qū)域轉移方面的性能，本文選用幾種經(jīng)典點對點路徑規(guī)劃算法與BINN算法做對比試驗. 通常情況下，路徑轉移距離和路徑轉移時間是衡量覆蓋任務的重要指標. 路徑轉移距離為機器人從上一個子區(qū)域結點到下一個子區(qū)域起始點生成的路徑距離；路徑轉移時間為完成這項任務消耗的時間，通過這兩種性能指標來評價兩種算法最短轉移路徑的總代價.

圖8 實驗結果對比. （a）BINN 算法；（b）A*算法；（c）Dijkstra 算法；（d）RRT 算法Fig.8 Comparison of experimental results: (a) BINN algorithm; (b) A* algorithm; (c) Dijkstra algorithm; (d) RRT algorithm

本小節(jié)選用的對比算法為A*算法、Dijkstra算法和 RRT算法. BINN算法、A*算法、Dijkstra算法均是基于柵格地圖，路徑轉移距離為所有柵格之間的歐氏距離之和；RRT算法基于坐標地圖，路徑轉移距離為所有坐標點之間的距離之和，柵格地圖與坐標地圖具有對應性，因此幾種算法路徑長度具有可比性. 圖8、表3、表4和圖9展示了四種算法對比實驗結果. 圖8中BINN算法路徑用“×”表示，A*算法路徑用“○”表示，Dijkstra算法路徑用“△”表示，RRT算法路徑用“·”表示.

表 3 路徑轉移距離對比Table 3 Distance comparison of path transition

表 4 路徑轉移時間對比Table 4 Time comparison of path transition

從圖 9（a）和表 3 可以得出，在 J—I，I—F 區(qū)域中，BINN算法生成的路徑長度和A*算法、Dijkstra算法相同，小于RRT算法的路徑長度；F—C區(qū)域中BINN算法的路徑長度最小，因此，總路徑長度BINN算法最小. 本文在區(qū)域轉移部分應用BINN算法時增大了目標點神經(jīng)元活性，引導算法快速搜索目標神經(jīng)元，同時根據(jù)對的不同設定，縮短了規(guī)劃路徑，該算法獲得最短搜索路徑. 根據(jù)圖9（b）和表4，在三個區(qū)域轉移部分，由于BINN算法對目標神經(jīng)元的導向作用，算法快速搜索到目標神經(jīng)元位置，BINN算法消耗的時間最少. 從上述實驗結果中可以看到，在路徑轉移距離方面，BINN算法在J—I區(qū)域，I—F區(qū)域，F(xiàn)—C區(qū)域均獲得最小的總路徑；在路徑轉移時間方面，BINN算法的路徑轉移時間代價最小. 因此，不論路徑轉移距離還是路徑轉移時間，BINN算法均最優(yōu).

圖9 算法性能評價結果圖. （a）距離對比結果；（b）時間對比結果Fig.9 Performance evaluation results of algorithms: (a) distance comparison result; (b) time comparison result

4 結論

針對礦區(qū)廢棄地等復雜環(huán)境，本文使用BCD方法結合BINN算法完成移動機器人對整個環(huán)境的全覆蓋. 本文將BINN算法用于區(qū)域分解中，既能夠實現(xiàn)機器人對子區(qū)域內(nèi)部全覆蓋又能完成子區(qū)域間路徑轉移. 仿真實驗結果驗證了本文所使用的方法的可行性. 在路徑轉移方面，本文使用三種點對點路徑規(guī)劃算法做對比實驗，實驗結果證明，不論是在路徑轉移距離方面還是在路徑轉移時間方面，BINN算法均具有高效性. 未來的工作任務是采用一種主動搜索算法完成下一子區(qū)域最佳起始點的搜索，要求該搜索算法獲得的最佳起始點與上一結點之間具有較短路徑消耗.