Description
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.
