计算机科学与探索

作者：魏琦，林韦达，吴彤，任永功

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

关键词：计算几何,在线协作搜索算法,竞争分析,机器人,弱感知

在未知环境中搜索一个目标，是机器人的基本任务场景之一，在现实中有着广泛的应用。相关问题在计算几何学科和机器人学科的研究中得到了广泛的关注。研究了一个双弱感知能力机器人在线协作搜索街道的问题。街道被定义为具有LR可视性的简单多边形P ，两个可相互通信的弱感知能力机器人从街道起点s出发，在预先不知道街道几何信息的前提下，协作完成街道终点t 的搜索。弱感知能力机器人携带的感应器仅能探测可视区域内街道边界的不连续情况，除此之外不能获取任何其他几何信息，如距离和角度。弱感知能力机器人虽然感知能力有限，却具有性价比高、面对不确定因素时可靠性强等优点。基于在线搜索模型的几何特征，提出了竞争比为3的在线协作搜索算法，并通过给出相匹配的竞争比下界，证明了算法的最优性。

来源：2020年第9期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2020年第9期