一種改進的全覆蓋路徑規(guī)劃算法

李淑霞,楊俊成,2

(1.河南工業(yè)職業(yè)技術(shù)學院電子信息工程學院，河南 南陽 473000; 2.武漢大學計算機學院，湖北 武漢 430072)

0 引 言

路徑規(guī)劃算法[1]實現(xiàn)從起始點到目標點的無碰撞路徑，但該算法并不能覆蓋環(huán)境的全部區(qū)域。而現(xiàn)實生活中全區(qū)域路徑規(guī)劃[2-3](即全覆蓋路徑規(guī)劃)的應用還是比較多的，比如排雷機器人[4]、日常家家戶戶用得比較多的室內(nèi)清掃機器人[5-6]、智能時代用得比較多的播撒機器人、搜救機器人[7]……，這些機器人要想完成任務就避不開路徑問題，并且該路徑需要覆蓋所給區(qū)域的所有坐標，即為全覆蓋路徑規(guī)劃[8]問題。所以全覆蓋路徑規(guī)劃具有一定的研究意義，其路徑規(guī)劃算法是核心技術(shù)，受到專家學者的關(guān)注。

全覆蓋路徑規(guī)劃[8]是指在短時間內(nèi)以低重復率走遍除障礙物外的所有自由空間。根據(jù)環(huán)境狀態(tài)的不同，全覆蓋路徑規(guī)劃可分為已知環(huán)境下的路徑規(guī)劃和未知環(huán)境下的路徑規(guī)劃[9]。在已知環(huán)境中，機器人根據(jù)當前的環(huán)境信息規(guī)劃出一條重復路徑最少的路徑走遍環(huán)境中的所有自由點，其規(guī)劃方法比較成熟[7]；在未知環(huán)境中，機器人需利用自身的傳感器認知環(huán)境信息，再規(guī)劃出全覆蓋路徑規(guī)劃[10]。根據(jù)移動策略的不同，全覆蓋路徑規(guī)劃可以分為隨機移動策略和非隨機移動策略。隨機移動策略是清掃機器人無法直行時隨機旋轉(zhuǎn)一個角度，該方法簡單，工作效率不高；非隨機移動策略采用某種性能評價函數(shù)來控制機器人運動路徑，性能評價函數(shù)是清潔效率的關(guān)鍵。

針對全覆蓋路徑規(guī)劃，不同的學者提出了不同的方法，如隨機方法[11-12]、最大面積優(yōu)先算法[13]、內(nèi)螺旋覆蓋(Internal Spiral Coverage, ISC)算法[14-15]、基于模板的完全覆蓋方法[16]、Boustrophedon(牛耕式)[17]覆蓋方法等。隨機方法[18]即機器無法直行時隨機旋轉(zhuǎn)一個角度繼續(xù)前進，該算法簡單，但不能保證覆蓋全面。最大面積優(yōu)先算法首先將整個待覆蓋區(qū)域劃分成若干個柵格，機器人從當前位置進行清掃，如果前方有未覆蓋柵格，則繼續(xù)向前搜索，否則計算當前位置的左、右2個方向的未覆蓋柵格數(shù)目，并轉(zhuǎn)向未覆蓋柵格多的方向進行搜索。De Carvalho等人[16]提出的基于模板的完全覆蓋方法是利用已知的環(huán)境地圖信息和一系列模板規(guī)劃出覆蓋路徑，針對不同的地形采用不同的模板(如向前TM模板、U型轉(zhuǎn)彎UT模板、側(cè)移SS模板、U型交錯UTI模板、返回BT模板)實現(xiàn)區(qū)域全覆蓋，該方法只適應于已知的環(huán)境信息。Choset[17]提出了Boustrophedon覆蓋方法，文獻[19]對此方法進行了改進，采用二次往復前進(與第一次行進方向相垂直)和三次往復前進(與第一次行進方向相同)來提高覆蓋率，從而也提高了重復覆蓋率。上述方法在覆蓋效率方面都有待提高[7]。

在ISC算法[20]中，由于障礙物的存在引起部分未覆蓋區(qū)域。為解決這一問題，本文在ISC算法的基礎(chǔ)上，結(jié)合行走優(yōu)先級策略，采用柵格建模法初始化室內(nèi)環(huán)境信息，并用柵格地圖表示房間及障礙物的信息分布情況，采用回溯方法解決機器人清掃過程中遇到的死角問題及未覆蓋區(qū)域問題。

