雙弱感知能力機(jī)器人在線協(xié)作街道搜索算法*

魏 琦，林韋達(dá)，吳 彤，任永功

遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧大連 116081

1 引言

未知區(qū)域中的目標(biāo)搜索是計(jì)算幾何學(xué)和機(jī)器人學(xué)中的熱點(diǎn)研究問題[1-3]，在機(jī)器人搜索、探索和監(jiān)控等領(lǐng)域有著廣泛的應(yīng)用[4-5]。近年來，國(guó)內(nèi)外眾多學(xué)者針對(duì)相關(guān)問題展開研究，并取得了一定成果。

本研究將機(jī)器人搜索區(qū)域抽象為街道模型[6]，即具有LR（left chain and right chain）可視性的簡(jiǎn)單多邊形。Klein[6]最先提出街道模型，并提出機(jī)器人從街道起點(diǎn)s出發(fā)，在線搜索街道終點(diǎn)t的街道搜索問題。該模型可視作對(duì)街道、河道、賽道場(chǎng)景的抽象，機(jī)器人從起點(diǎn)出發(fā)，在線搜索并到達(dá)終點(diǎn)，可看到場(chǎng)景內(nèi)的所有區(qū)域，進(jìn)而完成勘察、搜索、探索等任務(wù)。針對(duì)街道搜索問題，Klein[6]給出了競(jìng)爭(zhēng)比為5.72的在線算法，并證明算法的競(jìng)爭(zhēng)比下界為。自此，街道模型的相關(guān)問題獲得了學(xué)術(shù)界的廣泛關(guān)注。Tseng等[7]提出了在簡(jiǎn)單多邊形邊界上尋找所有可能作為起點(diǎn)和終點(diǎn)構(gòu)成街道的點(diǎn)對(duì)的算法。Ghosh和Saluja[8]提出了搜索路徑轉(zhuǎn)折次數(shù)最少的街道搜索算法。針對(duì)Klein[6]提出的競(jìng)爭(zhēng)比為5.72的街道搜索算法，多位學(xué)者先后提出新的算法，降低競(jìng)爭(zhēng)比，提升算法效率。最終，由Icking等[9]給出了與競(jìng)爭(zhēng)比下界相匹配的最優(yōu)算法。

上述街道模型的研究中，使用的機(jī)器人都具有較強(qiáng)的感知能力，其攜帶的感應(yīng)器不僅可以觀察可視區(qū)域內(nèi)的場(chǎng)景，還可以測(cè)量距離和角度，使得機(jī)器人在行進(jìn)的過程中可以根據(jù)感應(yīng)器收集到的信息繪制出街道的局部地圖。與感知能力較強(qiáng)的感應(yīng)器相對(duì)應(yīng)的，一些研究人員將關(guān)注點(diǎn)放在簡(jiǎn)單感應(yīng)器上，因?yàn)槠渚哂泻芏鄡?yōu)點(diǎn)，如價(jià)格低廉、抗干擾能力強(qiáng)、適應(yīng)性強(qiáng)等。Tovar等[10]最先提出弱感知模型，機(jī)器人攜帶的感應(yīng)器僅能探測(cè)可視區(qū)域內(nèi)搜索區(qū)域邊界的不連續(xù)情況，借助數(shù)據(jù)結(jié)構(gòu)GNT（gap navigation tree），這些搜索區(qū)域邊界的不連續(xù)情況可被保存和更新，用于制定機(jī)器人的搜索策略。Lopez-Padilla等[11]在弱感知模型下研究了使用盤式機(jī)器人在簡(jiǎn)單多邊形區(qū)域中搜索目標(biāo)點(diǎn)的問題。Tabatabaei等[12]在弱感知模型下研究了街道搜索問題，受雙倍策略[13]啟發(fā)，提出了競(jìng)爭(zhēng)比為11的在線搜索算法。Wei等[14]又針對(duì)此問題提出了競(jìng)爭(zhēng)比為9的算法，并通過給出相匹配的競(jìng)爭(zhēng)比下界證明了算法的最優(yōu)性，同時(shí)還去掉了機(jī)器人需要攜帶位置標(biāo)記裝置及使用數(shù)據(jù)結(jié)構(gòu)SGNT（street gap navigation tree）的限制。

