双弱感知能力机器人在线协作街道搜索算法*

魏 琦，林韦达，吴 彤，任永功

辽宁师范大学计算机与信息技术学院，辽宁大连 116081

1 引言

未知区域中的目标搜索是计算几何学和机器人学中的热点研究问题[1-3]，在机器人搜索、探索和监控等领域有着广泛的应用[4-5]。近年来，国内外众多学者针对相关问题展开研究，并取得了一定成果。

本研究将机器人搜索区域抽象为街道模型[6]，即具有LR（left chain and right chain）可视性的简单多边形。Klein[6]最先提出街道模型，并提出机器人从街道起点s出发，在线搜索街道终点t的街道搜索问题。该模型可视作对街道、河道、赛道场景的抽象，机器人从起点出发，在线搜索并到达终点，可看到场景内的所有区域，进而完成勘察、搜索、探索等任务。针对街道搜索问题，Klein[6]给出了竞争比为5.72的在线算法，并证明算法的竞争比下界为。自此，街道模型的相关问题获得了学术界的广泛关注。Tseng等[7]提出了在简单多边形边界上寻找所有可能作为起点和终点构成街道的点对的算法。Ghosh和Saluja[8]提出了搜索路径转折次数最少的街道搜索算法。针对Klein[6]提出的竞争比为5.72的街道搜索算法，多位学者先后提出新的算法，降低竞争比，提升算法效率。最终，由Icking等[9]给出了与竞争比下界相匹配的最优算法。

上述街道模型的研究中，使用的机器人都具有较强的感知能力，其携带的感应器不仅可以观察可视区域内的场景，还可以测量距离和角度，使得机器人在行进的过程中可以根据感应器收集到的信息绘制出街道的局部地图。与感知能力较强的感应器相对应的，一些研究人员将关注点放在简单感应器上，因为其具有很多优点，如价格低廉、抗干扰能力强、适应性强等。Tovar等[10]最先提出弱感知模型，机器人携带的感应器仅能探测可视区域内搜索区域边界的不连续情况，借助数据结构GNT（gap navigation tree），这些搜索区域边界的不连续情况可被保存和更新，用于制定机器人的搜索策略。Lopez-Padilla等[11]在弱感知模型下研究了使用盘式机器人在简单多边形区域中搜索目标点的问题。Tabatabaei等[12]在弱感知模型下研究了街道搜索问题，受双倍策略[13]启发，提出了竞争比为11的在线搜索算法。Wei等[14]又针对此问题提出了竞争比为9的算法，并通过给出相匹配的竞争比下界证明了算法的最优性，同时还去掉了机器人需要携带位置标记装置及使用数据结构SGNT（street gap navigation tree）的限制。

与单机器人在未知环境下搜索目标相比，使用多机器人协作完成目标搜索具有并行处理、容错率高、信息冗余等优点[15-17]，不仅有助于克服传感器和环境的不确定性，而且还扩展了单个机器人的搜索功能。Czyzowicz等[18]研究了使用多个机器人在一条直线上搜索目标的问题，并给出了竞争比为2的在线搜索算法。Burgard等[19]、Ortolf等[20]研究了使用多个机器人探索未知区域的问题。

在上述研究基础上，本研究提出双弱感知能力机器人在线协作街道搜索问题，研究使用两个弱感知能力机器人从街道起点s出发，在预先不知道街道几何信息的前提下，协作搜索街道终点t。本研究提出了竞争比为3的在线协作搜索算法，并通过给出相匹配的竞争比下界，证明了算法的最优性。

2 模型描述

本章将从搜索场景、感应器、机器人动作初始设定等方面给出双弱感知能力机器人在线协作街道搜索模型的描述。

设P为一简单多边形，bd为P的边界。设p、q为P内部的两点，如果线段完全在P的内部，则称p、q两点相互可视。对于P内部的两个点集A、B，若A中任意一点p，B中都至少存在一点q与之相互可视，反之亦然，则称集合A与B相互弱可视。

定义1（街道）设P为一简单多边形，其边界上有两个不相同的点s和t。设L和R分别表示P上从s到t的两条边界链。如果L和R相互弱可视，则称(P,s,t)为街道，其中s为起点，t为终点。

