Foundations of Computational Mobile Entities: Facing Limitations and Changes

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

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.