與單機(jī)器人在未知環(huán)境下搜索目標(biāo)相比，使用多機(jī)器人協(xié)作完成目標(biāo)搜索具有并行處理、容錯(cuò)率高、信息冗余等優(yōu)點(diǎn)[15-17]，不僅有助于克服傳感器和環(huán)境的不確定性，而且還擴(kuò)展了單個(gè)機(jī)器人的搜索功能。Czyzowicz等[18]研究了使用多個(gè)機(jī)器人在一條直線上搜索目標(biāo)的問題，并給出了競(jìng)爭(zhēng)比為2的在線搜索算法。Burgard等[19]、Ortolf等[20]研究了使用多個(gè)機(jī)器人探索未知區(qū)域的問題。

在上述研究基礎(chǔ)上，本研究提出雙弱感知能力機(jī)器人在線協(xié)作街道搜索問題，研究使用兩個(gè)弱感知能力機(jī)器人從街道起點(diǎn)s出發(fā)，在預(yù)先不知道街道幾何信息的前提下，協(xié)作搜索街道終點(diǎn)t。本研究提出了競(jìng)爭(zhēng)比為3的在線協(xié)作搜索算法，并通過給出相匹配的競(jìng)爭(zhēng)比下界，證明了算法的最優(yōu)性。

2 模型描述

本章將從搜索場(chǎng)景、感應(yīng)器、機(jī)器人動(dòng)作初始設(shè)定等方面給出雙弱感知能力機(jī)器人在線協(xié)作街道搜索模型的描述。

設(shè)P為一簡(jiǎn)單多邊形，bd為P的邊界。設(shè)p、q為P內(nèi)部的兩點(diǎn)，如果線段完全在P的內(nèi)部，則稱p、q兩點(diǎn)相互可視。對(duì)于P內(nèi)部的兩個(gè)點(diǎn)集A、B，若A中任意一點(diǎn)p，B中都至少存在一點(diǎn)q與之相互可視，反之亦然，則稱集合A與B相互弱可視。

定義1（街道）設(shè)P為一簡(jiǎn)單多邊形，其邊界上有兩個(gè)不相同的點(diǎn)s和t。設(shè)L和R分別表示P上從s到t的兩條邊界鏈。如果L和R相互弱可視，則稱(P,s,t)為街道，其中s為起點(diǎn)，t為終點(diǎn)。

設(shè)點(diǎn)集Vis(a)={q∈P|a與q相互可視}表示點(diǎn)a(a∈P)在P內(nèi)的可視區(qū)域。如圖1所示，為一街道P及其起點(diǎn)s的可視區(qū)域Vis(s)。兩個(gè)機(jī)器人從起點(diǎn)s出發(fā)，協(xié)作搜索并到達(dá)終點(diǎn)t，本研究的目標(biāo)即為兩個(gè)機(jī)器人規(guī)劃高效的協(xié)作搜索路徑。

Fig.1 Street P,visibility region of P at s,gaps A,B and C,the shortest path SP圖1 街道P，Vis(s)，間隔A、B、C，最短路徑SP

定義2（間隔）設(shè)Vis(a)為機(jī)器人在街道P內(nèi)a點(diǎn)的可視區(qū)域，Vis(a)邊界上的構(gòu)造部分（非P的邊界）稱為間隔。

機(jī)器人攜帶有視覺感應(yīng)器，但感知能力較弱，僅能探測(cè)可視區(qū)域內(nèi)街道邊界的不連續(xù)情況（間隔），并可為間隔加上L或R標(biāo)簽。相對(duì)于機(jī)器人當(dāng)前所處的位置，每個(gè)間隔背后都關(guān)聯(lián)著一個(gè)不可視區(qū)域，如果不可視區(qū)域在其關(guān)聯(lián)間隔的左側(cè)，則為該間隔加上L標(biāo)簽并稱之為L(zhǎng)間隔，R間隔可按類似的方式定義。如圖1所示，機(jī)器人在起點(diǎn)s可探測(cè)到L間隔A、B，R間隔C。需要指出的是，終點(diǎn)t可能在任意一個(gè)間隔背后的不可視區(qū)域內(nèi)。