设点集Vis(a)={q∈P|a与q相互可视}表示点a(a∈P)在P内的可视区域。如图1所示，为一街道P及其起点s的可视区域Vis(s)。两个机器人从起点s出发，协作搜索并到达终点t，本研究的目标即为两个机器人规划高效的协作搜索路径。

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（间隔）设Vis(a)为机器人在街道P内a点的可视区域，Vis(a)边界上的构造部分（非P的边界）称为间隔。

机器人携带有视觉感应器，但感知能力较弱，仅能探测可视区域内街道边界的不连续情况（间隔），并可为间隔加上L或R标签。相对于机器人当前所处的位置，每个间隔背后都关联着一个不可视区域，如果不可视区域在其关联间隔的左侧，则为该间隔加上L标签并称之为L间隔，R间隔可按类似的方式定义。如图1所示，机器人在起点s可探测到L间隔A、B，R间隔C。需要指出的是，终点t可能在任意一个间隔背后的不可视区域内。

在搜索过程中，随着机器人的移动，其可视区域内的间隔会动态地发生变化。这些变化可归因于四类事件的发生，分别是消失、分裂、合并、共线。如图2所示，当机器人从s点走到a点时，间隔A分裂成D、E和F，间隔C消失；当机器人从a点走到b点时，间隔D消失，间隔E和F合并为H，间隔I和J共线。

Fig.2 Dynamical changes of gaps when robot moves图2 机器人移动过程中间隔的动态变化

当可视区域内间隔发生变化时，可能会有新的间隔出现，机器人可将新出现的间隔划分为原生间隔和非原生间隔两类。一个间隔，如果其背后的不可视区域对机器人曾经是可视的（如图2（c）中的间隔K），则称之为非原生间隔；否则，称之为原生间隔。在本研究中，机器人是不关心非原生间隔的，因为终点t不可能在其中。

机器人在街道中被抽象成一点，并设定其在搜索过程中匀速前进，其携带的感应器可按顺时针序报告可视区域内发现的间隔，并为间隔加上L或R标签。机器人可朝向间隔移动任意个单位步长的距离，这里的单位步长是一个较小的常量。机器人在移动的过程中，不能测量与间隔之间的距离和角度，也不能测量间隔的尺寸，只能根据可视区域内间隔的变化情况规划搜索路径。搜索过程中，机器人可与其他机器人实时通信，并可以识别终点t。

本研究关注使用两个相同机器人从街道起点s出发，在预先不知道街道几何信息的前提下，协作搜索街道终点t的算法。算法的效率使用竞争比[21]来衡量，如下列公式所示：

其中，C表示竞争比，P表示被搜索街道，supP表示P的所有可能情况构成集合的上确界，和分别表示机器人RT1和RT2从起点s到终点t所走的路径，SP表示从起点s到终点t的最短路径。

3 几何特性

本章将分析弱感知能力机器人街道搜索过程中的几何特性，为下章算法的提出提供依据。

每个间隔都有一个与之关联的凹顶点，这里凹顶点是指内角和大于180°的P的顶点。如果间隔是L间隔，则其关联凹顶点称为L关联凹顶点，记作vl；R关联凹顶点可按类似的方式定义，记作vr。

定义3（极限间隔）可视区域内所有L间隔中，顺时针序最后一个称为极限L间隔，记作Glm，其关联凹顶点记作vlm；可视区域内所有R间隔中，顺时针序第一个称为极限R间隔，记作Grm，其关联凹顶点记作vrm（如图3（a）所示）。

引理1机器人搜索街道的过程中，如果终点t不在其可视区域内，那么一定在极限L间隔或极限R间隔的背后。

证明假设相反情况，街道的终点t不在机器人可视区域内，也不在极限L间隔或极限R间隔背后。不失一般性，设t在一个L间隔Gli（非极限L间隔）背后，如图3（b）所示。在这个实例中，极限L间隔背后的边界在R链上，其上至少存在一点与L链上的任意一点都不相互可视，这与街道的定义L和R相互弱可视矛盾。假设不成立，引理1得证。□

Fig.3 Most-advanced gap and its properties图3 极限间隔及其特性

