李淑霞,楊俊成,2

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

0 引 言

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

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

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

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

1 基本概念

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

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

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

(1)

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

圖1 10×10的二維柵格圖

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

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

圖2 ISC算法示意圖

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

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

圖3 回溯路徑圖

2 路徑規(guī)劃

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

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

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

圖4 PISC算法流程圖

2.2 路徑規(guī)劃算法

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

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

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

Step 3清掃機(jī)器人所在的柵格作為當(dāng)前路徑開(kāi)始搜索的柵格，且清掃機(jī)器人從此搜索并清掃。

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

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

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

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

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

Step 9算法結(jié)束。

3 仿真結(jié)果

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

圖5 簡(jiǎn)單障礙物清掃機(jī)器人遍歷路徑

圖6 復(fù)雜障礙物清掃機(jī)器人遍歷路徑

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

4 結(jié)束語(yǔ)

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