Grant: Discovery Grants Program - Individual

This project is concerned with computing in environments where the interacting entities are autonomous and decentralized, but also mobile. These environments comprise very different systems, including networks supporting software mobile agents, robotic swarms and robotic networks, vehicular networks, mobile sensors networks, etc. The entities we consider are identical, simple, ""disposable"", so they can be created inexpensively, and damaged or ""lost"" ones can be easily replaced. Although individually ""weak"", we want the entities to be able, collectively, to solve complex tasks. In other words, the computational capabilities lie not in the single entity but within the ""team"". This project focuses on the very basic issues at the heart of computing in such environments: computability and complexity; that is, on question like: what problems can be solved ? under what conditions ? how? at what cost ? In particular, the aim is always to determine what minimal hypotheses (e.g., capabilities of the entities, restrictions on the environment) allow a given problem to be solved.The problems range from electing a leader (a temporary coordinator), to creating maps of the environment; from locating black holes (harmful hosts that destroys incoming agents), to decontaminating a network being infected by a mobile intruder (e.g. a virus); from gathering autonomous mobile vehicles (e.g., tanks) dispersed on a terrain, to scattering mobile sensors on a terrain so to obtain a uniformly coverage of the space (e.g., for surveillance). In spite of the differences, the same fundamental principles occur in all these contexts. The discovery of these principles is a new important long-term research challenge; their study is the main underlying goal of this project.