机器人在街道中搜索的时候，可能会遇到三种情况。第一种，终点t出现在机器人的可视区域中，毫无疑问，机器人这时直接走向终点t。第二种，可视区域内两个极限间隔Glm和Grm，只有其中一个存在，如图4（a）所示，机器人位于s点，此时只有Grm存在，根据引理1，机器人在该情况下直接走向现存极限间隔的关联凹顶点。第三种，可视区域内两个极限间隔Glm和Grm同时存在，如图4（b）所示，机器人位于s点，由引理1可知，终点t可能在Glm后面，也可能在Grm后面，这种情况称为漏斗，也是本研究要着重分析的一种情况。

在漏斗情况中，机器人会保持可视区域内极限间隔的更新。从漏斗的起点出发，依次连接曾经的极限L间隔的关联凹顶点，可得到一条凸链，称为该漏斗情况的L凸链；类似地，可以得到该漏斗情况的R凸链，如图4（b）中虚线所示，s,vl1,vl2,vl3为L凸链，s,vr1,vr2,vr3为R凸链。

Fig.4 Two searching situations图4 两种搜索情况

引理2在漏斗情况中，L凸链和R凸链上各存在一个关键点，使得当机器人到达关键点时，当前漏斗情况结束。

证明当机器人到达L凸链或R凸链上的关键点时，漏斗情况会因如下两种事件的发生而结束。第一种，极限L间隔和极限R间隔中的一个消失，如图5（a）所示，消失的极限间隔的关联凹顶点处的拐点射线与L凸链和R凸链分别交于a、b两点，这两点就是该漏斗情况中的关键点。第二种，极限L间隔和极限R间隔共线，此时原漏斗情况结束，一个新的漏斗情况出现，如图5（b）所示，共线的两个极限间隔的关联凹顶点的公切线与L凸链和R凸链分别交于a、b两点，这两点就是原漏斗情况中的关键点。□

Fig.5 Two events for ending funnel situation图5 漏斗情况结束的两种关键事件

上述引理中提到的关键点称为漏斗情况的关键点，由其定义可知，当机器人到达一条凸链上的关键点时，它可确认另一条凸链上的对应关键点。

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

证明在一个漏斗情况中，显然SP经过其起点sf。从sf出发，由引理1可知，终点t在极限L间隔或极限R间隔背后，不失一般性，设其在极限L间隔背后，相反情况的分析与之类似。由上述假设可知，从sf到极限L间隔关联凹顶点vlm的连线段必然属于SP。接下来，随着机器人的移动，极限间隔会持续更新，下面分两种情况讨论：第一种情况，直至该漏斗情况结束，第一个极限L间隔背后没有任何极限R间隔出现，如图4（b）所示，随着极限L间隔的更新，SP在该漏斗情况中依次经过L凸链上每个极限L间隔的关联凹顶点vl1、vl2、vl3。第二种情况，随着极限间隔的更新，有一个极限R间隔出现在第一个极限L间隔背后，如图5（b）所示，这个极限R间隔与当前的极限L间隔共线，此时该漏斗情况结束，SP在该漏斗情况中依次经过L凸链上每个极限L间隔的关联凹顶点vl1、vl2。综上，引理得证。□

定义4（精确链）漏斗情况的L凸链和R凸链中，SP覆盖的那一条称为该漏斗情况的精确链。

引理4在漏斗情况中，若机器人沿着L凸链或R凸链中的一条前进，当它到达关键点使得该漏斗情况结束时，它可以确认哪一条是精确链。

证明机器人沿着凸链前进，到达关键点使得漏斗情况结束，可分为如下两种情况：第一种，极限L间隔和极限R间隔中的一个消失，如图5（a）所示，显然包含消失的极限间隔的关联凹顶点的那条凸链不是精确链，与之对应的另一条为精确链。第二种，极限L间隔和极限R间隔共线，如图5（b）所示，显然包含共线极限间隔关联凹顶点的那条凸链为精确链。□

4 双弱感知能力机器人在线协作街道搜索算法

本章将根据上一章提出的街道搜索中的几何特性，给出使用两个弱感知能力机器人在线协作搜索街道的算法。算法的具体步骤如算法1和算法2所示。

算法1双弱感知能力机器人在线协作街道搜索算法

算法2漏斗情况搜索算法

