Algorithms and Foundations for Computational Mobile Entities

计算移动实体的算法和基础

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

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

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