Computational issues in systems of mobile entities

移动实体系统中的计算问题

• 批准号: 203254-2011
• 负责人: Flocchini, Paola
• 金额: $ 2.4万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=569914
• 关键词: Computational; issues; systems; mobile; entities

In this project I am interested in the design of deterministic algorithms for groups of computational moving entities. Such entities are identical, extremely simple and individually quite weak; but collectively capable of performing possibly complex tasks. The environment in which the entities operate can be a network or a terrain. In both environments the behaviour of the entities is cyclic: an entity becomes active (asynchronously and independently), it decides where to move based on the protocol, it moves to a location, and it becomes inactive again. What can be done by a team of entities and how efficiently depends on the characteristics of the entities like, for example, their communication media, their ability to see neighbouring entities, their level of synchronization, the possibility to remember the past. Some of the entities' characteristics (for example, locality, obliviousness, and communication) are particularly important and their study could have significant consequences in terms of scalability, efficiency, and fault-tolerance. The main objective of the project is to study the above mentioned characteristics to understand the extent of their impact on typical coordination problems. In particular, I will focus on identifying the minimal capabilities that allows the entities to successfully perform their tasks. The main novelty of my approach is to tackle the various problems (e.g., pattern formation, exploration, rendezvous, flocking) from an analytical and deterministic standpoint as opposed to following probabilistic approaches or empirical methods. The approach I will follow is typical to the fields of algorithms and theoretical computer science and will consist of first creating coherent and precise models of the problems under investigation, secondly solving problems or identifying situations of unsolvability. The algorithmic solutions will employ a variety of techniques based on combinatorics, discrete mathematics, graph theory, and geometry. The significant consequences of this study will be a better understanding of the computational power of mobile computational entities and the design of novel algorithms that are scalable, fault-tolerant, and possibly self-stabilizing.

在这个项目中，我感兴趣的是为群体设计确定性算法， 计算移动实体。这些实体是相同的，极其简单，单独非常弱;但集体能够执行可能复杂的任务。 实体操作的环境可以是网络或地形。在这两种环境中，实体的行为都是循环的：一个实体变得活跃（异步和独立），它根据协议决定移动到哪里，它移动到一个位置，然后它再次变得不活跃。一组实体可以做什么以及效率如何取决于实体的特性，例如它们的通信媒体，它们看到相邻实体的能力，它们的同步水平，记住过去的可能性。一些实体的特征（例如，局部性、遗忘性和通信）特别重要，它们的研究可能在可扩展性、效率和容错性方面产生重大影响。 该项目的主要目标是研究上述特征，以了解它们对典型协调问题的影响程度。特别是，我将着重于确定允许实体成功执行其任务的最低能力。 我的方法的主要新奇之处是解决各种问题（例如，模式形成、探索、会合、群集），而不是遵循概率方法或经验方法。 我将遵循的方法是算法和理论计算机科学领域的典型方法，首先包括为正在研究的问题创建连贯和精确的模型，其次解决问题或识别不可解决的情况。 算法解决方案 将采用基于组合数学、离散数学、图论和几何学的各种技术。这项研究的重要后果将是更好地理解的计算能力的移动的计算实体和新的算法，可扩展的，容错的，并可能自我稳定的设计。