基于籠圖-快速搜索的移動機器人目標搜索

孫曉莉，鐘發榮

(浙江師范大學 數學與計算機科學學院，浙江 金華 321000)

0 引 言

在生物界存在一類常見問題，群狼搜索一只羊。若搜索區域存在道路縱橫交錯的山洞，為了搜索到羊，群狼該如何利用最少的狼按照某種路線盡早捉到羊呢?移動機器人目標搜索與此類動物捕食問題類似，主要是研究一群作為搜索者的機器人應當如何合作、采取怎樣的搜索策略去搜索目標。移動機器人目標搜索是實現救援、防御等任務的重要環節，是多機器人研究的重要內容之一[1-4]。所謂搜索問題，即搜索者試圖搜索到目標。在某特定區域的移動機器人目標搜索實質是圖搜索問題(graph searching)的實際應用案例。圖搜索，即一群搜索者在某類圖上利用最少的搜索者去搜索目標。因此，考慮將給定區域的移動機器人目標搜索問題的搜索區域抽象為類似結構的圖，然后選用合適的圖搜索模型，將其轉化為圖搜索問題進行研究。

針對不同的搜索問題，圖搜索問題提供了多種模型，如邊搜索、點搜索、混合搜索、快速搜索等[5-9]。考慮到移動機器人目標搜索問題中機器人造價花費高及機器人需避免出現來回往返移動等需求，文中利用快速搜索模型進行研究。Dyer等人[10]介紹了快速搜索模型并提出一種用于計算樹的快速搜索數的線性時間算法。Stanley和Yang[11]給出一個用于計算Halin圖的快速搜索數的線性時間算法，并提出一種二次時間算法來計算三次圖的快速搜索數。Yang[12]證明了求解圖的快速搜索數是NP完全問題，他還證明了判斷圖G的快速搜索數是否等于G中奇數頂點數的一半是NP完全問題；Dereniowski等人[13]描述了一種在快速搜索模型中用兩個或三個搜索者就足夠搜索到入侵者的圖，并證明了圖的快速搜索問題是NP難問題。Xue等人[14]提出完全k部圖、完全分割圖的快速搜索數的下界和上界，并確定了完全二部圖的快速搜索數。Xue[15]還給出了笛卡爾積圖的快速搜索數。

目前，在快速搜索模型的研究中僅研究了樹、Halin圖、完全k部圖、完全分割圖等的快速搜索數，還有大量不同結構圖的快速搜索問題沒有研究。然而，移動機器人目標搜索等實際問題中的搜索區域結構往往各不相同，當遇到除上述已有成果外的搜索區域時，已經提出的圖的快速搜索數及其快速搜索算法不能滿足其他區域的移動機器人目標搜索。因此，針對上述問題，考慮到實際生活中存在機器人在類似籠圖結構的區域進行目標搜索，根據籠圖的特定性質，確定籠圖的快速搜索數下界，然后根據下界及搜索策略給出快速搜索數，提出一種基于籠圖的快速搜索算法。該算法對求解與籠圖類似區域的移動機器人目標搜索問題具有重要意義。

1 基本概念

為了論述方便，引入以下基本概念及符號[16-18]。

1.1 圖論概念

假設G=(VG,EG)是簡單無向圖，其中VG和EG分別表示圖G的頂點集和邊集。用uv表示連接頂點u和v的邊。如果uvEG，則稱u和v鄰接。若E'是EG的子集，V'是VG的子集，則稱H=(V',E')是G的子圖。如果頂點集S?V，那么G[S]表示圖G中由S導出的子圖。對于VG的子集X，稱NG(X)={u∈VG|?v∈X,uv∈EG}為X的鄰接頂點集。若X只有一個元素u，則用NG(u)表示u的鄰接頂點集。頂點u的鄰接頂點集大小，即u的鄰接頂點數，稱為u的度或價，用符號d(u)或r表示，顯然有d(u)=|NG(u)|=|{v∈VG|uv∈EG}|。

圖G的一條通道(walk)是指一個有限的非空序列W=v0e1v1e2v2…ekvk，其中vi∈VG(0≤i≤k)，ej=vj-1vj∈EG(1≤j≤k)。若通道W中的邊互不相同，則稱之為跡(trail)。若跡W的長度為正且起點和終點相同，則稱之為閉跡(trail)。若通道W中的頂點互不相同，則稱之為路徑(path)。使用p=v1v2…vk表示起點為v1和終點為vk的路徑。路徑中邊的數目稱為路徑長度。若一條閉跡的起點和內部頂點互不相同，則稱之為簡單回路，也稱為圈(cycle)，記為C。圈中的邊數稱為圈的長度，長度為k的圈稱為k-圈，記為Ck。圖中最短圈的長度也稱為圍長(girth)，記為g。不在圈上但連接圈中兩個頂點的邊稱為該圈的弦(chord)(如圖1所示)。經過G的每條邊一次并且僅一次的路徑稱為歐拉通路。如果歐拉通路是回路(起點和終點是同一個頂點)，則稱此回路為歐拉回路(Euler circuit)。

