Algorithms and Foundations for 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.