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 metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01072723
Contributor : Nicolas Nisse <>
Submitted on : Friday, October 17, 2014 - 11:02:16 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on: Sunday, January 18, 2015 - 10:06:26 AM

File

stimergyRobotsRevised_10pages....
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

314

Files downloads

215