Recruiting robots perform stochastic diffusion search

doi:10.15406/iratj.2018.04.00111

eISSN: 2574-8092

International Robotics & Automation Journal

Opinion Volume 4 Issue 2

Recruiting robots perform stochastic diffusion search

Bishop JM,¹

Verify Captcha

Regret for the inconvenience: we are taking measures to prevent fraudulent form submissions by extractors and page crawlers. Please type the correct Captcha word to see email ID.

De Meyer K,² Nasuto SJ³

¹Goldsmiths, University of London, UK
²Kings College London, UK
³University of Reading, UK

Correspondence: Bishop JM, Goldsmiths, University of London, UK

Received: March 23, 2018 | Published: April 26, 2018

Citation: Bishop JM, De Meyer K, Nasuto SJ. Recruiting robots perform stochastic diffusion search. Int Rob Auto J. 2018;5(2):1-4. DOI: 10.15406/iratj.2018.04.00111

Download PDF

Opinion

A Letter to Nature¹ demonstrated that a simple ant-inspired `tandem calling' recruitment mechanism² Improved task performance in a group of robots. In these experiments a group of robots attempt to locate `food' and return it to base. On its return a successful robot tries to recruit another to help exploit its find. As a result a population of robots rapidly expands to exploit the resource, resulting in greater foraging efficacy. In this note we observe that the type of recruitment and information sharing mechanism employed by the robots is one instance of a general class of Swarm Intelligence parallel search and optimization methods, known as Stochastic Diffusion Search (SDS).³

SDS is an efficient probabilistic multi-agent global search, optimization and decision making technique⁴ that has been applied to diverse problems such as site selection for wireless networks,⁵ mobile robot self-localization,⁶ object recognition⁷ and text search³. Additionally, a hybrid SDS method was successfully used to track facial features in video sequences.^7,8 Previous analysis of SDS has investigated its global convergence,⁹ linear time complexity¹⁰ and resource allocation¹¹ under a variety of search conditions. For a recent review of the theoretical foundations and applications of SDS by Al-Rifaie and Bishop.¹²

In SDS, a set of agents individually test for the presence of a small part of the target pattern at a specific location in the search space. The robot foraging task can be seen as a pattern recognition task in which the target parts are uniform; the test then simply equates to a test for the presence of `food' at a location. If an agent passes the test, i.e. finds a partial match, it tries to attract other agents to co-examine the same region in the search space (diffusion of information). An agent failing the test can either be recruited by another agent successfully examining a (partial) match, or otherwise randomly adopt a new search location.

By iterating through test and diffusion phases agents will stochastically explore the whole search space. However, since tests will succeed more often in regions having a large overlap with the target pattern than in regions with irrelevant information, an individual agent will spend more time examining these regions, at the same time attracting other agents, which in turn attract even more agents. Thus, potential matches to the target pattern are identified by concentrations of a substantial population of agents. Because such populations develop dynamically, SDS is able to track changing and moving patterns.

The `attention' of a dynamic population of agents to a part of the search space has been suggested as an alternative mechanism solving a persistent problem in neuroscience, the binding problem.¹³ Classical connectionist models view neurons as simple computational devices; however, a neural network model of SDS grounded upon communication as a metaphor for neuronal operation¹⁴ has now been implemented. Emergent synchronization across a large population of neurons in this network can be interpreted as a mechanism of attentional amplification.¹⁵

The basic properties of SDS are well understood: convergence to the global optimal solution;^7,16 convergence time, increasing at most linearly with search space size;¹⁶ resource allocation dynamics.⁶ The algorithm is robust to noise distortion and multiple instantiations of the target.⁶ SDS also provides a solution for an old problem in Artificial Intelligence, the problem of stimulus equivalence: the ability to recognize a pattern independent of its potential distortions or transformations in the search space.^3,7

As a general class of search and optimization algorithms, Stochastic Diffusion Processes have many features in common with other population-based algorithms inspired by nature: Genetic Algorithms, pheromone trail-based Ant Search and Mimetic Algorithms. Moreover, the well understood theoretical properties, together with the elegance, speed and robustness of the algorithm make it a valuable additional tool in addressing many search and optimization problems where partial evaluations of candidate solutions provide useful information about the global search problem.