AMYBIA
Aggregating MYriads of Biologically-Inspired Agents
This page provides more information on the AMYBIA projet.
We describe here others approaches related to ours.
This page provides only a starting point ; it is intended to grow as our research advances.
The idea that distributed computing systems could find inspiration in the biological domain is certainly not new and goes back to von Neuman's work about cellular automata
[1]. More recently, several computing systems/paradigms have been developed, that heavily rely on such biological metaphors.
Amorphous computing
[2], embryonics
[3], P-systems
[4] or claytronics
[5] are just examples of this trend. However, few of these examples have specifically focused on the capabilities of biological systems to promote the emergence of a coordination among their individual entities.
Similarly, the properties of reaction-diffusion travelling waves have been used directly or indirectly as metaphor, for the design of computation devices.
Indeed travelling waves propagate without attenuation at constant speed, vanish on collision with each other or the environment boundaries and split around obstacles (i.e., skirt them) during their propagation
[6]. Hence, they offer a way to handle problems related to computational geometry such as Voronoi diagram, shortest path search, robot navigation or image skeletisation
[7]. Ant algorithms are arguably the most famous bio-inspired algorithms where the interplay between diffusion and chemotaxis allows the ants to self-organise and form spatial patterns in a coherent way. The "ant colony meta-heuristic" was successfully applied for solving various problems in computer science: travelling salesman, routing in networks...
[8]. Finally, more recent biological metaphors rely on the organisation of bacterial colonies. This is in particular exemplified by quorum sensing-inspired algorithms, whereby the cell behaviour abruptly switches when a cell-produced chemical in the environment reaches a given threshold
[9]. Note however that these latter algorithms usually do not make use of the properties derived from bacterial chemotaxis.
Our project can be seen as the complementation of these approaches using a different paradigm, namely reaction-diffusion-chemotaxis.
Indeed we believe that there exist various problems in which those mechanisms could reveal new self-organisation principles.
The performance of our algorithms will be compared to other proposals in the field, in particular ant algorithms, chemical computing or quorum sensing-inspired algorithms.
We expect the performance of our proposal to be higher in noisy environments, such as in the cases of irregular neighbourhoods, faulty or noisy environments or computing elements and, most notably, in the presence of large-size obstacles to information propagation.
- [1] E.F. Moore, Machine models of self-reproduction,Proc. Symposia in Applied Mathematics, 14:17-33,1962.
- [2] Abelson H. et al., Amorphous computing,Communications of the ACM, 43:74-82,2001.
- [3] Mange et al., Embryonics: A microscopic view of the molecular architecture,In Evolvable systems: from biology to hardware, M. Sipper, D. Mange & A. Perez-Uribe, eds, vol 1478 of Lecture Notes in Computer Science, Springer, Berlin, pp. 185-195,1998.
- [4] Paun G. , Membrane computing: an introduction,Springer Verlag, Berlin,2002.
- [5] Pillai et al, A 3D fax machine based on claytronics,Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, Bejing, China, 4728-2735,2006.
- [6] Steinbock et al, Navigating complex labyrinths: optimal paths from chemical waves,Science, 267:868-871,2005.
- [7] Adamatzky A. et al, Elsevier,,2006; Reaction-diffusion computers.
- [8] Dorigo M. and Stutzle T., Ant colony optimization,MIT Press,2004.
- [9] Wokoma et al, A Biologically-Inspired Clustering Algorithm Dependent on Spatial Data on Sensor Networks,Proc. European Conference on Wireless Sensor Networks, Istambul, Turkey,2005.
|