1 基本概念

全覆蓋路徑規(guī)劃是路徑規(guī)劃的一種，其根據(jù)環(huán)境信息和任務目標規(guī)劃出一條從起點到目標的無碰路徑，吸引了大量研究人員的關(guān)注。具體定義如下：

定義2環(huán)境中的柵格定義為[22-23]g(a,b)，其中a為g所在的行號(a=1,2,…,n)，b為g所在的列號(b=1,2,…,n)，環(huán)境的采樣信息為一串連續(xù)的柵格集合G(g1,g2,…,gi),i=1,2,…,n是柵格采樣序號[18-19]。

根據(jù)定義，假設(shè)柵格寬度為ε，其取值與清掃機器人的尺寸大小有關(guān)，且機器人尺寸大小遠小于已知環(huán)境區(qū)域φ尺寸大小，柵格模型的建立依據(jù)如公式(1)所示，將環(huán)境坐標(x,y)映射為柵格坐標g(a,b)∈φ∈ω。

(1)

采用柵格(grid)法將機器人工作環(huán)境量化成若干個柵格，柵格粒度的大小直接影響著柵格法的效率；柵格粒度越小則清掃的部分表示得越精確，需占用的存儲空間越大；柵格粒度越大，環(huán)境信息存儲量就越小，規(guī)劃時間越短，但清掃整個柵格同樣可以達到清掃干凈的目的。系統(tǒng)利用柵格法將室內(nèi)環(huán)境建模為10×10的二維柵格如圖1所示。

圖1 10×10的二維柵格圖

圖1中標記為0的灰色柵格表示障礙物，標記為2的柵格為需清掃區(qū)域，又稱自由柵格。清掃機器人要以較低的重復率和較少的時間走遍所有標記為2的柵格，以達到清掃室內(nèi)衛(wèi)生的目的。

本文根據(jù)內(nèi)螺旋覆蓋算法的思想(如圖2所示)，將ISC算法結(jié)合行走優(yōu)先級進行改進，以此減少未覆蓋區(qū)域的產(chǎn)生，該算法記為帶優(yōu)先級的ISC算法(Priority Internal Spiral Coverage, PISC)。

圖2 ISC算法示意圖

在圖2中，符號“●”表示清掃機器人的起始位置，符號“○”表示清掃機器人的結(jié)束位置，符號“→”表示清掃機器人的運動路線，區(qū)域D表示障礙物區(qū)域，區(qū)域A表示由于障礙物D的存在而導致的未覆蓋區(qū)域。

回溯算法又稱試探法，其基本思想是從一條路徑往前走，能進則進，不能進則原路退回來，換一條路再試。回溯法的優(yōu)點在于其程序結(jié)構(gòu)明確，可讀性強，易于理解，且可以提高運行效率。本文利用回溯法來解決機器人清掃死角問題。當機器人前方是邊界，左邊或右邊柵格有障礙物存在或已被遍歷，柵格地圖中還存在其他未被遍歷的柵格，此時稱機器人進入死角狀態(tài)。在死角狀態(tài)下，機器人后退一個柵格判斷左(右)兩邊柵格是否存在未遍歷柵格，如果存在則按規(guī)定的優(yōu)先級轉(zhuǎn)彎90°繼續(xù)按照行走優(yōu)先級進行遍歷，否則繼續(xù)后退一個柵格，直到兩邊出現(xiàn)未覆蓋柵格。如果不存在這樣的柵格說明該環(huán)境柵格中的清掃區(qū)域已被清掃完。如圖3所示，機器人起始位于C位置，頭朝向右，根據(jù)本文算法遍歷到A位置時，進入死角狀態(tài)。清掃機器人采用回溯法來走出這種死角，當清掃機器人進入柵格A時，前方、左方及右方柵格都沒辦法遍歷，清掃機器人將回到上一柵格B，之后回到柵格C，按逆時針(向左旋轉(zhuǎn)90°)、向前、順時針(向右旋轉(zhuǎn)90°)的行走優(yōu)先級規(guī)則，走向柵格D，從而走出死角。

圖3 回溯路徑圖

2 路徑規(guī)劃

本文對ISC算法進行改進，提出PISC算法，該算法的核心思想是直線行走和直角轉(zhuǎn)彎，下面闡述具體的路徑規(guī)劃思想及路徑規(guī)劃算法。

2.1 路徑規(guī)劃算法描述

