一種改進(jìn)的網(wǎng)格多邊形online探索算法

謝玉瑩 包敏澤 胡秀婷 蔣 波

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116026)

0 引 言

利用移動機(jī)器人探測未知環(huán)境的路徑規(guī)劃問題可描述為：在一個(gè)邊界信息未知的網(wǎng)格區(qū)域P中，機(jī)器人從初始位置出發(fā)，在區(qū)域P內(nèi)做上、下、左、右四個(gè)方向上的移動，但每次僅限移動一個(gè)單元格，要求機(jī)器人能完全遍歷給定的網(wǎng)格區(qū)域，最終返回到出發(fā)點(diǎn)，并使得其移動路線的長度達(dá)到最短。該問題一直受到計(jì)算幾何學(xué)[1-4]、機(jī)器人學(xué)[5]領(lǐng)域?qū)W者的廣為關(guān)注，并取得了較好的研究成果[6-11]。該問題的研究成果可在自動割草機(jī)、自動澆水機(jī)、掃地機(jī)器人等智能設(shè)備的開發(fā)中得到廣泛應(yīng)用，因此值得進(jìn)一步展開研究。

在online探索問題研究中，要探索的區(qū)域往往是邊界信息未知的，因此一般難以設(shè)計(jì)出最優(yōu)的探索策略[12-15]。為了對比分析online探索問題的求解策略，通常引入“競爭比”的概念。所謂競爭比，它可定義為探索策略的代價(jià)(可以是探索路徑的長度或探索所需要的時(shí)間)與邊界信息已知情形下的最優(yōu)搜索策略所需代價(jià)的比。由于邊界信息已知，所以往往能夠設(shè)計(jì)出好的搜索策略，甚至是最優(yōu)搜索策略。但是，當(dāng)邊界信息未知時(shí)，機(jī)器人往往需要反復(fù)探索，所以競爭比通常大于1。顯然，online探索問題的改進(jìn)方向就在于設(shè)法降低算法的競爭比。

針對網(wǎng)格區(qū)域的online探索問題，可通過對網(wǎng)格做深度優(yōu)先(DFS)來實(shí)現(xiàn)競爭比為2的簡單探索。對于正方形單元格，文獻(xiàn)[6]提出了SmartDFS算法，將競爭比優(yōu)化為4/3。文獻(xiàn)[8]將該問題的競爭比的上界更新為5/4；文獻(xiàn)[15]證明了三角形單元格不存在競爭比優(yōu)于7/6的算法；六邊形單元格不存在競爭比優(yōu)于13/11的算法[15]。

online探索算法可用于解決一些實(shí)際應(yīng)用問題。文獻(xiàn)[9]提出了一個(gè)帶洞網(wǎng)格多邊形中哈密爾頓路徑存在的必要條件，并證明了網(wǎng)格圖中哈密頓路徑可在線性時(shí)間內(nèi)算出；文獻(xiàn)[7]進(jìn)一步研究了基于online探索的疏散問題，將競爭比從19.5降低為不超過17.5，使受災(zāi)人員能更加快地速撤離出網(wǎng)格類型的受災(zāi)區(qū)域。

為方便研究，假設(shè)機(jī)器人要探索的網(wǎng)格區(qū)域?yàn)镻，P中每個(gè)網(wǎng)格的邊緣是垂直或水平的，且每個(gè)網(wǎng)格為單位長度的正方形。P的邊界是一個(gè)簡單多邊形，并以網(wǎng)格的邊作為邊界。除了邊界外，P的內(nèi)部不存在阻礙機(jī)器人移動的任何障礙物。

在這類問題研究中，通常對機(jī)器人的能力做不同約束：除了機(jī)器人的視距范圍外，還有機(jī)器人的感知范圍、移動限制、記憶能力、標(biāo)記能力等。本文對機(jī)器人的能力定義如下：機(jī)器人每次移動距離為一個(gè)單位長度，移動方向?yàn)榛谇斑M(jìn)方向的上、下、左、右；機(jī)器人具有足夠的記憶能力，但卻沒有先驗(yàn)?zāi)芰?；機(jī)器人在當(dāng)前位置能且僅能感知到3/2個(gè)單位長度范圍內(nèi)的網(wǎng)格狀態(tài)(在P的內(nèi)部或者在P的邊界)。

