Foundations of Computational Mobile Entities: Facing Limitations and Changes

点击翻译按钮获取中文摘要

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.