Grant: Discovery Grants Program - Individual
University of Ottawa
$42,000.00
Algorithms and Foundations for Computational Mobile Entities
EF 2017-18
Résumé
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 onwhat 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 togain 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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2017-05022
Name nom
Flocchini, Paola
Department département
Electrical Engineering and Computer Science , School of - science informatique e
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2017
Award amount
42000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
1
Nb partie
5
Application title
Algorithms and Foundations for Computational Mobile Entities
Keyword
NSERC
Application summary
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 onwhat 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 togain 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.