圖1 弦與非弦示意

1.2 快速搜索

快速搜索是一個在連通無向圖上進行的搜索問題，該模型由對立的搜索者和入侵者雙方組成。搜索初，圖G上沒有搜索者，但圖G包含一個隱藏在頂點或邊上的入侵者，故搜索開始時，假設整個圖都是污染的。在搜索過程中，搜索者和入侵者分別在圖上移動，其中搜索者只能從一個頂點滑動到與其相鄰接的頂點，且搜索者看不見入侵者，只能根據每一次的移動路徑等信息，推測入侵者的位置信息；入侵者可以在任意時刻以任意快的速度沿著一條沒有搜索者的路徑滑動，去躲避搜索者的搜索[10-12]。在該模型中，搜索者可以采取兩種動作：占據在某一頂點(放置)、從某一頂點滑動到相鄰頂點(滑動)。放置動作須發生在滑動動作前。

如果一條邊uv可能包含入侵者，則稱之為污染的，否則稱之為干凈的。可以采取以下兩種動作搜索一條邊uv，使之成為干凈的邊：

若頂點u包含大于等于兩個搜索者，滑動其中一個搜索者從u沿邊uv到v；

若頂點u包含一個搜索者，并且uv是唯一一條與u關聯的污染的邊，則滑動u上的搜索者沿邊uv到v。

如果確定某個頂點沒有關聯污染的邊，則稱該頂點為干凈的，否則稱它為污染的。在快速搜索模型中，圖中的每條邊只允許遍歷一次。如果某個頂點只包含一個搜索者，并且與該頂點關聯的污染的邊的數量大于該頂點上的搜索者的數量，則該頂點上的搜索者不能滑動離開該頂點，否則干凈的頂點和邊會重新被污染。

當所有的邊和頂點都被搜索過，即搜索者搜索到入侵者，搜索結束。圖的搜索策略即搜索者所移動的路線的集合。圖G的快速搜索數，即在圖上搜捕到入侵者所需要的最小的搜索者數，用fs(G)表示。如果一個策略使用fs(G)個搜索者搜捕到入侵者，則稱此策略是搜索圖G的最優搜索策略。

用VC表示干凈的頂點的集合，VZ表示污染的頂點的集合，EC表示干凈的邊的集合，EZ表示污染的邊的集合。snum(v)表示頂點v上的搜索者數量，csnum(v)表示可以在頂點v上滑動到其他頂點的搜索者數量,EZ(v)表示與頂點v關聯的污染的邊的集合。

2 籠圖的快速搜索

對r=2的籠圖G2,g，由于G2,g是g-圈，只需要在圖中的某一頂點放置兩個搜索者，移動其中一個沿圈Cg搜索即可搜索到目標，易得fs(G2,g)=2。

對g=2的籠圖Gr,2，由于Gr,2只有兩個頂點且由r個邊連接，易得fs(Gr,2)=3。

在本節中，首先研究籠圖的性質，利用頂點度和邊的關系給出籠圖G3,g(3≤g≤12)、G4,g(3≤g≤8)的快速搜索數的下界；其次，根據快速搜索數的下界給出籠圖G3,g(3≤g≤12)、G4,g(3≤g≤8)、Gr,4的快速搜索數。

2.1 快速搜索數的下界

定理1：對r=3,3≤g≤12籠圖G3,g，有

定理2：對r=4,3≤g≤8的籠圖G4,g，有：

類似定理1的證明可證，不再贅述。

2.2 籠圖的快速搜索數

下面給出r=3，3≤g≤12、r=4，3≤g≤8以及g=4的籠圖的快速搜索數。

引理1：對r=3,g=3的籠圖，有fs(G3,3)=4。

證明：根據定理1得，fs(G3,3)≥4。下面采用一個4個搜索者的策略進行搜索(G3,3見圖2)。

首先在頂點v1放置搜索者γ1、γ2、γ3，在頂點v4放置搜索者γ4，然后進行以下移動動作：

