Submit manuscript...
eISSN: 2574-8092

International Robotics & Automation Journal

Opinion Volume 4 Issue 2

Recruiting robots perform stochastic diffusion search

Bishop JM,1 De Meyer K,2 Nasuto SJ3

1Goldsmiths, University of London, UK
2Kings College London, UK
3University 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 Nature1 demonstrated that a simple ant-inspired `tandem calling' recruitment mechanism2 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).3

SDS is an efficient probabilistic multi-agent global search, optimization and decision making technique4 that has been applied to diverse problems such as site selection for wireless networks,5 mobile robot self-localization,6 object recognition7 and text search3. 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,9 linear time complexity10 and resource allocation11 under a variety of search conditions. For a recent review of the theoretical foundations and applications of SDS by Al-Rifaie and Bishop.12

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.13 Classical connectionist models view neurons as simple computational devices; however, a neural network model of SDS grounded upon communication as a metaphor for neuronal operation14 has now been implemented. Emergent synchronization across a large population of neurons in this network can be interpreted as a mechanism of attentional amplification.15

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;16 resource allocation dynamics.6 The algorithm is robust to noise distortion and multiple instantiations of the target.6 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.

Acknowledgements

None.

Conflict of interest

The author declares there is no conflict of interest.

References

  1. Krieger MJB, Billeter JB, Keller L. Ant-like task allocation and recruitment in cooperative robots. Nature. 2000;406(6799):992–995.
  2. Möglich M, Maschwitz U, Hölldobler B. Tandem calling: a new kind of signal in ant communication. Science. 1974;186(4168):1046–1047.
  3. Bishop JM. Stochastic searching networks. In: Proc 1st IEE Int Conf Arti-ficial Neural Networks, IEE Conference Publication; London. 1989. p. 329–331.
  4. De Meyer K, Nasuto SJ, Bishop JM. Stochastic diffusion optimization: the application of partial function evaluation and stochastic recruitment. In: Abraham A, Grosam C, Ramos V, editors. Stig ergic Optimization, Studies in Computational Intelligence 31. Heidelberg, New York. Springer: Berlin; 2006. p. 185–207.
  5. Whitaker RM, Hurley S. An agent based approach to site selection for wireless networks. In: Proc. 2002 ACM Symp Applied Computing (Madrid); ACM: New York. 2002. p. 574–577.
  6. Beattie PD, Bishop JM. Self localization in the `SENARIO' autonomous wheelchair. Journal of Intelligent and Robotic Systems. 1998;22:255–267.
  7. Bishop JM, Torr P. The stochastic search network. In: Linggard R, Myers DJ, Nightingale C, editors. Neural Networks for Images, Speech and Natural Language. Chapman Hall: New York; 1992.
  8. Grech-Cini E. Locating facial features. University of Reading: Reading. 1995.
  9. Nasuto SJ, Bishop JM. Convergence of the stochastic diffusion search. Parallel Algorithms and Applications. 1999;14(2):89–107.
  10. Nasuto SJ, Bishop JM, Lauria S. Time Complexity of Stochastic Diffusion Search. In: Heiss M, editor. Proc. Int. ICSC / IFAC Symposium on Neural Computation. Austria.1998.
  11. Nasuto SJ, Bishop JM. Steady State Resource Allocation analysis of the stochastic diffusion search, Biologically Inspired Cognitive Architectures. 2015;12:65–76.
  12. al-Rifaie MM, Bishop JM. Stochastic Discussion Search Review. Journal of Behavioural Robotics. 2013;4(3):155–173.
  13. Nasuto SJ, Bishop JM. Multiple Drafts or Global Workspace? Proc. ASSC2: Neural Correlates of Consciousness: empirical and conceptual questions. Germany. 1998. p. 56.
  14. Nasuto SJ, Dautenhahn, K, Bishop JM. Communication as an emergent metaphor for neuronal operation. In: Nehaniv C, editor. Computation for Metaphors, Analogy, and Agents. Lecture Notes in Artificial Intelligence 1562, Springer: Berlin, Heidelberg, New York; 1999. p. 365–379.
  15. De Meyer K, Bishop JM, Nasuto SJ. Consciousness and Cognition 2000;9(2):S81.
  16. Nasuto SJ. Resource allocation analysis of the stochastic diffusion Search. University of Reading: Reading. 1999.
Creative Commons Attribution License

©2018 Bishop, et al . This is an open access article distributed under the terms of the Creative Commons Attribution License , which permits unrestricted use, distribution, and build upon your work non-commercially.