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. **