Foundations of Computational Mobile Entities: Facing Limitations and Changes

该研究计划旨在研究由大量计算移动实体组成的系统中的计算和复杂性问题。实体运行的环境要么是离散的(例如，图)，要么是连续的(例如，平面)。无论具体环境如何，它们自主行动，感知环境，它们通常以一种简单的方式与邻近地区互动，它们的目标是共同完成一些全球任务(例如，形成模式，聚集在同一地点，以队形移动)。本研究的主要目标是在给定单个实体的计算能力的情况下更好地了解实体组的整体计算能力，特别是在面对环境变化的情况下。我的研究目标是以下两个主要方向：1)研究连续空间中的移动实体，以更好地了解它们的限制和能力，专注于允许它们执行任务的最低能力；2)评估在网络上移动的代理团队的限制和能力，这些网络的拓扑结构在入侵者存在的情况下随时间发生变化；我尤其感兴趣的是为团队设计策略，以便有效地搜索入侵者(S)以将其从网络中移除。我的总体长期研究目标是提供两个方向的算法基础，并使用结果来进一步深入了解移动实体计算的本质。沿着第一个方向，我计划开始研究机器人的计算能力，这些机器人的能量是有限的，但可能在一个或多个不活动的时期是可再生的，目的是在各种环境中提供能量受限和不受限机器人之间关系的特征。我还打算探索机器人在新的具有挑战性的环境中的计算能力，在这种环境中，多个机器人团队需要在同一时间在同一空间执行不同的、可能相互冲突的任务。第二个方向代表了该领域中一个重要但在很大程度上仍未探索的研究领域。在感兴趣的问题中，我计划集中在两个特定的问题上，在这两个问题上，一组特工必须搜索一个(或多个)试图避免被捕获的入侵者。在第一个问题(警察和强盗)中，代理和入侵者都知道彼此的位置，在第二个问题(网络去污)中，代理不知道入侵者在哪里移动。这两个问题都有可能描述计算机病毒的行为。变化的环境和入侵者的同时存在以前从未被研究过；能够使移动实体在这些情况下操作的高效确定性算法的设计可以立即在各种现实环境中应用。

This research plan aims to study computational and complexity issues in systems composed by a multitude of computational mobile entities. The environment where entities operate is either discrete (e.g., a graph) or continuous (e.g., the plane). Regardless of the specific setting, they act autonomously, they sense the environment, they move typically interacting in a simple way with their immediate neighbourhood, and their objective is to accomplish, together, some global tasks (e.g., form a pattern, gather at the same location, move in formation). The main goal of this research is to better understand the overall computational power of the group of entities given the computational power of the single one, especially in face of changes in the environment. My research aims at deterministic provably correct approaches following two main directions: 1) the study of mobile entities in continuous spaces, to better understand their limitations and abilities focusing on the minimal capabilities that allow them to perform their tasks; 2) assess limitations and capability of teams of agents moving on networks whose topology changes in time in presence of intruders; in particular, I am interested in the design of strategies for the team to effectively search for the intruder(s) to remove them from the network. My overall long term research goal is to provide algorithmic foundations in both directions and use the results to attain further insights into the nature of computing by mobile entities. Along the first direction, I plan to initiate the study of the computational capabilities of robots whose energy is limited but possibly renewable through one or more periods of inactivity, with the goal of providing a characterization of the relationship between energy-restricted and unrestricted robots in a variety of settings. I also intend to explore the computability power of the robots in a new challenging setting, where multiple teams of robots need to perform different, possibly conflicting, tasks in the same space at the same time. The second direction represents an important but still largely unexplored research area in the field. Among the problems of interest, I plan to concentrate on two specific ones, where a team of agents must search for one (or more) intruders that try to avoid being captured. In the first problem (cops and robber), the agents and the intruder are all aware of each other's positions, in the second (network decontamination), the agents do not know where the intruder is moving. Both problems can potentially describe the behaviors of computer viruses. The simultaneous presence of a changing environment and an intruder has never been studied before; the design of efficient deterministic algorithms enabling the mobile entities to operate under these circumstances can have immediate applications in a variety of realistic setting.