在搜索過程中，隨著機(jī)器人的移動(dòng)，其可視區(qū)域內(nèi)的間隔會(huì)動(dòng)態(tài)地發(fā)生變化。這些變化可歸因于四類事件的發(fā)生，分別是消失、分裂、合并、共線。如圖2所示，當(dāng)機(jī)器人從s點(diǎn)走到a點(diǎn)時(shí)，間隔A分裂成D、E和F，間隔C消失；當(dāng)機(jī)器人從a點(diǎn)走到b點(diǎn)時(shí)，間隔D消失，間隔E和F合并為H，間隔I和J共線。

Fig.2 Dynamical changes of gaps when robot moves圖2 機(jī)器人移動(dòng)過程中間隔的動(dòng)態(tài)變化

當(dāng)可視區(qū)域內(nèi)間隔發(fā)生變化時(shí)，可能會(huì)有新的間隔出現(xiàn)，機(jī)器人可將新出現(xiàn)的間隔劃分為原生間隔和非原生間隔兩類。一個(gè)間隔，如果其背后的不可視區(qū)域?qū)C(jī)器人曾經(jīng)是可視的（如圖2（c）中的間隔K），則稱之為非原生間隔；否則，稱之為原生間隔。在本研究中，機(jī)器人是不關(guān)心非原生間隔的，因?yàn)榻K點(diǎn)t不可能在其中。

機(jī)器人在街道中被抽象成一點(diǎn)，并設(shè)定其在搜索過程中勻速前進(jìn)，其攜帶的感應(yīng)器可按順時(shí)針序報(bào)告可視區(qū)域內(nèi)發(fā)現(xiàn)的間隔，并為間隔加上L或R標(biāo)簽。機(jī)器人可朝向間隔移動(dòng)任意個(gè)單位步長(zhǎng)的距離，這里的單位步長(zhǎng)是一個(gè)較小的常量。機(jī)器人在移動(dòng)的過程中，不能測(cè)量與間隔之間的距離和角度，也不能測(cè)量間隔的尺寸，只能根據(jù)可視區(qū)域內(nèi)間隔的變化情況規(guī)劃搜索路徑。搜索過程中，機(jī)器人可與其他機(jī)器人實(shí)時(shí)通信，并可以識(shí)別終點(diǎn)t。

本研究關(guān)注使用兩個(gè)相同機(jī)器人從街道起點(diǎn)s出發(fā)，在預(yù)先不知道街道幾何信息的前提下，協(xié)作搜索街道終點(diǎn)t的算法。算法的效率使用競(jìng)爭(zhēng)比[21]來衡量，如下列公式所示：

其中，C表示競(jìng)爭(zhēng)比，P表示被搜索街道，supP表示P的所有可能情況構(gòu)成集合的上確界，和分別表示機(jī)器人RT1和RT2從起點(diǎn)s到終點(diǎn)t所走的路徑，SP表示從起點(diǎn)s到終點(diǎn)t的最短路徑。

3 幾何特性

本章將分析弱感知能力機(jī)器人街道搜索過程中的幾何特性，為下章算法的提出提供依據(jù)。

每個(gè)間隔都有一個(gè)與之關(guān)聯(lián)的凹頂點(diǎn)，這里凹頂點(diǎn)是指內(nèi)角和大于180°的P的頂點(diǎn)。如果間隔是L間隔，則其關(guān)聯(lián)凹頂點(diǎn)稱為L(zhǎng)關(guān)聯(lián)凹頂點(diǎn)，記作vl；R關(guān)聯(lián)凹頂點(diǎn)可按類似的方式定義，記作vr。

定義3（極限間隔）可視區(qū)域內(nèi)所有L間隔中，順時(shí)針序最后一個(gè)稱為極限L間隔，記作Glm，其關(guān)聯(lián)凹頂點(diǎn)記作vlm；可視區(qū)域內(nèi)所有R間隔中，順時(shí)針序第一個(gè)稱為極限R間隔，記作Grm，其關(guān)聯(lián)凹頂點(diǎn)記作vrm（如圖3（a）所示）。

引理1機(jī)器人搜索街道的過程中，如果終點(diǎn)t不在其可視區(qū)域內(nèi)，那么一定在極限L間隔或極限R間隔的背后。

