基于计算几何与图论的动态目标协作搜索机制及其算法研究

多搜索员协作搜索机制及其搜索算法是动态目标搜索研究的核心问题。本项目基于计算几何与图论的技术方法，针对2维或3维空间里的移动目标，研究搜索这些目标的各种搜索算法。将搜索区域设定为多边形或多面体的表面，并将搜索目标设定为多边形内快速移动的点，设计性能较优的算法搜索该动态目标并计算发现目标所需的最少搜索员数。采用循序渐进方法,先研究1个搜索员在多边形内进行搜索时的充要条件，并在可搜索时给出线性时间算法。然后针对多个搜索员，设计一个递减过程将它逐步归纳为2个搜索员的问题，运用计算几何与图论的相关技术为搜索员建立可视图与动态变迁图，并对已搜索区做合并操作，在此基础上设计相应的求解算法。当多边形内部含有洞(属NP难题)时,采用平面图分割定理进行递归剖分,消去洞的影响并获得较好的近似算法。拓展到3D空间，当多面体表面的垂直投影为平面图时，将它归纳为图的搜索问题后再求解。本项研究成果具有很好的应用前景。

本项目针对基于多边形的动态目标搜索问题进行研究，运用计算几何、图论等技术方法，针对2维或3维空间中的移动目标，研究多搜索员协作搜索这些动态目标的有效搜索算法。本项目属于计算机算法、计算几何领域的应用基础课题，是对机器人运动规划、机器人监测、游戏、军事目标搜索、海上搜救等领域中一些实际应用问题的抽象，研究该问题不仅具有理论意义，而且具有实用价值。本项目首先研究了单个搜索员能够完成多边形搜索的充要条件，并给出了可搜索多边形的高效搜索算法。然后针对多搜索员协作搜索问题，设计了一个归约过程，将对多搜索员协作搜索问题转化为两个搜索员能够求解的问题。针对多边形内部含“洞”以及3D空间中的terrain搜索问题，也分别采用相应的技术方法，将其转化为平面上可求解或可近似求解的问题。依托项目，经过项目成员的共同努力，完成了2部专著；39篇学术论文，其中SCI检索论文4篇，EI检索论文25篇；培养了4名博士生，12名硕士毕业生。项目取得的研究成果在本领域具有较高的水平，较好地完成了项目所赋予的研究任务。