在本文研究中，約定機(jī)器人具有視覺范圍，但范圍是受限的。文獻(xiàn)[6]約定機(jī)器人的視覺范圍為一個(gè)正方形單元格，本文對之做了改進(jìn)，讓機(jī)器人的可視范圍最大化，并將機(jī)器人的視覺范圍定義為相應(yīng)單元格的外接圓，在理論上盡可能充分利用機(jī)器人的可視范圍，設(shè)計(jì)出性能更優(yōu)的探索策略。從實(shí)際應(yīng)用的角度看，機(jī)器人的視距范圍是圓形更切合生活實(shí)際。例如，在考古或救災(zāi)等場合需要探索一些惡劣環(huán)境時(shí)，使用機(jī)器人探索是最安全、適宜的，而這時(shí)的機(jī)器人視覺范圍通常是受限的，因此為機(jī)器人附加一些約束條件是具有可操作性與實(shí)際意義的。

1 online探索策略

由于P為由整數(shù)個(gè)網(wǎng)格單元組成的簡單多邊形，P的內(nèi)部無阻塞(如圖1所示)，所以遍歷多邊形P的機(jī)器人路徑應(yīng)包括在P中。文獻(xiàn)[6，8]中的機(jī)器人在遍歷多邊形P時(shí)，其位置處于單元格中心，有效遍歷區(qū)域僅為機(jī)器人視覺范圍的內(nèi)接正方形，本文擴(kuò)大了機(jī)器人的可視范圍，即遍歷范圍大于文獻(xiàn)[6，8]所定義的范圍如圖2所示。其中，陰影正方形是改進(jìn)之前的機(jī)器人視覺范圍，而整個(gè)圓圈則是改進(jìn)后的機(jī)器人視覺范圍。利用擴(kuò)大的視覺范圍，讓機(jī)器人從P的某單元格邊界出發(fā)，逐個(gè)遍歷P中的單元格，最終返回出發(fā)點(diǎn)。

圖1 內(nèi)部無阻塞的簡單網(wǎng)格多邊形

圖2 機(jī)器人不同的可視范圍

不失一般性，假設(shè)機(jī)器人的初始位置在網(wǎng)格多邊形的右上角，即機(jī)器人的右邊是多邊形的邊界，左邊或下邊是可訪問的單元格，如圖3所示。若機(jī)器人的初始位置不滿足該約定，則可預(yù)先將它移動到相應(yīng)的位置，且初始所做的移動操作不會影響本文的結(jié)果。

圖3 可視范圍最大情形下機(jī)器人遍歷網(wǎng)格多邊形的示例

機(jī)器人在單元格邊緣上移動時(shí)，往往難以發(fā)現(xiàn)機(jī)器人行走路徑與網(wǎng)格單元間的關(guān)系，為此，本文將P整體向右平移1/2個(gè)單元格，并在P的最左邊增加一列單元格，稱該操作為P+處理，經(jīng)過P+處理得到的多邊形為P+多邊形。如圖4所示，其中陰影部分為添加的單元格。

圖4 多邊形P+

P+處理有利于競爭比分析，且并不改變機(jī)器人對P的遍歷路徑。由于P+處理后機(jī)器人的初始位置約定為多邊形P+右上角的單元格，所以機(jī)器人初始方向右邊的位置可標(biāo)記為返回單元格(如圖4中的斜線陰影單元格所示)。在探索過程中，返回單元格可作為一般單元格在最后被訪問。

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

在SmartDFS算法[6]和算法A[8]的基礎(chǔ)上，本文提出了SmartDFS-OPT算法。將機(jī)器人遍歷過的單元格(包括機(jī)器人當(dāng)前所在的單元格)記為已訪問單元格，未遍歷的單元格記為未訪問單元格，并對未訪問單元格做進(jìn)一步細(xì)分。

定義1若未訪問單元格滿足下列條件，則稱之為A類單元格。

(1) 機(jī)器人當(dāng)前位置與該單元格相鄰。

(2) 該單元格周圍的四個(gè)位置中有3個(gè)或4個(gè)位置，要么是已經(jīng)訪問過的單元格，要么是多邊形邊界及其外部。

顯然，A類單元格可分為包含邊界邊的邊界A類單元格和不包含邊界邊的內(nèi)部A類單元格。

定義2若未訪問單元格滿足下列所有條件，則稱之為B類單元格。

