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

摘要：

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

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

所属期刊栏目：14

分类号：TP301(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos. 61702242, 61976109 国家自然科学基金;the Doctoral Scien-tific Research Foundation of Liaoning Province under Grant Nos. 2019-BS-153, 2019-BS-014 辽宁省博士科研启动基金;the Stu-dent Research Training Program of Liaoning Normal University under Grant No. CX201902026 辽宁师范大学指导本科生科研训练项目

在线出版日期：2020-09-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1571-1579