An official website of the United States government
We study the problem of distributed task allocation by workers in an ant colony in a setting of limited capabilities and noisy environment feedback. We assume that each task has a demand that should be satisfied but not exceeded, i.e., there is an optimal number of ants that should be working on this task at a given time. The goal is to assign a near-optimal number of workers to each task in a distributed manner without explicit access to the value of the demand nor to the number of ants working on the task. We seek to answer the question of how the quality of task allocation depends on the accuracy of assessing by the ants whether too many (overload) or not enough (lack) ants are currently working on a given task. In our model, each ant receives a binary feedback that depends on the deficit, defined as the difference between the demand and the current number of workers in the task. The feedback is modeled as a random variable that takes values lack or overload with probability given by a sigmoid function of the deficit. The higher the overload or lack of workers for a task, the more likely it is that an ant receives the correct feedback from this task; the closer the deficit is to zero, the less reliable the feedback becomes. Each ant receives the feedback independently about one chosen task. We measure the performance of task allocation algorithms using the notion of inaccuracy, defined as the number of steps in which the deficit of some task is beyond certain threshold. We propose a simple, constant-memory, self-stabilizing, distributed algorithm that converges from any initial assignment to a near-optimal assignment under noisy feedback and keeps the deficit small for all tasks in almost every step. We also prove a lower bound for any constant-memory algorithm, which matches, up to a constant factor, the accuracy achieved by our algorithm.
more »
« less
Remember the Past and Forget Thresholds
One of the most popular existing models for task allocation in ant colonies is the so-called threshold-based task allocation model. Here, each ant has a fixed, and possibly distinct, threshold. Each task has a fixed demand which represents the number of ants required to perform the task.1Thestimulusanant receives for a task is defined as the demand of the task minus the number of ants currently working at the task. An ant joins a task if the stimulus of the task exceeds the ant’s threshold.A large body of results has studied this model for over four decades; however, most of the theoretical works focuses on the study of two tasks. Interestingly, no work in this line of research shows that the number of ants working at a task eventually converges towards the demand nor does any work bound the distance to the demands over time.In this work, we study precisely this convergence. Our results show that while the threshold-based model works fine in the case of two tasks (for certain distributions of thresholds); the threshold model no longer works for the case of more than two tasks. In fact, we show that there is no possible setting of thresholds that yields a satisfactory deficit (demand minus number of ants working on the task) for each task.This is in stark contrast to other theoretical results in the same setting [CDLN14] that rely on state-machines, i.e., some form of small memory together with probabilistic decisions. Note that, the classical threshold model assumes no states or memory (apart from the bare minimum number of states required to encode which task an ant is working on). The resulting task allocation is near-optimal and much better than what is possible using joining thresholds. This remains true even in a noisy environment [DLM+18]. While the deficit is not the only important metric, it is conceivably one of the most important metrics to guarantee the survival of a colony: for example if the number of workers assigned for foraging stays significantly below the demand, then starvation may occur. Moreover, our results do not imply that ants do not use thresholds; we merely argue that relying on thresholds yields a considerable worse performance.
more »
« less
- Award ID(s):
- 1810758
- PAR ID:
- 10161888
- Date Published:
- Journal Name:
- 7th Workshop on Biological Distributed Algorithms (BDA)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the problem of distributed task allocation in multi-agent systems e.g. the division of labor in an ant colony or robot swarm. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the number of agents required to perform each task.The goal of the agents is to collectively allocate themselves to the tasks to satisfy the demand vector. We study the dynamic version of the problem where the demand vector changes overtime. Here, the goal is to minimize the switching cost, which is the number of agents that change tasks in response to a change in the demand vector. The switching cost is an important metric since changing tasks may incur significant overhead.We study a mathematical formalization of the above problem introduced by Su, Su, Dornhaus, and Lynch [21]. We prove the first non-trivial lower bounds for the switching cost.more » « less
-
We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modelled as a probabilistic agent with limited power, and there is no central control governing the ants. We show a (log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Further, we show a matching upper bound of expected O(log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest qualities or a quorum rule can affect the emigration process. In particular, we find that a quorum threshold that is high enough causes transports to the inferior nest to cease to happen after O(log n) rounds when there are two nests in the environment.more » « less
-
We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modelled as a probabilistic agent with limited power, and there is no central control governing the ants. We show a Ω(log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Further, we show a matching upper bound of expected O(log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest qualities or a quorum rule can affect the emigration process. In particular, we find that a quorum threshold that is high enough causes transports to the inferior nest to cease to happen after O(log n) rounds when there are two nests in the environment.more » « less
-
We study the problem of house-hunting in ant colonies, where ants reach consensus on a new nest and relocate their colony to that nest, from a distributed computing perspective. We propose a house-hunting algorithm that is biologically inspired by Temnothorax ants. Each ant is modeled as a probabilistic agent with limited power, and there is no central control governing the ants. We show an O( log n) lower bound on the running time of our proposed house-hunting algorithm, where n is the number of ants. Furthermore, we show a matching upper bound of expected O( log n) rounds for environments with only one candidate nest for the ants to move to. Our work provides insights into the house-hunting process, giving a perspective on how environmental factors such as nest quality or a quorum rule can affect the emigration process.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