(1) 該單元格位于機(jī)器人當(dāng)前位置的前方(機(jī)器人前進(jìn)方向上的下一個(gè)單元格)。

(2) 已訪問單元格與該單元格的集合恰好包圍了一塊未訪問單元格區(qū)域P′。

圖5給出了上述定義的幾個(gè)示例，其中，圖5(a)中陰影部分的單元格為邊界A類單元格；圖5(b)中陰影部分的單元格為B類單元格，斜線陰影單元格為內(nèi)部A類單元格。

圖5 A類單元格和B類單元格示例

算法SmartDFS-OPT描述如下：

1)設(shè)置未訪問單元格堆棧N和存儲A、B類單元格的未訪問單元格堆棧V，并設(shè)置堆棧N和V的初值為空。

2)機(jī)器人每移動一步，均做以下更新：

(1) 將機(jī)器人周圍的未訪問單元格按如下規(guī)則分別加入N或V中。

① 若為內(nèi)部A類單元格或B類單元格，機(jī)器人將按照右、上、左的順序訪問它們，將未訪問單元格按優(yōu)先級順序加入棧N；

② 若為邊界A類單元格，機(jī)器人將按照左、上、右的順序訪問它們，將未訪問單元格按優(yōu)先級順序加入棧N；

③ 若為非A或B類單元格，機(jī)器人將按照左、上、右的順序訪問它們，將未訪問單元格按優(yōu)先級順序加入棧V。

(2)確定機(jī)器人的目的地。

① 若堆棧V非空，則目的地=堆棧V頂部；

② 若堆棧V空，堆棧N非空，則目的地=堆棧N頂部；

③ 若堆棧V和堆棧N皆空，則目的地=機(jī)器人初始位置。

3) 若機(jī)器人回到初始位置，則N和V為空，算法結(jié)束。

4) 否則，重復(fù)執(zhí)行步驟2)。

由于本文將文獻(xiàn)[8]提出的死端概念進(jìn)一步劃分為A類單元格，因而很好地避免了算法A[8]因局部遍歷而得到的最壞情形，如圖6和圖7所示。

圖6 算法A的最壞情形

圖7 用SmartDFS-OPT算法解決圖6所示的最壞情形

圖7所示的解決方法為SmartDFS-OPT算法的執(zhí)行結(jié)果，其具體描述如下：

用平面坐標(biāo)標(biāo)記每個(gè)單元格，并假定機(jī)器人的初始位置為(1, 4)，并標(biāo)記(2, 4)為返回單元格。機(jī)器人沿多邊形邊緣移動至(3, 2)，此時(shí)它識別到(4, 2)、(3, 3)和(2, 2)為未訪問單元格，其中(4, 2)和(2, 2)為A類單元格。機(jī)器人優(yōu)先訪問邊界A類單元格(4, 2)，再通過最短路徑訪問內(nèi)部A類單元格(2, 2)，然后根據(jù)最短的未訪問路徑回到多邊形邊界單元格(6, 3)，…。當(dāng)機(jī)器人遍歷到(n-2,n-1)時(shí)，發(fā)現(xiàn)(n-1,n-1)和(n-2,n-2)都是內(nèi)部A類單元格，故優(yōu)先訪問右側(cè)單元格(n-1,n-1)，直至從預(yù)留的返回單元格返回初始位置。

3 算法性能分析

3.1 競爭比分析

由于機(jī)器人具有記憶功能，所以能夠根據(jù)局部視圖和遍歷記錄來區(qū)分單元格的類型。假設(shè)用Ti來表示重復(fù)訪問單元格i的次數(shù)，則有：

T=T2+2T3+…+(i-1)Ti

i=2,3,…

(1)

若多邊形P+中有X個(gè)單元格，則探索P+需要遍歷的單元格數(shù)量為：

S=X+T

(2)

引理1對于任意X>2的網(wǎng)格多邊形P+，機(jī)器人通過SmartDFS-OPT算法探索網(wǎng)格多邊形所走的路徑有：

(3)

式中：c為常數(shù)。

證明：

1) 若機(jī)器人在對多邊形探索過程中沒有遇到內(nèi)部A類單元格和B類單元格，則S不僅恰好符合式(2)且滿足式(3)關(guān)系。