算法1是双弱感知能力机器人在线协作街道搜索算法的主程序，其目标在于引导两个机器人RT1和RT2从街道P的起点s出发，搜索并到达终点t。如前所述，在搜索的过程中，机器人可能会遇到三种不同的情况，分别为：终点t被发现、单极限间隔情况和漏斗情况。在终点t被发现以前，另外两种情况可能会反复出现多次。当单极限间隔情况发生时，RT1和RT2径直行至该极限间隔的关联凹顶点，到达该凹顶点时，开始一个新的情况。当漏斗情况发生时，调用算法2专门处理这种情况。直到终点t被发现时，RT1和RT2径直行至终点t。

算法2是双弱感知能力机器人在线协作街道搜索算法的子程序，其目标在于处理搜索过程中较为复杂的漏斗情况。在漏斗情况中，由引理1可知，终点t要么在极限L间隔背后，要么在极限R间隔背后，但机器人不知道终点t具体在哪一个极限间隔背后。算法2让RT1和RT2分别沿L凸链和R凸链前进，并保持各自可视区域内极限间隔及其关联凹顶点的更新，直至某个机器人到达漏斗情况的关键点。由引理2可知，此时漏斗情况结束且关键点可被确认，再由引理3和引理4可知，此时精确链也可被确认。两个机器人通过实时通信共享信息，共同行至精确链上的关键点。至此，两个机器人将面对一个新的情况，或者是单极限间隔情况，或者是漏斗情况，或者是终点t被发现。

图6给出了一个上述算法引导两个弱感知能力机器人完成街道搜索的实例，图中虚线表示漏斗情况中的凸链，箭头表示机器人的行进路线。两个机器人RT1和RT2从起点s出发，遇到第一个漏斗情况，根据算法2，RT1和RT2分别沿着该漏斗情况的L凸链和R凸链前进。RT1行至k点时，可视区域内极限R间隔更新，其关联凹顶点更新为vr2，RT1行至vl1点时，可视区域内极限L间隔更新，其关联凹顶点更新为vl2，类似地，RT2在行进过程中也保持可视区域内极限间隔及其关联凹顶点的更新。当RT2行至d点时，极限L间隔消失，漏斗情况结束，RT2停在d点，确认该漏斗情况的关键点为d和vl2，精确链为R凸链。RT2将上述信息实时传递给RT1，RT1收到信息停在原地（c点），转而走向d点。两个机器人在d点会和，面对一个单极限间隔情况，一起从d点行至vr2点。两个机器人再次面对一个单极限间隔情况，一起从vr2点行至vr3点。此时，两个机器人遇到第二个漏斗情况，RT1和RT2分别沿着该漏斗情况的L凸链和R凸链前进。当RT1行至e点时，极限L间隔和极限R间隔共线，漏斗情况结束，RT1停在e点，确认该漏斗情况的关键点为e和vr4，精确链为R凸链。RT1将上述信息实时传递给RT2，RT2收到信息停在原地（f点）。两个机器人行至vr4点会和，遇到第三个漏斗情况，与第一个漏斗情况类似，RT2行至i点时该漏斗情况结束。两个机器人在i点会和，面对一个单极限间隔情况，一起从i点行至vr5点。两个机器人再次面对一个单极限间隔情况，一起从vr5点行至vr6点。此时，终点t被发现，两个机器人一起行至终点t。

Fig.6 Instance of searching in street图6 搜索街道的一个实例

5 算法效率分析

本章将通过竞争比分析算法的效率，并通过给出相匹配的竞争比下界证明算法的最优性。

5.1 算法的竞争比分析

由前文的分析可知，机器人搜索街道的过程中，只有漏斗情况会使机器人走出冗余路径，进而影响算法的效率（竞争比）。因此，本节将分析的重点放在漏斗情况，为了准确界定漏斗情况的范围，本研究将从漏斗情况起点出发，到漏斗情况精确链上的关键点结束，两个机器人所走路径围成的区域称为漏斗多边形。如图6所示，凸链s,vl1,c，线段和凸链s,vr1,d围成的区域为漏斗多边形。

定理1双弱感知能力机器人在线协作街道搜索算法的竞争比为3。

证明如前所述，在街道搜索的过程中，机器人将面对三种情况，分别为终点t可见、单极限间隔情况和漏斗情况。在第一种情况中，本研究所提出的算法将引导机器人径直行至终点t；在第二种情况中，本研究所提出的算法将引导机器人径直行至极限间隔的关联凹顶点。显然，在这两种情况中，机器人所走的路径是最短路径，算法的竞争比为1。