(1)移動γ1從頂點v1沿邊v1v4到頂點v4，移動γ2從頂點v1沿邊v1v3到頂點v3，移動γ3從頂點v1沿邊v1v2到頂點v2。

(2)移動γ4從頂點v4沿路徑v4v3v2v4到頂點v4。

此時，G被搜索干凈，因此對于(3,3)-籠圖，有fs(G3,3)=4，引理1成立。

圖2 (3,3)籠

引理2：對r=3，g=4的籠圖，有fs(G3,4)=5。

引理3：對r=3，g=5的籠圖，有fs(G3,5)=7。

引理4：對r=3，g=6的籠圖，有fs(G3,6)=9。

引理5：對r=3，g=7的籠圖，有fs(G3,7)=14。

引理6：對r=3，g=8的籠圖，有fs(G3,8)=17。

引理7：對r=3，g=9的籠圖，有fs(G3,9)=31。

引理8：對r=3，g=10的籠圖，有fs(G3,10)=37。

引理9：對r=3，g=11的籠圖，有fs(G3,11)=58。

引理10：對r=3，g=12的籠圖，有fs(G3,12)=65。

證明類似，不再逐一證明。

下面給出當r=3，3≤g≤12時，籠圖的快速搜索數的定理。

根據定理1以及引理1到引理10可證，不再贅述。

引理11：對r=4,g=3的籠圖，有fs(G4,3)=5。

證明：根據定理2得，fs(G4,3)≥5。下面采用一個5個搜索者的策略進行搜索(G4,3見圖3)。首先在頂點v1放置搜索者γ1、γ2、γ3。γ4在頂點v5放置搜索者γ5，然后進行以下移動動作：

(1)移動γ1從頂點v1沿邊v1v5到頂點v5，移動γ2從頂點v1沿邊v1v4到頂點v4，移動γ3從頂點v1沿邊v1v3到頂點v3，移動γ4從頂點v1沿邊v1v2到頂點v2。

(2)移動γ5從頂點v5沿路徑v5v4v3v2v5到頂點v5；

(3)移動γ1從頂點v5沿邊v5v3到頂點v3。

(4)移動γ4從頂點v2沿邊v2v4到頂點v4。

此時，圖被搜索干凈，因此對于(4,3)-籠圖，引理成立。

圖3 (4,3)籠

引理12：對r=4,g=4的籠圖，有fs(G4,4)=7。

引理13：對r=4,g=5的籠圖，有fs(G4,5)=12。

引理14：對r=4,g=6的籠圖，有fs(G4,6)=15。

引理15：對r=4,g=7的籠圖，有fs(G4,7)=31。

引理16：對r=4,g=8的籠圖，有fs(G4,8)=37。

上述引理證明類似，不再逐一列出。

下面給出當r=4，3≤g≤8時，籠圖的快速搜索數的定理。

定理4：對任意r=4,3≤g≤8的籠圖，有：

根據定理2以及引理11到引理16可證，不再贅述。

定理5：對于r≥3，g=4的籠圖，有fs(Gr,4)=2r-1。

證明：對r≥3，g=4的籠圖，給出以下快速搜索策略。

(1)在頂點v1放置r個搜索者γ1,γ2,…,γr，在頂點v|VG|放置r-2個搜索者γr+1,γr+2,…,γ2r-2，在頂點v2r-1放置搜索者γ2r-1。

(2)對i從1到r，滑動γi從頂點v1到頂點vj，其中vj∈NH(vi)，1≤j≤|VGr,4|。

(3)滑動頂點v|VG|上所有的搜索者從v|VG|分別到其每一個鄰接點vj，其中vj∈NH(v|VG|)。

(4)當r為奇數時，滑動搜索者γ2r-1從頂點v2r-1沿歐拉回路搜索H；當r為偶數時，滑動搜索者γ2r-1從頂點v2r-1沿H中的非弦邊到頂點v2r-1，然后滑動搜索者γ2r-1從頂點v2r-1沿其一條弦到其鄰接點搜索直到該搜索者不能再滑動。

(5)若此時H仍有污染的邊：

若H中存在vp滿足|EZ(vp)|=1，則滑動vp上的搜索者搜索與其關聯的污染的邊。若仍存在污染的邊，則繼續滑動其他能滑動的搜索者搜索H。

2.3 籠圖的快速搜索算法

