Noise, cost and speed-accuracy trade-offs: decision-making in a decentralized system
Abstract
Many natural and artificial decision-making systems face decision problems where there is an inherent compromise between two or more objectives. One such common compromise is between the speed and accuracy of a decision. The ability to exploit the characteristics of a decision problem in order to vary between the extremes of making maximally rapid, or maximally accurate decisions, is a useful property of such systems. Colonies of the ant Temnothorax albipennis (formerly Leptothorax albipennis) are a paradigmatic decentralized decision-making system, and have been shown flexibly to compromise accuracy for speed when making decisions during house-hunting. During emigration, a colony must typically evaluate and choose between several possible alternative new nest sites of differing quality. In this paper, we examine this speed-accuracy trade-off through modelling, and conclude that noise and time-cost of assessing alternative choices are likely to be significant for T. albipennis. Noise and cost of such assessments are likely to mean that T. albipennis' decision-making mechanism is Pareto-optimal in one crucial regard; increasing the willingness of individuals to change their decisions cannot improve collective accuracy overall without impairing speed. We propose that a decentralized control algorithm based on this emigration behaviour may be derived for applications in engineering domains and specify the characteristics of the problems to which it should be suited, based on our new results.
Footnotes
References
Banks J.S& Sundaram R.K . 1994 Switching costs and the Gittins index. Econometrica 62, 687–694. Crossref, Web of Science, Google ScholarBishop J.M . 1989 Stochastic searching networks.In Proc. First IEE Conf. on Artificial Neural Networks London:IEE Press 329–331. Google ScholarBonabeau E, Dorigo M& Theraulaz G . 1999 Swarm intelligence: from natural to artificial systems. New York:Oxford University Press. Google ScholarChittka L, Dyer A.G, Bock F& Dornhaus A . 2003 Bees trade off foraging speed for accuracy. Nature 424, 388 doi:10.1038/424388a. Crossref, PubMed, Web of Science, Google ScholarDean T.L& Boddy M . 1988 An analysis of time-dependent planning., Mitchell T.M& Smith R.G In Proc. Seventh Nat. Conf. on Artificial Intelligence Menlo Park, CA:AAAI Press 49–54. Google ScholarDornhaus A, Franks N.R, Hawkins R.M& Shere H.N.S . 2004 Ants move to improve: colonies of Leptothorax albipennis emigrate whenever they find a superior nest site. Anim. Behav 67, 959–963.doi:10.1016/j.anbehav.2003.09.004. Crossref, Web of Science, Google ScholarDragalin V.P, Tartakovsky A.G& Veeravalli V.V . 1999 Multihypothesis sequential probability ratio tests—part I: asymptotic optimality. IEEE Trans. Info. Theo 45, 2448–2461.doi:10.1109/18.796383. Crossref, Web of Science, Google ScholarEdwards W . 1965 Optimal strategies for seeking information: models for statistics, choice reaction times, and human information processing. J. Math. Psy 2, 312–329.doi:10.1016/0022-2496(65)90007-6. Crossref, Web of Science, Google ScholarFoster I& Kesselman C In The grid: blueprint for a new computing infrastructure 2003 San Francisco, CA:Morgan Kaufmann. Google ScholarFranks N.R, Pratt S.C, Mallon E.B, Britton N.F& Sumpter D.J.T . 2002 Information flow, opinion polling and collective intelligence in house-hunting social insects. Phil. Trans. R. Soc. B 357, 1567–1583.doi:10.1098/rstb.2002.1066. Link, Web of Science, Google ScholarFranks N.R, Dornhaus A, Fitzsimmons J.P& Stevens M Speed vs. accuracy in collective decision making. Proc. R. Soc. B 270 2003a 2457–2463.doi:10.1098/rspb.2003.2527. Link, Web of Science, Google ScholarFranks N.R, Mallon E.B, Bray H.E, Hamilton M.J& Mischler T.C Strategies for choosing between alternatives with different attributes: exemplified by house-hunting ants. Anim. Behav 65 2003b 215–223.doi:10.1006/anbe.2002.2032. Crossref, Web of Science, Google ScholarHutchinson J.C . 2004 Is more choice always desirable? Evidence and arguments from leks, food selection, and environmental enrichment. Biol. Rev 79, 1–20.doi:10.1017/S1464793103006183. PubMed, Web of Science, Google ScholarJun T . 2004 A survey on the bandit problem with switching costs. De Economist 152, 513–541.doi:10.1007/s10645-004-2477-z. Crossref, Web of Science, Google ScholarMallon E.B& Franks N.R . 2000 Ants estimate area using Buffon's needle. Proc. R. Soc. B 267, 765–770.doi:10.1098/rspb.2000.1069. Link, Web of Science, Google ScholarMallon E.B, Pratt S.C& Franks N.R . 2001 Individual and collective decision-making during nest site selection by the ant Leptothorax albipennis. Behav. Ecol. Sociobiol 50, 352–359.doi:10.1007/s002650100377. Crossref, Web of Science, Google ScholarMarshall J.A.R& Rowe J.E . 2003 Viscous populations and their support for reciprocal cooperation. Artif. Life 9, 327–334.doi:10.1162/106454603322392497. Crossref, PubMed, Web of Science, Google Scholarde Meyer K, Bishop J.M& Nasuto S.J . 2003 Stochastic diffusion: using recruitment for search., McOwan P, Dautenhahn K& Nehaniv C.L In Evolvability and interaction: evolutionary substrates of communication, signalling, and perception in the dynamics of social complexity. Technical Report 393 University of Hertfordshire:Department of Computer Science 60–65. Google ScholarMugford S.T, Mallon E.B& Franks N.R . 2001 The accuracy of Buffon's needle: a rule of thumb used by ants to estimate area. Behav. Ecol 12, 655–658.doi:10.1093/beheco/12.6.655. Crossref, Web of Science, Google ScholarPartridge L.W, Partridge K& Franks N.R . 1997 Field survey of a monogynous leptothoracine ant (Hymenoptera: Formicidae): evidence of seasonal polydomy? Insect. Soc 44, 75–83.doi:10.1007/s000400050031. Crossref, Web of Science, Google Scholar- Planqué, R., Dornhaus, A., Frank, N. R., Kovacs, T. & Marshall, J. A. R. In preparation. Weighting waiting in collective decision making. Google Scholar
Pratt S.C, Mallon E.B, Sumpter D.J.T& Franks N.R . 2002 Quorum sensing, recruitment, and collective decision-making during colony emigration by the ant Leptothorax albipennis. Behav. Ecol. Sociobiol 52, 117–127.doi:10.1007/s00265-002-0487-x. Crossref, Web of Science, Google Scholar- Pratt, S. C., Sumpter, D. J. T., Mallon, E. B., Franks, N. R. In press. An agent-based model of collective nest choice by the ant Temnothorax albipennis. Anim. Behav. Google Scholar
Stender J In Parallel genetic algorithms: theory and applications 1993 Amsterdam:IOS Press. Google ScholarSutton R.S& Barto A.G In Reinforcement learning: an introduction 1998 Cambridge, MA:MIT Press 53. Google ScholarTheil H . 1950 A rank invariant method of linear and polynomial regression analysis (I, II & III). Proc. Koninklijke Nederlandse Akademie Wetenschappen, Series A—mathematical sciences 53, 386–392.521–525, 1397–1412. Google ScholarWald A& Wolfowitz J . 1948 Optimum character of the sequential probability ratio test. Ann. Math. Stat 19, 326–339. Crossref, Google ScholarWilson W.G . 1998 Resolving discrepancies between deterministic population models and individual-based simulations. Am. Nat 151, 116–134.doi:10.1086/286106. Crossref, PubMed, Web of Science, Google Scholar