TY - JOUR
T1 - Costs of task allocation with local feedback
T2 - Effects of colony size and extra workers in social insects and other multi-agent systems
AU - Radeva, Tsvetomira
AU - Dornhaus, Anna
AU - Lynch, Nancy
AU - Nagpal, Radhika
AU - Su, Hsin Hao
N1 - Funding Information:
RN is funded by the Wyss Institute for Biologically Inspired Engineering, Harvard University (https://wyss.harvard.edu/). AD is funded by the National Science Foundation (https://www.nsf.gov/) Awards number IOS-3014230. NL, TR, and HS are funded by the National Science Foundation (https://www.nsf.gov/) Awards numbers CCF-0939370 and CCF-1461559, and by the Air Force Office of Scientific Research (http://www.wpafb.af.mil/afrl/afosr) Contract Number: FA9550-13-1-0042. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. We wish to thank the organizers of the annual ‘Biological Distributed Algorithms’ workshop for creating a venue to encourage biology-computer science interaction and collaboration.
Publisher Copyright:
© 2017 Radeva et al.
PY - 2017/12
Y1 - 2017/12
N2 - Adaptive collective systems are common in biology and beyond. Typically, such systems require a task allocation algorithm: a mechanism or rule-set by which individuals select particular roles. Here we study the performance of such task allocation mechanisms measured in terms of the time for individuals to allocate to tasks. We ask: (1) Is task allocation fundamentally difficult, and thus costly? (2) Does the performance of task allocation mechanisms depend on the number of individuals? And (3) what other parameters may affect their efficiency? We use techniques from distributed computing theory to develop a model of a social insect colony, where workers have to be allocated to a set of tasks; however, our model is generalizable to other systems. We show, first, that the ability of workers to quickly assess demand for work in tasks they are not currently engaged in crucially affects whether task allocation is quickly achieved or not. This indicates that in social insect tasks such as thermoregulation, where temperature may provide a global and near instantaneous stimulus to measure the need for cooling, for example, it should be easy to match the number of workers to the need for work. In other tasks, such as nest repair, it may be impossible for workers not directly at the work site to know that this task needs more workers. We argue that this affects whether task allocation mechanisms are under strong selection. Second, we show that colony size does not affect task allocation performance under our assumptions. This implies that when effects of colony size are found, they are not inherent in the process of task allocation itself, but due to processes not modeled here, such as higher variation in task demand for smaller colonies, benefits of specialized workers, or constant overhead costs. Third, we show that the ratio of the number of available workers to the workload crucially affects performance. Thus, workers in excess of those needed to complete all tasks improve task allocation performance. This provides a potential explanation for the phenomenon that social insect colonies commonly contain inactive workers: these may be a ‘surplus’ set of workers that improves colony function by speeding up optimal allocation of workers to tasks. Overall our study shows how limitations at the individual level can affect group level outcomes, and suggests new hypotheses that can be explored empirically.
AB - Adaptive collective systems are common in biology and beyond. Typically, such systems require a task allocation algorithm: a mechanism or rule-set by which individuals select particular roles. Here we study the performance of such task allocation mechanisms measured in terms of the time for individuals to allocate to tasks. We ask: (1) Is task allocation fundamentally difficult, and thus costly? (2) Does the performance of task allocation mechanisms depend on the number of individuals? And (3) what other parameters may affect their efficiency? We use techniques from distributed computing theory to develop a model of a social insect colony, where workers have to be allocated to a set of tasks; however, our model is generalizable to other systems. We show, first, that the ability of workers to quickly assess demand for work in tasks they are not currently engaged in crucially affects whether task allocation is quickly achieved or not. This indicates that in social insect tasks such as thermoregulation, where temperature may provide a global and near instantaneous stimulus to measure the need for cooling, for example, it should be easy to match the number of workers to the need for work. In other tasks, such as nest repair, it may be impossible for workers not directly at the work site to know that this task needs more workers. We argue that this affects whether task allocation mechanisms are under strong selection. Second, we show that colony size does not affect task allocation performance under our assumptions. This implies that when effects of colony size are found, they are not inherent in the process of task allocation itself, but due to processes not modeled here, such as higher variation in task demand for smaller colonies, benefits of specialized workers, or constant overhead costs. Third, we show that the ratio of the number of available workers to the workload crucially affects performance. Thus, workers in excess of those needed to complete all tasks improve task allocation performance. This provides a potential explanation for the phenomenon that social insect colonies commonly contain inactive workers: these may be a ‘surplus’ set of workers that improves colony function by speeding up optimal allocation of workers to tasks. Overall our study shows how limitations at the individual level can affect group level outcomes, and suggests new hypotheses that can be explored empirically.
UR - http://www.scopus.com/inward/record.url?scp=85039906071&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85039906071&partnerID=8YFLogxK
U2 - 10.1371/journal.pcbi.1005904
DO - 10.1371/journal.pcbi.1005904
M3 - Article
C2 - 29240763
AN - SCOPUS:85039906071
SN - 1553-734X
VL - 13
JO - PLoS Computational Biology
JF - PLoS Computational Biology
IS - 12
M1 - e1005904
ER -