下面，分析本研究所提出的算法在漏斗情况中的表现。不失一般性，设精确链为漏斗情况的L凸链，相反情况的分析与之类似。为便于分析，给出一个满足上述假设的漏斗多边形实例，如图7所示，其中sf为漏斗情况起点，a为精确链上的关键点，设A=凸链sf,vl1,vl2,vl3,a，B=凸链由算法2可知，RT1在该漏斗情况中所走路径为A，RT2在该漏斗情况中所走路径为B+D。结合两个机器人到达各自所在凸链上的关键点的先后情况，可分如下三种子情况来讨论：

Fig.7 Instance of funnel polygon图7 漏斗多边形的一个实例

（1）RT1先到达L凸链上的关键点

在该情况下，RT1先到达a点，漏斗情况结束，此时RT2到达c点，然后RT1在a点等候，直至RT2经D到达a点与之会合。由两个机器人速度相同且匀速前进可知，A=B。

（2）RT2先到达R凸链上的关键点

在该情况下，RT2先到达c点，漏斗情况结束，此时RT1尚未到达a点，然后RT1继续沿L凸链前进直至到达a点，RT2经D到达a点，先到的机器人在a点等候，直至与另一个机器人在a点会和。由两个机器人速度相同且匀速前进可知，A＞B。

（3）RT1和RT2同时到达各自凸链上的关键点

在该情况下，RT1到达a点，同时RT2到达c点，漏斗情况结束。后续与子情况（1）一致，因此A=B。

上述三种子情况覆盖了精确链为L凸链的所有漏斗情况，由此可知，在该设定下，A≥B。

在△asf c中，D＜A'+B'，又A'＜A，B'＜B，可知D＜A+B。接下来，根据本研究第2章模型描述中所述式（1）计算竞争比。

综上，在街道搜索过程中，机器人可能面对的三种情况里，都满足竞争比C＜3，因此，定理得证。□

5.2 竞争比下界分析

为证明本研究所提出算法的最优性，现给出竞争比下界的分析。

定理2任意使用两个弱感知能力机器人在线协作搜索街道的确定性算法，其竞争比下界为3。

证明如前所述，在街道搜索的过程中，机器人将面对三种情况，分别为终点t被发现、单极限间隔情况和漏斗情况。在前两种情况中，任意确定性算法都会引导机器人走最短路径，因此不会对竞争比产生影响。在第三种情况中，为了限制住竞争比的上界，任意确定性算法都会引导两个机器人分别向两个极限间隔的关联凹顶点前进，当一个机器人到达关键点使得漏斗情况结束时，两个机器人会再次会和以面对后续情况，也只有这种情况会影响竞争比。由定理1证明中漏斗情况的分析可知，在精确链为漏斗情况的L凸链的前提下，A≥B，精确链为漏斗情况的R凸链的情况的分析与之类似。再结合竞争比计算公式，可知图7中的D为决定竞争比的关键因素，当B=A，且D取最大值时，竞争比取得最大值。

如图7所示，在△asf c中，根据余弦定理可知，这是一个关于β的增函数，当β=π 时取得最大值，Dmax=A'+B'。

根据上述分析，现构建一个特殊的漏斗情况，即L凸链与R凸链几乎共线，可以想象该情况是通过增加β，拉伸D，压平图7所示的漏斗情况所得。此时，A趋近于A'，B趋近于B'，再设置该特殊情况下B=A。由竞争比计算公式可知，该特殊情况下竞争比C=(B+D)/A=3。

综上，任意使用两个弱感知能力机器人在线协作搜索街道的确定性算法在上述构建的特殊漏斗情况中，都不可能取得小于3的竞争比，因此，定理得证。

6 结束语

本研究分析了使用两个弱感知能力机器人在线协作搜索街道的问题，通过构建模型并分析几何特征，给出了竞争比为3的在线协作搜索算法，并通过给出相匹配的竞争比下界，证明了算法的最优性。本研究第3章给出的几何性质同样适用于街道模型中其他机器人搜索、探索问题的分析。本研究将搜索场景限制在街道模型，下一步将在更一般的多边形场景中研究使用弱感知能力机器人在线协作完成搜索任务的高效算法；此外，将在模型中加入机器人视距的限制条件，研究相应的在线协作搜索算法。