Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems
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 individu...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Public Library of Science (PLoS)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/118171 https://orcid.org/0000-0003-1261-6681 https://orcid.org/0000-0003-3045-265X |
| _version_ | 1826203051001643008 |
|---|---|
| author | Dornhaus, Anna Nagpal, Radhika Radeva, Tsvetomira T. Lynch, Nancy Ann Su, Hsin-Hao |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Dornhaus, Anna Nagpal, Radhika Radeva, Tsvetomira T. Lynch, Nancy Ann Su, Hsin-Hao |
| author_sort | Dornhaus, Anna |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:30:54Z |
| format | Article |
| id | mit-1721.1/118171 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:30:54Z |
| publishDate | 2018 |
| publisher | Public Library of Science (PLoS) |
| record_format | dspace |
| spelling | mit-1721.1/1181712022-09-28T08:13:58Z Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems Dornhaus, Anna Nagpal, Radhika Radeva, Tsvetomira T. Lynch, Nancy Ann Su, Hsin-Hao Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Radeva, Tsvetomira T. Lynch, Nancy Ann Su, Hsin-Hao 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. National Science Foundation (U.S.) (Grant CCF-0939370) National Science Foundation (U.S.) (Grant CCF-1461559) United States. Air Force Office of Scientific Research (Grant FA9550-13-1-0042) 2018-09-26T14:08:51Z 2018-09-26T14:08:51Z 2017-12 2017-03 2018-09-19T15:44:30Z Article http://purl.org/eprint/type/JournalArticle 1553-7358 1553-734X http://hdl.handle.net/1721.1/118171 Radeva, Tsvetomira et al. “Costs of Task Allocation with Local Feedback: Effects of Colony Size and Extra Workers in Social Insects and Other Multi-Agent Systems.” Edited by Natalia L. Komarova. PLOS Computational Biology 13, 12 (December 2017): e1005904 © 2017 Radeva et al https://orcid.org/0000-0003-1261-6681 https://orcid.org/0000-0003-3045-265X http://dx.doi.org/10.1371/JOURNAL.PCBI.1005904 PLOS Computational Biology Creative Commons Attribution 4.0 International License http://creativecommons.org/licenses/by/4.0/ application/pdf Public Library of Science (PLoS) PLoS |
| spellingShingle | Dornhaus, Anna Nagpal, Radhika Radeva, Tsvetomira T. Lynch, Nancy Ann Su, Hsin-Hao Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems |
| title | Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems |
| title_full | Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems |
| title_fullStr | Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems |
| title_full_unstemmed | Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems |
| title_short | Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems |
| title_sort | costs of task allocation with local feedback effects of colony size and extra workers in social insects and other multi agent systems |
| url | http://hdl.handle.net/1721.1/118171 https://orcid.org/0000-0003-1261-6681 https://orcid.org/0000-0003-3045-265X |
| work_keys_str_mv | AT dornhausanna costsoftaskallocationwithlocalfeedbackeffectsofcolonysizeandextraworkersinsocialinsectsandothermultiagentsystems AT nagpalradhika costsoftaskallocationwithlocalfeedbackeffectsofcolonysizeandextraworkersinsocialinsectsandothermultiagentsystems AT radevatsvetomirat costsoftaskallocationwithlocalfeedbackeffectsofcolonysizeandextraworkersinsocialinsectsandothermultiagentsystems AT lynchnancyann costsoftaskallocationwithlocalfeedbackeffectsofcolonysizeandextraworkersinsocialinsectsandothermultiagentsystems AT suhsinhao costsoftaskallocationwithlocalfeedbackeffectsofcolonysizeandextraworkersinsocialinsectsandothermultiagentsystems |