證明假設(shè)相反情況，街道的終點(diǎn)t不在機(jī)器人可視區(qū)域內(nèi)，也不在極限L間隔或極限R間隔背后。不失一般性，設(shè)t在一個(gè)L間隔Gli（非極限L間隔）背后，如圖3（b）所示。在這個(gè)實(shí)例中，極限L間隔背后的邊界在R鏈上，其上至少存在一點(diǎn)與L鏈上的任意一點(diǎn)都不相互可視，這與街道的定義L和R相互弱可視矛盾。假設(shè)不成立，引理1得證?！?/p>

Fig.3 Most-advanced gap and its properties圖3 極限間隔及其特性

機(jī)器人在街道中搜索的時(shí)候，可能會(huì)遇到三種情況。第一種，終點(diǎn)t出現(xiàn)在機(jī)器人的可視區(qū)域中，毫無疑問，機(jī)器人這時(shí)直接走向終點(diǎn)t。第二種，可視區(qū)域內(nèi)兩個(gè)極限間隔Glm和Grm，只有其中一個(gè)存在，如圖4（a）所示，機(jī)器人位于s點(diǎn)，此時(shí)只有Grm存在，根據(jù)引理1，機(jī)器人在該情況下直接走向現(xiàn)存極限間隔的關(guān)聯(lián)凹頂點(diǎn)。第三種，可視區(qū)域內(nèi)兩個(gè)極限間隔Glm和Grm同時(shí)存在，如圖4（b）所示，機(jī)器人位于s點(diǎn)，由引理1可知，終點(diǎn)t可能在Glm后面，也可能在Grm后面，這種情況稱為漏斗，也是本研究要著重分析的一種情況。

在漏斗情況中，機(jī)器人會(huì)保持可視區(qū)域內(nèi)極限間隔的更新。從漏斗的起點(diǎn)出發(fā)，依次連接曾經(jīng)的極限L間隔的關(guān)聯(lián)凹頂點(diǎn)，可得到一條凸鏈，稱為該漏斗情況的L凸鏈；類似地，可以得到該漏斗情況的R凸鏈，如圖4（b）中虛線所示，s,vl1,vl2,vl3為L(zhǎng)凸鏈，s,vr1,vr2,vr3為R凸鏈。

Fig.4 Two searching situations圖4 兩種搜索情況

引理2在漏斗情況中，L凸鏈和R凸鏈上各存在一個(gè)關(guān)鍵點(diǎn)，使得當(dāng)機(jī)器人到達(dá)關(guān)鍵點(diǎn)時(shí)，當(dāng)前漏斗情況結(jié)束。

證明當(dāng)機(jī)器人到達(dá)L凸鏈或R凸鏈上的關(guān)鍵點(diǎn)時(shí)，漏斗情況會(huì)因如下兩種事件的發(fā)生而結(jié)束。第一種，極限L間隔和極限R間隔中的一個(gè)消失，如圖5（a）所示，消失的極限間隔的關(guān)聯(lián)凹頂點(diǎn)處的拐點(diǎn)射線與L凸鏈和R凸鏈分別交于a、b兩點(diǎn)，這兩點(diǎn)就是該漏斗情況中的關(guān)鍵點(diǎn)。第二種，極限L間隔和極限R間隔共線，此時(shí)原漏斗情況結(jié)束，一個(gè)新的漏斗情況出現(xiàn)，如圖5（b）所示，共線的兩個(gè)極限間隔的關(guān)聯(lián)凹頂點(diǎn)的公切線與L凸鏈和R凸鏈分別交于a、b兩點(diǎn)，這兩點(diǎn)就是原漏斗情況中的關(guān)鍵點(diǎn)?！?/p>

Fig.5 Two events for ending funnel situation圖5 漏斗情況結(jié)束的兩種關(guān)鍵事件

上述引理中提到的關(guān)鍵點(diǎn)稱為漏斗情況的關(guān)鍵點(diǎn)，由其定義可知，當(dāng)機(jī)器人到達(dá)一條凸鏈上的關(guān)鍵點(diǎn)時(shí)，它可確認(rèn)另一條凸鏈上的對(duì)應(yīng)關(guān)鍵點(diǎn)。

引理3搜索街道的最短路徑SP在漏斗情況中的那一段，要么在L凸鏈上，要么在R凸鏈上。

