Combinatorial Search-Type Problems for Mobile Agents

移动代理计算涉及许多组合和/或几何算法问题，其中许多移动代理（搜索者/机器人）需要执行任务，例如探索未知地形，定位隐藏物品或实现特殊编队，例如聚集在一个地点。与理论计算机科学的基本问题一致，这些问题的目标是确定受计算资源约束的算法边界。在这个研究项目中，我将在这个方向上进一步扩展，通过研究一些搜索型问题的组合问题，旨在开发新的算法工具以及证明负（不可能）结果的新技术。在60年代早期，数学家们首先将搜索型问题视为在所谓的捉迷藏游戏中确定最佳策略的一种手段。几十年后，计算机科学界重新发明了这个话题，在在线算法的镜头下检查了同样的问题，即部分输入未知的优化问题（例如，移动代理寻找的隐藏项目）。甚至在最近，由于考虑了多个移动代理及其底层通信模型，该领域重新焕发了活力。到目前为止，已经有一长串的结果为一些变化确定了积极和消极的结果。当前研究方案的新颖之处在于强调几何移动智能体问题的组合结构。更具体地说，该计划将考虑有关非确定性计算模型的研究问题，效率/资源权衡，以及移动代理的组合属性。这些方向将搜索类型问题作为组合问题重新审视，其中它们的可追踪性不仅由输入的（部分）信息决定，还由作为处理器的移动代理的计算能力决定。上述研究方向的意义涉及到计算中关于组合问题可溯性的基本问题。该领域的进展将产生新的算法技术来解决分布式环境中的困难优化问题，以及新的数学工具来证明底层计算模型中的效率限制。除了该课程的理论价值外，理解组合搜索型问题还可以应用于应急响应、搜索和救援行动、监视以及对动物/昆虫行为的理解。

Mobile agent computing pertains to a number of combinatorial and/or geometric algorithmic problems in which a number of mobile agents (searchers/robots) need to execute a task, e.g. explore an unknown terrain, locate hidden items or achieve a special formation such as gathering in one spot. In alignment with fundamental questions of Theoretical Computer Science, the goal in such problems is to identify algorithmic boundaries subject to computation resources. In this research program I will expand further in this direction by investigating a number of combinatorial questions for search-type problems aiming to develop new algorithmic tools as well as new techniques for proving negative (impossibility) results. Search-type problems were first considered in the early 60's by mathematicians as a means to identify optimal strategies in so-called hide-and-seek games. The topic was reinvented by the computer science community a few decades later, where the same problems were examined under the lens of online algorithms, that is, optimization problems where part of the input is not known (e.g. the hidden item that is sought by mobile agents). Even more recently, the area was rejuvenated due to the consideration of multiple mobile agents along with their underlying communication model. To this date, a long series of results exist that establish both positive and negative results for a number of variations. The novelty of the current research program is the emphasis on the combinatorial structure of geometric mobile agent problems. More specifically, the program will consider research questions pertaining to non-deterministic models of computation, efficiency/resources trade-offs, and combinatorial attributes for the mobile agents. These directions revisit the search-type problems as combinatorial problems, where among others their tractability is determined not only by the (partial) information of the input but also by the computational capabilities of the mobile agents as processors. The significance of the above research directions pertains to the fundamental question in computing regarding the tractability of combinatorial problems. Progress in the area will give rise to new algorithmic techniques for solving hard optimization problems in a distributed environment, as well as to new mathematical tools for proving efficiency limitations in the underlying model of computation. Apart from the theoretical value of the program, understanding combinatorial search-type problems can have applications in emergency response, in search and rescue operations, in surveillance and in the understanding of animal/insect behavior.