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.