AMYBIA
Aggregating MYriads of Biologically-Inspired Agents
As explained above, controlling massively parallel irregular systems at low costs necessitates the development of new decentralized algorithms based on spatial abstractions. A major expected benefit of these new algorithms is that they may adapt to faulty or noisy situations more gracefully. At long term, our objective is to develop systems/tools that actually calculate some results. As a start, we however have to focus on a more restricted goal.
Hence, as a first short term objective, we consider the problem of dynamically allocating a large set of computing units, in the presence of evolving faults or defects. As a specific problem, we consider the decentralised gathering problem that consists in grouping at the same location, agents that move on a grid and that are initially randomly scattered on this grid. The main constraint here is that the agents can only see their immediate neighbourhood. Moreover, they cannot directly communicate with each other: all they can do is to send simple messages, called 'influences', to their environment. This condition is aimed at adapting to faulty computing units but implies that this algorithm must be performed as a low-cost subprocess or subroutine.
The prototype model that motivates our approach of the decentralised gathering problem is inspired from the aggregation phenomenon in Dictyostelium discoideum.
Click here to see a detailed description of the model (paper preprint and demos).
The nodes of the grid follow a cellular automaton dynamic: they read the states of their neighbours and change it according to a simple, uniform and local transition rule. The state of a node can be of three types neutral, excited or refractory.
The moves of the agents are also simple: they move by following the nodes that are in a particular state.
Interactions between the nodes and the agents are governed by a single rule: a node that is neutral might get excited, with a given probability, if it has an agent on it.
|