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

辽宁师范大学计算机与信息技术学院，辽宁大连 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]给出了与竞争比下界相匹配的最优算法。

上述街道模型的研究中，使用的机器人都具有较强的感知能力，其携带的感应器不仅可以观察可视区域内的场景，还可以测量距离和角度，使得机器人在行进的过程中可以根据感应器收集到的信息绘制出街道的局部地图。与感知能力较强的感应器相对应的，一些研究人员将关注点放在简单感应器上，因为其具有很多优点，如价格低廉、抗干扰能力强、适应性强等。……