Skip to Main content Skip to Navigation
New interface
Conference papers

Understanding the Power of Stigmergy of Anonymous Agents in Discrete Environments

Gianlorenzo d'Angelo 1 Xavier Défago 2 Nicolas Nisse 3 
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Friday, October 17, 2014 - 11:02:16 AM
Last modification on : Thursday, August 4, 2022 - 4:58:23 PM
Long-term archiving on: : Sunday, January 18, 2015 - 10:06:26 AM


Files produced by the author(s)


  • HAL Id : hal-01072723, version 1



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. ⟨hal-01072723⟩



Record views


Files downloads