Understanding the Power of Stigmergy of Anonymous Agents in Discrete Environments

Abstract : Communication by stigmergy consists, for agents/robots devoid of other dedicated communication devices, in exchanging information by observing each other's movements, similar to how honeybees use a dance to inform each other on the location of food sources. Stigmergy, while a popular technique in soft computing (e.g., swarm intelligence and swarm robotics), has received little attention from a computational viewpoint, with only one study proposing a method in a continuous environment. An important question is whether there are limits intrinsic to the environment on the feasibility of stigmergy. While it is not the case in a continuous environment, we show that the answer is quite different when the environment is discrete. This paper considers stigmergy in graphs and identifies classes of graphs in which robots can communicate by stigmergy. We provide two algorithms with different tradeoffs. One algorithm achieves faster stigmergy when the density of robots is low enough to let robots move independently. This algorithm works when the graph contains some particular pairwise-disjoint subgraphs. The second algorithm, while slower solves the problem under an extremely high density of robots assuming that the graph admits some large cycle. Both algorithms are described in a general way, for any graph that admits the desired properties and with identified nodes. We show how the latter assumption can be removed in more specific topologies. Indeed, we consider stigmergy in the grid which offers additional orientation information not available in a general graphs, allowing us to relax some of the assumptions. Given an $N\times M$ anonymous grid, we show that the first algorithm requires $O(\mathcal{M})$ steps to achieve communication by stigmergy, where $\mathcal{M}$ is the maximum length of a communication message, but it works only if the number of robots is less than $\left\lfloor\frac{N\cdot M}{9}\right\rfloor$. The second algorithm, which requires $O(k^2)$ steps, where $k$ is the number of robots, on the other hand, works for up to $N\cdot M-5$ robots. In both cases, we consider very weak assumptions on the robots capabilities: i.e., we assume that the robots are anonymous, asynchronous, uniform, and execute deterministic algorithms.
Type de document :
Communication dans un congrès
Second International Symposium on Computing and Networking (CANDAR), Dec 2014, Mt. Fuji, Shizuoka, Japan. 2014
Liste complète des métadonnées


https://hal.inria.fr/hal-01072723
Contributeur : Nicolas Nisse <>
Soumis le : vendredi 17 octobre 2014 - 11:02:16
Dernière modification le : lundi 5 octobre 2015 - 17:00:56
Document(s) archivé(s) le : dimanche 18 janvier 2015 - 10:06:26

Fichier

stimergyRobotsRevised_10pages....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01072723, version 1

Collections

Citation

Gianlorenzo D'Angelo, Xavier Défago, Nicolas Nisse. Understanding the Power of Stigmergy of Anonymous Agents in Discrete Environments. Second International Symposium on Computing and Networking (CANDAR), Dec 2014, Mt. Fuji, Shizuoka, Japan. 2014. <hal-01072723>

Partager

Métriques

Consultations de
la notice

172

Téléchargements du document

115