下面給出搜索籠圖的快速搜索算法，輸入為籠圖Gr,g，輸出為放置搜索者的頂點集V和移動路徑序列S。算法大致思路為：(1)在圖中某一頂點v放置搜索者，并分別移動該頂點上的搜索者到其各個鄰接點；(2)此時若有滿足1≤|EZ(u)|≤snum(u)的頂點u，則滑動u上的搜索者沿污染的邊搜索；(3)否則，從頂點v的一個非弦鄰接點vi依次沿圈C|VGr,g|開始(當r=3,g=5時，從頂點v的任意一個鄰接點開始)，若|EZ(vi)|≥1且csnum(vi)<1，則在vi上放置搜索者，使其滿足|EZ(vi)|≤snum(vi)，然后滑動vi上搜索者搜索vi的鄰接點；(4)令vi的一個非弦鄰接點為新的vi(當r=3,g=5時，令vi的任意一個鄰接點為新的vi),重復步驟2～步驟4，直到每個頂點都沒有污染的邊，即圖完全干凈。下面給出具體搜索算法，算法SC為搜索籠圖G3,g(3≤g≤12)、G4,g(3≤g≤8)的搜索算法。

算法SC：

1.在vj放置搜索者，分別移動vj上的搜索者到其各個鄰接點

2.ifr=3,g=5 then

3.選擇vj的一個鄰接點vp，令i←p

4.else

5.選擇vj的一個鄰接點vncj，令i←ncj

6.end if

7.whileEZ≠? do

8.while除了vi有滿足1≤|EZ(u)|≤snum(u)的頂點udo

9.滑動u上的搜索者沿污染的邊搜索

10.end while

11.while除了vi所有的臟點滿足csnum(vi)<1 and|EZ(vi)|≥1 do

12.ifvi滿足snum(vi)≤1 and|EZ(vi)|≥1 then

13.在vi上放置|EZ(vi)|-1個搜索者,分別移動vi的搜索者到其鄰接點

14.end if

15.ifvi滿足snum(vi)≥2 and|EZ(vi)|≥1 then

16.分別移動vi的搜索者到其鄰接點

17.end if

18.ifr=3,g=5 then

19.令vi的一個鄰接點為新的vi

20.else

21.令vi的一個非弦鄰接點為新的vi

22.end if

23.end while

24.end while

3 實例分析

為保證籠圖的快速搜索算法的準確性，本節將對2.3節中的算法SC進行實驗驗證。實驗的測試例圖為(3,5)籠、(3,6)籠、(4,4)籠。具體數據見表1。其中|VG|為頂點數，|EG|為邊數，fs(G)為快速搜索數。

表1 實驗測試例圖數據

3.1 算法SC在籠圖G3,5上的實驗

根據引理3可知，搜索籠圖G3,5需要7個搜索者。實驗過程如下：在第0輪，在頂點v1放置三個搜索者，第1輪，移動頂點v1的搜索者去搜索；第2輪，在頂點v5放置一個搜索者，移動頂點v5上的搜索者去搜索；第3輪，在頂點v4放置一個搜索者，移動v4上的搜索者去搜索；第4輪，在頂點v3放置一個搜索者，移動v3上的搜索者去搜索；第5輪，移動v2上的搜索者去搜索；第6輪，在頂點v7放置一個搜索者，移動v7的搜索者去搜索。下面由表2給出搜索過程中搜索者的位置、臟邊集合、臟點集合的變化。其中i為移動的輪次，Vi為搜索者每輪所在位置集合，EZ為臟邊集合(搜索者的移動路徑)，VZ為臟點集合，且EZ、VZ隨輪次i變化。

表2 搜索過程中G3,5臟點集與臟邊集隨搜索輪次的變化

圖4所示為搜索過程中，臟點和臟邊的變化過程及實驗結果。其中三角形頂點表示已經搜索過的頂點，虛線表示已經搜索過的邊，圓形頂點表示未搜索的頂點，實線邊表示未搜索的邊。

圖4 (3,5)籠的部分搜索過程示意

通過表2和圖4可以看出，實驗經6輪搜索后，臟點集合和臟邊集合為空集，圖4(c)為最后結果，可以看出G3,5中的所有頂點皆為三角形、所有邊皆為虛線，即G3,5中的臟點和臟邊全部被搜索完。

3.2 算法SC在籠圖G3,6上的實驗