證明在一個(gè)漏斗情況中，顯然SP經(jīng)過其起點(diǎn)sf。從sf出發(fā)，由引理1可知，終點(diǎn)t在極限L間隔或極限R間隔背后，不失一般性，設(shè)其在極限L間隔背后，相反情況的分析與之類似。由上述假設(shè)可知，從sf到極限L間隔關(guān)聯(lián)凹頂點(diǎn)vlm的連線段必然屬于SP。接下來，隨著機(jī)器人的移動(dòng)，極限間隔會(huì)持續(xù)更新，下面分兩種情況討論：第一種情況，直至該漏斗情況結(jié)束，第一個(gè)極限L間隔背后沒有任何極限R間隔出現(xiàn)，如圖4（b）所示，隨著極限L間隔的更新，SP在該漏斗情況中依次經(jīng)過L凸鏈上每個(gè)極限L間隔的關(guān)聯(lián)凹頂點(diǎn)vl1、vl2、vl3。第二種情況，隨著極限間隔的更新，有一個(gè)極限R間隔出現(xiàn)在第一個(gè)極限L間隔背后，如圖5（b）所示，這個(gè)極限R間隔與當(dāng)前的極限L間隔共線，此時(shí)該漏斗情況結(jié)束，SP在該漏斗情況中依次經(jīng)過L凸鏈上每個(gè)極限L間隔的關(guān)聯(lián)凹頂點(diǎn)vl1、vl2。綜上，引理得證。□

定義4（精確鏈）漏斗情況的L凸鏈和R凸鏈中，SP覆蓋的那一條稱為該漏斗情況的精確鏈。

引理4在漏斗情況中，若機(jī)器人沿著L凸鏈或R凸鏈中的一條前進(jìn)，當(dāng)它到達(dá)關(guān)鍵點(diǎn)使得該漏斗情況結(jié)束時(shí)，它可以確認(rèn)哪一條是精確鏈。

證明機(jī)器人沿著凸鏈前進(jìn)，到達(dá)關(guān)鍵點(diǎn)使得漏斗情況結(jié)束，可分為如下兩種情況：第一種，極限L間隔和極限R間隔中的一個(gè)消失，如圖5（a）所示，顯然包含消失的極限間隔的關(guān)聯(lián)凹頂點(diǎn)的那條凸鏈不是精確鏈，與之對(duì)應(yīng)的另一條為精確鏈。第二種，極限L間隔和極限R間隔共線，如圖5（b）所示，顯然包含共線極限間隔關(guān)聯(lián)凹頂點(diǎn)的那條凸鏈為精確鏈。□

4 雙弱感知能力機(jī)器人在線協(xié)作街道搜索算法

本章將根據(jù)上一章提出的街道搜索中的幾何特性，給出使用兩個(gè)弱感知能力機(jī)器人在線協(xié)作搜索街道的算法。算法的具體步驟如算法1和算法2所示。

算法1雙弱感知能力機(jī)器人在線協(xié)作街道搜索算法

算法2漏斗情況搜索算法

算法1是雙弱感知能力機(jī)器人在線協(xié)作街道搜索算法的主程序，其目標(biāo)在于引導(dǎo)兩個(gè)機(jī)器人RT1和RT2從街道P的起點(diǎn)s出發(fā)，搜索并到達(dá)終點(diǎn)t。如前所述，在搜索的過程中，機(jī)器人可能會(huì)遇到三種不同的情況，分別為：終點(diǎn)t被發(fā)現(xiàn)、單極限間隔情況和漏斗情況。在終點(diǎn)t被發(fā)現(xiàn)以前，另外兩種情況可能會(huì)反復(fù)出現(xiàn)多次。當(dāng)單極限間隔情況發(fā)生時(shí)，RT1和RT2徑直行至該極限間隔的關(guān)聯(lián)凹頂點(diǎn)，到達(dá)該凹頂點(diǎn)時(shí)，開始一個(gè)新的情況。當(dāng)漏斗情況發(fā)生時(shí)，調(diào)用算法2專門處理這種情況。直到終點(diǎn)t被發(fā)現(xiàn)時(shí)，RT1和RT2徑直行至終點(diǎn)t。