2) 若機(jī)器人在對多邊形探索過程中遇到了B類單元格，則可把多邊形分成多個(gè)子多邊形分別處理，且綜合結(jié)果也滿足上述關(guān)系。

3) 若機(jī)器人在對多邊形探索過程中遇到了內(nèi)部A類單元格，則該多邊形存在骨架[8]，可對基本骨架做局部遍歷分析。假設(shè)一個(gè)存在基本骨架的最小反例多邊形P，滿足式(3)，那么P的基本骨架一定包括圖8所示的幾種情形，或斷開連接。

圖8 基本骨架的最小反例

斷開連接的情形可分別處理，容易得到證明。對于以圖8所示的6種骨架結(jié)尾的情形，可組合得到20種局部修改類型，通過這些局部修改，可在不改變遍歷方式的前提下，分析所有可能情形，求得Δ的值：

(4)

其中，

S′=S(P)-S(P′)

(5)

C′=C(P)-C(P′)

(6)

T′=T(P)-T(P′)

(7)

圖9給出了一個(gè)局部修改的示例，其中S′=4，X′=4，T′=0，則Δ=-2/3<0。

圖9 局部修改實(shí)例

其余19種情形可做類似的處理，均能得到Δ≤0的分析結(jié)果。限于篇幅，不一一列舉。

以上情形包括所有可能的例外情形，由于均有Δ≤0，所以引理1得證。

定理1可視范圍最大化情形下機(jī)器人對未知網(wǎng)格區(qū)域做online探索的競爭比不大于7/6。

證明：

由于本文引入了邊界A類單元格，且邊界A類單元格位于P+的最外層，所以確定為優(yōu)先訪問對象，且內(nèi)部A類單元格也是優(yōu)先訪問對象，這樣就縮短了返回路徑的長度。當(dāng)邊界A類單元格和內(nèi)部A類單元格位于機(jī)器人當(dāng)前位置的左右兩側(cè)時(shí)，可找到局部遍歷分析時(shí)的最壞情形，如圖10所示。

圖10 算法SmartDFS-OPT的最壞情形

因此，對于一般情形，有：

(8)

證畢。

綜上，SmartDFS-OPT算法的競爭比不超過7/6，即可視范圍最大化情形下機(jī)器人對未知網(wǎng)格區(qū)域的online探索的競爭比上界為7/6。因?yàn)镾martDFS算法[6]的競爭比下界為7/6，SmartDFS-OPT算法是通過擴(kuò)大視覺范圍而對其做的改進(jìn)，所以SmartDFS-OPT算法的競爭比下界也為7/6，也就是說，SmartDFS-OPT算法競爭比的上界和下界均為7/6，即SmartDFS-OPT算法為求解網(wǎng)格多邊形online探索問題的最優(yōu)算法。

3.2 算法實(shí)現(xiàn)

為驗(yàn)證SmartDFS-OPT算法的可靠性，本文通過編程對其進(jìn)行了仿真和對比試驗(yàn)，實(shí)驗(yàn)截圖如圖11所示，對于輸入數(shù)據(jù)182，系統(tǒng)隨機(jī)生成了一個(gè)有182個(gè)單元格的網(wǎng)格多邊形，并分別給出了算法A[8]、offline算法、SmartDFS-OPT算法執(zhí)行過程中機(jī)器人的遍歷路徑、遍歷路徑長度以及競爭比。

圖11 實(shí)驗(yàn)截圖

表1給出了20組隨機(jī)實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果。

表1 SmartDFS-OPT算法和算法A的對比試驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)顯示，SmartDFS-OPT算法的競爭比明顯小于算法A[8]的競爭比且小于7/6，因此SmartDFS-OPT算法優(yōu)于算法A。

4 結(jié) 語

本文提出了機(jī)器人視距最大化情形下網(wǎng)格多邊形的online探索算法，使求解算法的競爭比從5/4降低為7/6，達(dá)到了理論分析結(jié)果的下界，即為性能最優(yōu)的網(wǎng)格多邊形online探索算法。同時(shí)，通過隨機(jī)生成網(wǎng)格多邊形作為測試數(shù)據(jù)，對比分析了理論分析結(jié)果與實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文提出的算法SmartDFS-OPT的有效性。針對帶洞的網(wǎng)格區(qū)域online探索問題，視距最大化方法能否適用等問題，有待于今后做進(jìn)一步的研究。