根據引理4可知，搜索籠圖G3,6需要9個搜索者。實驗過程如下：在第0輪，在頂點v1放置三個搜索者；第1輪，移動頂點v1的搜索者去搜索；第2輪，在頂點v14放置一個搜索者，移動頂點v14上的搜索者去搜索；第3輪，在頂點v13放置一個搜索者，移動v13上的搜索者去搜索；第4輪，在頂點v12放置一個搜索者，移動v12上的搜索者去搜索；第5輪，在頂點v11放置一個搜索者，移動v11上的搜索者去搜索；第6輪，移動v10的搜索者去搜索；第7輪，在頂點v9放置一個搜索者，移動v9的搜索者去搜索；第8輪，移動v8的搜索者去搜索；第9輪，在頂點v7放置一個搜索者，移動v7的搜索者去搜索。下面由表3給出搜索過程中搜索者的位置、臟邊集合、臟點集合的變化。其中i為移動的輪次，Vi為搜索者所在位置集合，EZ為臟邊集合(搜索者的移動路徑)，VZ為臟點集合，且EZ、VZ隨輪次i變化。

表3 搜索過程中G3,6的臟點集與臟邊集隨搜索輪次的變化

圖5所示為搜索過程中，臟點和臟邊的變化過程及實驗結果圖。其中圖中三角形頂點表示已經搜索過的頂點、虛線表示已經搜索過的邊，圓形頂點表示未搜索的頂點、實線邊表示未搜索的邊。

(a)i=0 (b)i=1 (c)i=9

通過表3和圖5可以看出，該實驗經9輪搜索后，臟點集合和臟邊集合為空集，其中圖5(c)為最后結果圖，從圖5可以看出G3,6中所有頂點皆為三角形、所有邊皆為虛線，即G3,6中的臟點和臟邊全部被搜索完。

3.3 算法SC在籠圖G4,4上的實驗

根據引理12可知，搜索籠圖G4,4需要7個搜索者。實驗過程如下：在第0輪，在頂點v1放置三個搜索者；第1輪，移動頂點v1的搜索者去搜索；第2輪，在頂點v8放置2個搜索者，移動頂點v8上的搜索者去搜索；第3輪，在頂點v7放置一個搜索者，移動v7上的搜索者去搜索；第4輪，移動v6上的搜索者去搜索；第5輪，移動v5上的搜索者去搜索。下面由表4給出搜索過程中搜索者的位置、臟邊集合、臟點集合的變化。其中i為移動的輪次，Vi為搜索者所在位置集合，EZ為臟邊集合(搜索者的移動路徑)，VZ為臟點集合，且EZ、VZ隨輪次i變化。

表4 搜索過程中G4,4的臟點集與臟邊集隨搜索輪次的變化

圖6所示為搜索過程中，臟點和臟邊的變化過程及實驗結果圖。其中三角形頂點表示已經搜索過的頂點，虛線表示已經搜索過的邊，圓形頂點表示未搜索的頂點，實線邊表示未搜索的邊。

(a)i=0 (b)i=1 (c)i=5

通過表4和圖6可以看出，該實驗經5輪搜索后，臟點集合和臟邊集合皆為空集，其中圖6(c)為最后結果，可見籠圖G4,4中所有頂點皆為三角形、所有邊皆為虛線，即圖中所有頂點和邊都被搜索過，完成對籠圖G4,4的搜索。

3.4 總結與分析

在上述三個例圖實驗中，根據2.2節給出的搜索數引理，利用算法SC根據頂點關聯的污染的邊數放置搜索者(機器人)的個數，又在每條邊搜索的過程中遵循只搜索一次的規則完成在整個區域對目標的搜索。從表2、表3、表4可以看出臟邊一直在減少，且被搜索過的臟邊不會再次成為臟邊，即搜索者對每條邊只搜索了一次，減少了搜索次數；從圖4(c)、圖5(c)、圖6(c)可見，圖中所有頂點皆為三角形、所有邊皆為虛線，即都已被搜索者搜索過，有效地完成了對籠圖G3,5、G3,6、G4,4的搜索。因此，實驗表明算法SC在經有限輪次后使籠圖中的臟點和臟邊集合皆為空集，有效地完成了對整個籠圖區域的搜索。

4 結束語

針對籠圖區域的移動機器人目標搜索問題，對籠圖快速搜索建模，通過對籠圖性質的探索得到籠圖的快速搜索數的下界及籠圖的快速搜索數。提出一種基于籠圖的快速搜索算法，用于解決籠圖形狀區域的移動機器人目標搜索問題。在快速搜索模型下對籠圖的頂點和邊進行搜索，經在三個籠圖實例上的模擬驗證，該算法可以有效地使機器人在不知道目標具體位置的情況下，逐步搜索到目標。該研究為基于籠圖的移動機器人目標搜索問題的求解提供了一種新思路和可行的搜索策略,但仍需進一步在大規模問題上研究。