Foundations of Computational Mobile Entities: Facing Limitations and Changes

计算移动实体的基础：面临限制和变化

• 批准号: RGPIN-2022-03332
• 负责人: Flocchini, Paola
• 金额: $ 3.5万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=752487
• 关键词: Foundations; Computational; Mobile; Entities; Facing

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.

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