Combinatorial Search-Type Problems for Mobile Agents

点击翻译按钮获取中文摘要

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.