本文首先采用柵格建模法對環(huán)境信息進行建模；在已建模好的柵格地圖中將ISC算法和行走優(yōu)先級結(jié)合，將柵格地圖的逆時針(向左旋轉(zhuǎn)90°)、向前、順時針(向右旋轉(zhuǎn)90°)作為行走優(yōu)先級，根據(jù)該優(yōu)先級判定清掃機器人下一個柵格的搜索，同時標記遍歷過的柵格。如果機器人前方是邊界，左邊或右邊柵格有障礙物存在或已被遍歷，機器人進入死角狀態(tài)，此時清掃機器人采用回溯法沿原路徑回退，之后根據(jù)清掃機器人的行走優(yōu)先級進一步判定繼續(xù)PISC搜索，直到所有柵格被遍歷完為止。具體的算法流程如圖4所示。

圖4 PISC算法流程圖

2.2 路徑規(guī)劃算法

本文提出的全覆蓋路徑規(guī)劃算法——帶行走優(yōu)先級的ISC算法(PISC)具體描述如下：

Step 1在平面內(nèi)利用柵格建模法對清掃環(huán)境建模，將環(huán)境抽象為二維柵格。

Step 2在抽象的二維柵格中，標記為“0”的柵格表示存在障礙物柵格，標記為“1”的柵格表示無障礙物柵格，即需清掃柵格。

Step 3清掃機器人所在的柵格作為當前路徑開始搜索的柵格，且清掃機器人從此搜索并清掃。

Step 4判定清掃機器人左邊柵格是否是自由柵格，如果是則向左旋轉(zhuǎn)90°且移動一個柵格，轉(zhuǎn)Step4。

Step 5判定清掃機器人前邊柵格是否是自由柵格，如果是則向前移動一個柵格，轉(zhuǎn)Step4。

Step 6判定清掃機器人右邊柵格是否是自由柵格，如果是則向右旋轉(zhuǎn)90°且移動一個柵格，轉(zhuǎn)Step4。

Step 7如果機器人進入死角狀態(tài)，清掃機器人采用回溯法沿原路徑執(zhí)行回退操作，直到左邊或右邊的障礙物結(jié)束，轉(zhuǎn)Step4。

Step 8如果所有標記為“1”的柵格被遍歷完，轉(zhuǎn)Step9，否則執(zhí)行回退操作，轉(zhuǎn)Step4。

Step 9算法結(jié)束。

3 仿真結(jié)果

本文在Visual C++6.0環(huán)境使用PISC算法進行仿真，考慮到特殊的室內(nèi)環(huán)境障礙物，為了便于清掃機器人的路徑規(guī)劃，矩形化障礙物形狀。當室內(nèi)存在簡單障礙物時，利用此方法清掃機器人的運動路線如圖5所示。當室內(nèi)環(huán)境存在復雜的U型障礙物時，清掃機器人使用PISC算法進行路徑規(guī)劃，效果如圖6所示。

圖5 簡單障礙物清掃機器人遍歷路徑

圖6 復雜障礙物清掃機器人遍歷路徑

結(jié)果表明，在簡單的室內(nèi)環(huán)境中，清掃機器人能按照PISC算法完成室內(nèi)清掃任務，執(zhí)行效率比較高、重復率比較少；在比較復雜的室內(nèi)環(huán)境中，清掃機器人也可以完成室內(nèi)清掃任務，當清掃機器人進入死角時，回溯法能夠解決這一問題，使清掃機器人進入下一步搜索。

4 結(jié)束語

移動機器人全覆蓋路徑規(guī)劃技術(shù)在今后的實際生活中有著越來越重要的應用。本文提出了一種新的基于已知環(huán)境信息的全覆蓋路徑規(guī)劃算法(PISC)，該算法首先對已知的環(huán)境信息進行柵格建模，生成二維的柵格地圖；其次將ISC算法與行走優(yōu)先級逆時針(向左轉(zhuǎn)90°)、向前、順時針(向右轉(zhuǎn)90°)相結(jié)合，當環(huán)境中存在障礙物時，該方法能繞過障礙物且減少了由于障礙物的存在而形成的未覆蓋區(qū)域；最后該算法能夠利用回溯法解決清掃機器人的死角狀態(tài)。在簡單的室內(nèi)環(huán)境和復雜的室內(nèi)環(huán)境進行的仿真結(jié)果表明了該算法的可行性，在重復率比較低的情況下提高了覆蓋率和清掃效率。