算法2是雙弱感知能力機(jī)器人在線協(xié)作街道搜索算法的子程序，其目標(biāo)在于處理搜索過程中較為復(fù)雜的漏斗情況。在漏斗情況中，由引理1可知，終點(diǎn)t要么在極限L間隔背后，要么在極限R間隔背后，但機(jī)器人不知道終點(diǎn)t具體在哪一個(gè)極限間隔背后。算法2讓RT1和RT2分別沿L凸鏈和R凸鏈前進(jìn)，并保持各自可視區(qū)域內(nèi)極限間隔及其關(guān)聯(lián)凹頂點(diǎn)的更新，直至某個(gè)機(jī)器人到達(dá)漏斗情況的關(guān)鍵點(diǎn)。由引理2可知，此時(shí)漏斗情況結(jié)束且關(guān)鍵點(diǎn)可被確認(rèn)，再由引理3和引理4可知，此時(shí)精確鏈也可被確認(rèn)。兩個(gè)機(jī)器人通過實(shí)時(shí)通信共享信息，共同行至精確鏈上的關(guān)鍵點(diǎn)。至此，兩個(gè)機(jī)器人將面對(duì)一個(gè)新的情況，或者是單極限間隔情況，或者是漏斗情況，或者是終點(diǎn)t被發(fā)現(xiàn)。

圖6給出了一個(gè)上述算法引導(dǎo)兩個(gè)弱感知能力機(jī)器人完成街道搜索的實(shí)例，圖中虛線表示漏斗情況中的凸鏈，箭頭表示機(jī)器人的行進(jìn)路線。兩個(gè)機(jī)器人RT1和RT2從起點(diǎn)s出發(fā)，遇到第一個(gè)漏斗情況，根據(jù)算法2，RT1和RT2分別沿著該漏斗情況的L凸鏈和R凸鏈前進(jìn)。RT1行至k點(diǎn)時(shí)，可視區(qū)域內(nèi)極限R間隔更新，其關(guān)聯(lián)凹頂點(diǎn)更新為vr2，RT1行至vl1點(diǎn)時(shí)，可視區(qū)域內(nèi)極限L間隔更新，其關(guān)聯(lián)凹頂點(diǎn)更新為vl2，類似地，RT2在行進(jìn)過程中也保持可視區(qū)域內(nèi)極限間隔及其關(guān)聯(lián)凹頂點(diǎn)的更新。當(dāng)RT2行至d點(diǎn)時(shí)，極限L間隔消失，漏斗情況結(jié)束，RT2停在d點(diǎn)，確認(rèn)該漏斗情況的關(guān)鍵點(diǎn)為d和vl2，精確鏈為R凸鏈。RT2將上述信息實(shí)時(shí)傳遞給RT1，RT1收到信息停在原地（c點(diǎn)），轉(zhuǎn)而走向d點(diǎn)。兩個(gè)機(jī)器人在d點(diǎn)會(huì)和，面對(duì)一個(gè)單極限間隔情況，一起從d點(diǎn)行至vr2點(diǎn)。兩個(gè)機(jī)器人再次面對(duì)一個(gè)單極限間隔情況，一起從vr2點(diǎn)行至vr3點(diǎn)。此時(shí)，兩個(gè)機(jī)器人遇到第二個(gè)漏斗情況，RT1和RT2分別沿著該漏斗情況的L凸鏈和R凸鏈前進(jìn)。當(dāng)RT1行至e點(diǎn)時(shí)，極限L間隔和極限R間隔共線，漏斗情況結(jié)束，RT1停在e點(diǎn)，確認(rèn)該漏斗情況的關(guān)鍵點(diǎn)為e和vr4，精確鏈為R凸鏈。RT1將上述信息實(shí)時(shí)傳遞給RT2，RT2收到信息停在原地（f點(diǎn)）。兩個(gè)機(jī)器人行至vr4點(diǎn)會(huì)和，遇到第三個(gè)漏斗情況，與第一個(gè)漏斗情況類似，RT2行至i點(diǎn)時(shí)該漏斗情況結(jié)束。兩個(gè)機(jī)器人在i點(diǎn)會(huì)和，面對(duì)一個(gè)單極限間隔情況，一起從i點(diǎn)行至vr5點(diǎn)。兩個(gè)機(jī)器人再次面對(duì)一個(gè)單極限間隔情況，一起從vr5點(diǎn)行至vr6點(diǎn)。此時(shí)，終點(diǎn)t被發(fā)現(xiàn)，兩個(gè)機(jī)器人一起行至終點(diǎn)t。

