謝玉瑩 包敏澤 胡秀婷 蔣 波

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

0 引 言

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

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

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

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

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

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

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

1 online探索策略

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

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

圖2 機器人不同的可視范圍

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

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

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

圖4 多邊形P+

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

2 算法設(shè)計

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

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

(1) 機器人當前位置與該單元格相鄰。

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

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

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

(1) 該單元格位于機器人當前位置的前方(機器人前進方向上的下一個單元格)。

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

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

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

算法SmartDFS-OPT描述如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

圖6 算法A的最壞情形

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

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

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

3 算法性能分析

3.1 競爭比分析

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

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

i=2,3,…

(1)

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

S=X+T

(2)

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

(3)

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

證明：

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

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

3) 若機器人在對多邊形探索過程中遇到了內(nèi)部A類單元格，則該多邊形存在骨架[8]，可對基本骨架做局部遍歷分析。假設(shè)一個存在基本骨架的最小反例多邊形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給出了一個局部修改的示例，其中S′=4，X′=4，T′=0，則Δ=-2/3<0。

圖9 局部修改實例

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

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

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

證明：

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

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

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

(8)

證畢。

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

3.2 算法實現(xiàn)

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

圖11 實驗截圖

表1給出了20組隨機實驗的實驗結(jié)果。

表1 SmartDFS-OPT算法和算法A的對比試驗

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

4 結(jié) 語

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