Moving and Computing: Agents, Robots and Networks – MACARON

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 » (http://leds-chat.net/): 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.