ANR LIF Aix-Marseille Université CNRS


scientific description of the project (pdf)

Project summary:

There is an emerging trend in robotics : rather than by a few bulky robots, certain tasks can be performed by tiny robots, each with very limited capabilities. This trend is similar to the less recent trend about sensor networks, with sensors that are also of limited capabilities but deployed in huge number. This is the emergence of systems where elementary bricks are simple and cheap though can provide relatively complex collective behavior. From an algorithmic point of view, one need to consider a new computing paradigm « Moving and computing »: the study and design of systems where the computational entities themselves are capable of movement within the spatial universe they inhabit. The field has applications in areas as diverse as autonomous robots moving in a terrain, software agents moving in a network, autonomous intelligent vehicles, wireless mobile ad-hoc networks, and networks of mobile sensors; where the computational objectives are exploration, coordination and cooperation.

When considering the design of algorithms for mobile robots in a geometric environment, the modeling of the environment, i.e., the way the mobile entities have access to it, is crucial. The entities can have access to only limited aspects of the environment : e.g. where it can move. Indeed, in this setting, the robot main responsibility is to compute where to go next. Such a modeling implies the study of the graph of the possible locations, linked by the elementary moves. Such a graph does not have an arbitrary structure but inherit some combinatorial properties from its geometric context. In this framework, using the mobile agent model, from classical distributed computing, is very much relevant. The specificity of our study is that the graphs under consideration are of geometric type (e.g. the visibility graph of a polygon). Moreover, it is known that adding more sensing capabilities will yield more efficient algorithms. A natural investigation is therefore to characterize what are the weakest kind of sensors, i.e., the kind of geometric information, that enable to solve efficiently problems such as exploration, map construction, rendezvous, ...

In contrast with the previous situation, in the case of mobile sensors, the computation is more how to react to moves and changes in the topology that are not directly under control. However, similarly, by using geometric properties, it is possible to improve the efficiency of algorithms, compare to algorithms using only combinatorial graphs properties. Hence, solving tasks such as broadcast, computing/repairing local structures, benefits from a deep understanding of the relationship generated by the actual topology of the sensor network, especially the possible dynamic evolutions of such networks. It is also possible to show that the ``mobile agent" model is also relevant in this context, because it enables to use a simple computational structure within a complex data structure.

A distant goal for our research, that will be of importance in the near future, is to investigate thoroughly the interactions and evolutions of mobile agents in dynamic networks. More generally, our objective is to dramatically improve the models and algorithms for distributed robot computing. Such a study implies to get a better understanding of the relations between local, global and geometric properties shared by those problems and environments. We will benefit from tools and known results from geometric graph theory, discrete algebraic topology, computational geometry and timed systems. Last, part of the validation of this project's results will be done with « LED's CHAT » : a modular light and sensor system developed at LIF, and currently subject to a technology transfer program with the aim of commercializing the technology to actual light applications.

Project aims:

The aim of our project is to design efficient algorithms for distributed systems that have geometric properties and can be dynamic.

We want to identify large families of geometric graphs where mobile agents can solve fundamental distributed algorithms such as map construction or rendezvous efficiently. To do so, we need to use and study the combinatorial properties of these geometric families of graphs, as well as results from algebraic topology.

Considering mobile robots moving in geometric environments, we want to identify the weakest geometric sensors that enable the agents to solve coordination problems such as rendezvous without having to explore the entire environment. Example of sensors we want to consider are sensors that allow the agents to compute their position (GPS), angles, distances, etc. Considering sensor networks, we want to study what geometric sensors allow to obtain local algorithms (i.e., algorithms that terminate in constant time) to build local structures such as maximal independent set or minimal dominating set. In order to answer these questions, one should use the properties of the underlying geometric environment and use some results and techniques from geometric graph theory and computational geometry.

Considering dynamic networks, we want to identify the combinatorial and temporal properties of dynamic geometric networks that allow to solve fundamental problems such as broadcast. We also want to study mobile agent models in dynamic networks by adapting existing techniques in the study of timed automata.

We want to extend the ViSiDiA simulator to study and visualize our models and algorithms. We also want to extend the « LED's CHAT » system so that it can handle wireless communication and support dynamic changes of the topology. This requires that the models we develop in our theoretical studies are realistic enough in order to be able to transfer our algorithms into this actual embedded system.