Algorithms and Foundations for Computational Mobile Entities

考虑一个由移动实体组成的系统，这些移动实体在附近相互交互，其行为非常简单：当活动时，实体看(感知紧邻环境)、计算(执行一组确定性规则以计算目的地)并向计算的目的地移动。*在这样的系统中，单独的单个实体非常弱，不能执行任何有意义的任务；然而，实体的集合整体能够进行相当复杂的计算，如形成所需的图案、队形移动、围绕对象、搜索。*这一研究计划的主线是研究这类移动计算实体组的可计算性和复杂性问题，遵循两个主要研究轴：1)实体在平面上移动，2)实体在图上移动。*在第一轴方向上，长期目标是更好地理解感知仅限于局部的移动实体系统的限制和能力；重点关注允许它们执行任务的最低能力。为了实现这一目标，我计划研究一些重要的因素，如内存、通信、同步，并就这些因素对实体的全局计算能力的影响提出自然的基本问题。*在第二个研究轴的方向上，长期目标是为高动态网络中移动实体的分布式(即分散)计算开发算法工具和分析方法。为了实现这一目标，我计划首先集中在探索、交会和地图构建等问题上，然后根据系统的时间结构、其他网络参数和实体可用的环境知识，询问在高度动态网络中移动的实体可以执行哪些操作。*通过这些研究，我希望对移动计算实体系统有更深入的了解，显著提高我们对它们的限制和能力的知识。我还预计，这个项目将为几个协调问题带来新的算法，以及分析动态网络的新方法。在这样做时，它还将产生新的技术，这些技术可能在实际系统的设计和分析中产生实际影响。**

Consider a system composed by mobile entities that interact with each other when in proximity, and whose behaviour is extremely simple: when active, an entity Looks (perceives the immediate surroundings), Computes (executes a set of deterministic rules to compute a destination), and Moves toward the computed destination.***In such a system, the single entity, alone, is quite weak and cannot perform any meaningful task; the collection of entities, in its entirety, can however be capable of rather complex computations, like forming desired patterns, moving in formation, surrounding an object, searching. ***The general thread of this research plan is the investigation of computability and complexity issues for groups of such mobile computational entities, following two main research axes: 1) entities moving on the plane, and 2) entities moving on graphs.***In the direction of the first axis, the long term objective is to better understand limitations and abilities of systems of mobile entities whose perception is only local; the focus is on the minimal capabilities that allow them to perform their tasks. To achieve this goal, I plan to study some important factors like memory, communication, synchrony, and ask natural fundamental questions on the impact that these factors have on the global computational power of the entities.***In the direction of the second research axis, the long term objective is to develop algorithmic tools and analysis methods for distributed (i.e., decentralized) computations by mobile entities in highly dynamic networks. To achieve this goal, I plan to first concentrate on problems like exploration, rendezvous, and map construction, and then ask general questions on what can be performed by the entities moving in highly dynamic networks depending on the temporal structure of the system, on other network parameters, and on the knowledge available to the entities about the environment.***With these investigations, I expect to gain a deeper understanding of systems of mobile computational entities, significantly advancing our knowledge on their limits and capabilities. I also anticipate that this project will lead to new algorithms for several coordination problems, as well as novel methods for the analysis of dynamic networks. In doing so it will also generate new techniques that could have a practical impact in the design and analysis of actual systems. **