Fig.6 Instance of searching in street圖6 搜索街道的一個(gè)實(shí)例

5 算法效率分析

本章將通過競(jìng)爭(zhēng)比分析算法的效率，并通過給出相匹配的競(jìng)爭(zhēng)比下界證明算法的最優(yōu)性。

5.1 算法的競(jìng)爭(zhēng)比分析

由前文的分析可知，機(jī)器人搜索街道的過程中，只有漏斗情況會(huì)使機(jī)器人走出冗余路徑，進(jìn)而影響算法的效率（競(jìng)爭(zhēng)比）。因此，本節(jié)將分析的重點(diǎn)放在漏斗情況，為了準(zhǔn)確界定漏斗情況的范圍，本研究將從漏斗情況起點(diǎn)出發(fā)，到漏斗情況精確鏈上的關(guān)鍵點(diǎn)結(jié)束，兩個(gè)機(jī)器人所走路徑圍成的區(qū)域稱為漏斗多邊形。如圖6所示，凸鏈s,vl1,c，線段和凸鏈s,vr1,d圍成的區(qū)域?yàn)槁┒范噙呅巍?/p>

定理1雙弱感知能力機(jī)器人在線協(xié)作街道搜索算法的競(jìng)爭(zhēng)比為3。

證明如前所述，在街道搜索的過程中，機(jī)器人將面對(duì)三種情況，分別為終點(diǎn)t可見、單極限間隔情況和漏斗情況。在第一種情況中，本研究所提出的算法將引導(dǎo)機(jī)器人徑直行至終點(diǎn)t；在第二種情況中，本研究所提出的算法將引導(dǎo)機(jī)器人徑直行至極限間隔的關(guān)聯(lián)凹頂點(diǎn)。顯然，在這兩種情況中，機(jī)器人所走的路徑是最短路徑，算法的競(jìng)爭(zhēng)比為1。

下面，分析本研究所提出的算法在漏斗情況中的表現(xiàn)。不失一般性，設(shè)精確鏈為漏斗情況的L凸鏈，相反情況的分析與之類似。為便于分析，給出一個(gè)滿足上述假設(shè)的漏斗多邊形實(shí)例，如圖7所示，其中sf為漏斗情況起點(diǎn)，a為精確鏈上的關(guān)鍵點(diǎn)，設(shè)A=凸鏈sf,vl1,vl2,vl3,a，B=凸鏈由算法2可知，RT1在該漏斗情況中所走路徑為A，RT2在該漏斗情況中所走路徑為B+D。結(jié)合兩個(gè)機(jī)器人到達(dá)各自所在凸鏈上的關(guān)鍵點(diǎn)的先后情況，可分如下三種子情況來討論：

Fig.7 Instance of funnel polygon圖7 漏斗多邊形的一個(gè)實(shí)例

（1）RT1先到達(dá)L凸鏈上的關(guān)鍵點(diǎn)

在該情況下，RT1先到達(dá)a點(diǎn)，漏斗情況結(jié)束，此時(shí)RT2到達(dá)c點(diǎn)，然后RT1在a點(diǎn)等候，直至RT2經(jīng)D到達(dá)a點(diǎn)與之會(huì)合。由兩個(gè)機(jī)器人速度相同且勻速前進(jìn)可知，A=B。

（2）RT2先到達(dá)R凸鏈上的關(guān)鍵點(diǎn)

在該情況下，RT2先到達(dá)c點(diǎn)，漏斗情況結(jié)束，此時(shí)RT1尚未到達(dá)a點(diǎn)，然后RT1繼續(xù)沿L凸鏈前進(jìn)直至到達(dá)a點(diǎn)，RT2經(jīng)D到達(dá)a點(diǎn)，先到的機(jī)器人在a點(diǎn)等候，直至與另一個(gè)機(jī)器人在a點(diǎn)會(huì)和。由兩個(gè)機(jī)器人速度相同且勻速前進(jìn)可知，A＞B。

（3）RT1和RT2同時(shí)到達(dá)各自凸鏈上的關(guān)鍵點(diǎn)

在該情況下，RT1到達(dá)a點(diǎn)，同時(shí)RT2到達(dá)c點(diǎn)，漏斗情況結(jié)束。后續(xù)與子情況（1）一致，因此A=B。

