障碍物和视距限制下的多边形区域在线探索算法研究

Online exploration of a polygonal terrain is a hot research issue in computational geometry and robotics, which is widely applied to many fields such as exploration, search, and monitoring of robots. Methods of computational geometry and graph theory are based upon in this research, and the explored terrain is a general polygon or a rectilinear polygon. This research designs algorithms for a robot equipped with a vision system to explore the terrain. The robot has no knowledge of this terrain in advance. In view of the actual situation of exploration, constraints such as obstacles and visible range of a robot are added to study the polygonal terrain exploration via a robot in three different cases: obstacles in the area without range of visibility; no obstacles in the area with range of visibility; obstacles in the area with range of visibility. In the study of each case, modeling is made first by integrating the type of the polygon and the specific constraints to analyze the geometrical properties. And then, an exploration algorithm is designed according to the model properties, and competitive analysis is adopted to analyze the efficiency of the algorithm. Finally, a special submodel is designed to prove that no other algorithms can get a competitive ratio less than a certain fixed value with such model, and then the lower bound of the competitive ratio for such exploration model is given. This research program will provide new ideas and methods for exploration of polygonal terrains, and its achievements are of great significance and value for solving practical problems involving robotic exploration.

多边形区域的在线探索是计算几何学和机器人学中的一个热点研究问题，在机器人探索、搜索和监控等领域有着广泛的应用。本项目基于计算几何与图论的技术方法，将探索区域设定为一般多边形或直角多边形，研究在预先不知道探索区域几何信息的前提下，引导一个装备有视觉感知系统的机器人探索该区域的算法。考虑到探索中的实际情况，本项目先后引入障碍物和机器人视距的限制条件，研究有障碍物无视距、无障碍物有视距和有障碍物有视距三个场景下的多边形区域探索。在各场景的研究中，首先，结合多边形类型和限定条件建模并分析其几何特征，然后，根据模型特征设计探索算法，并使用竞争比来分析算法的效率，最后，通过设计一个特殊的子模型，证明任何算法在该模型下都得不到比某一固定值小的竞争比，给出该模型中探索算法的竞争比下界。本项目的研究将为多边形区域的探索提供新的思路和方法，其成果对于解决涉及机器人探索的诸多现实问题，具有重要的意义和价值。

本项目基于计算几何与图论的技术方法，在障碍物和视距限制的条件下，研究机器人在线探索未知多边形区域的高效算法。本项目的研究领域为计算几何，研究的问题为与机器人路径规划相关的基础理论问题，是对机器人搜索、探索、监控等领域中一些实际应用问题的抽象，不仅具有理论意义，还具有实际应用价值。本项目经过3年的实施，取得了如下重要成果。首先研究了街道弱感知模型的探索问题，给出了单机器人竞争比为9的在线算法，双机器人竞争比为3的在线算法，并通过给出相匹配的竞争比下界证明了算法的最优性；其次研究了网格多边形的探索问题，通过单元格分割，将探索整个区域等价地转换为访问到每个单元格，给出了竞争比为7/6的最优在线算法；最后研究了多边形外边界的探索问题，针对凸多边形，给出了竞争比为23.78的在线算法并证明下界为5，针对凹多边形，给出了竞争比为26.5的在线算法并证明下界为5.03。依托项目，经过项目组成员的共同努力，完成了15篇学术论文，其中SCI检索论文4篇，EI检索论文7篇，CSCD检索论文4篇；培养了5名硕士研究生，较好地完成了项目所赋予的研究任务。