上述三種子情況覆蓋了精確鏈為L(zhǎng)凸鏈的所有漏斗情況，由此可知，在該設(shè)定下，A≥B。

在△asf c中，D＜A'+B'，又A'＜A，B'＜B，可知D＜A+B。接下來，根據(jù)本研究第2章模型描述中所述式（1）計(jì)算競(jìng)爭(zhēng)比。

綜上，在街道搜索過程中，機(jī)器人可能面對(duì)的三種情況里，都滿足競(jìng)爭(zhēng)比C＜3，因此，定理得證。□

5.2 競(jìng)爭(zhēng)比下界分析

為證明本研究所提出算法的最優(yōu)性，現(xiàn)給出競(jìng)爭(zhēng)比下界的分析。

定理2任意使用兩個(gè)弱感知能力機(jī)器人在線協(xié)作搜索街道的確定性算法，其競(jìng)爭(zhēng)比下界為3。

證明如前所述，在街道搜索的過程中，機(jī)器人將面對(duì)三種情況，分別為終點(diǎn)t被發(fā)現(xiàn)、單極限間隔情況和漏斗情況。在前兩種情況中，任意確定性算法都會(huì)引導(dǎo)機(jī)器人走最短路徑，因此不會(huì)對(duì)競(jìng)爭(zhēng)比產(chǎn)生影響。在第三種情況中，為了限制住競(jìng)爭(zhēng)比的上界，任意確定性算法都會(huì)引導(dǎo)兩個(gè)機(jī)器人分別向兩個(gè)極限間隔的關(guān)聯(lián)凹頂點(diǎn)前進(jìn)，當(dāng)一個(gè)機(jī)器人到達(dá)關(guān)鍵點(diǎn)使得漏斗情況結(jié)束時(shí)，兩個(gè)機(jī)器人會(huì)再次會(huì)和以面對(duì)后續(xù)情況，也只有這種情況會(huì)影響競(jìng)爭(zhēng)比。由定理1證明中漏斗情況的分析可知，在精確鏈為漏斗情況的L凸鏈的前提下，A≥B，精確鏈為漏斗情況的R凸鏈的情況的分析與之類似。再結(jié)合競(jìng)爭(zhēng)比計(jì)算公式，可知圖7中的D為決定競(jìng)爭(zhēng)比的關(guān)鍵因素，當(dāng)B=A，且D取最大值時(shí)，競(jìng)爭(zhēng)比取得最大值。

如圖7所示，在△asf c中，根據(jù)余弦定理可知，這是一個(gè)關(guān)于β的增函數(shù)，當(dāng)β=π 時(shí)取得最大值，Dmax=A'+B'。

根據(jù)上述分析，現(xiàn)構(gòu)建一個(gè)特殊的漏斗情況，即L凸鏈與R凸鏈幾乎共線，可以想象該情況是通過增加β，拉伸D，壓平圖7所示的漏斗情況所得。此時(shí)，A趨近于A'，B趨近于B'，再設(shè)置該特殊情況下B=A。由競(jìng)爭(zhēng)比計(jì)算公式可知，該特殊情況下競(jìng)爭(zhēng)比C=(B+D)/A=3。

綜上，任意使用兩個(gè)弱感知能力機(jī)器人在線協(xié)作搜索街道的確定性算法在上述構(gòu)建的特殊漏斗情況中，都不可能取得小于3的競(jìng)爭(zhēng)比，因此，定理得證。

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

本研究分析了使用兩個(gè)弱感知能力機(jī)器人在線協(xié)作搜索街道的問題，通過構(gòu)建模型并分析幾何特征，給出了競(jìng)爭(zhēng)比為3的在線協(xié)作搜索算法，并通過給出相匹配的競(jìng)爭(zhēng)比下界，證明了算法的最優(yōu)性。本研究第3章給出的幾何性質(zhì)同樣適用于街道模型中其他機(jī)器人搜索、探索問題的分析。本研究將搜索場(chǎng)景限制在街道模型，下一步將在更一般的多邊形場(chǎng)景中研究使用弱感知能力機(jī)器人在線協(xié)作完成搜索任務(wù)的高效算法；此外，將在模型中加入機(jī)器人視距的限制條件，研究相應(yīng)的在線協(xié)作搜索算法。