Task allocation in a society of agents is the regulation of appropriate global division of labor over a set of tasks with respect to a given evaluation metric. For example, for a typical ant colony to prosper, it needs ants foraging for food, defending the colony from intruders, repairing the nest, tending the brood, and many other tasks. The appropriate division of labor in the ant colony, that is how many ants should be participating in each task at any given time, is determined by the current environmental conditions.
In particular, we are interested in mechanisms for self-organized task allocation. In self-organized task allocation, the appropriate global division of labor emerges as a result of local interactions among relatively simple agents. Returning to the ant colony example, the actions of each ant can largely be explained by a relatively simple set of behaviors, yet an appropriate colony division of labor emerges from the local interactions of the ants.
It is desirable for such a self-organized system to be capable of dynamically adjusting the division of labor in response to changing environmental conditions and/or societal needs. For example, if the ant colony’s nest is being invaded by another colony, then the number of ants defending the nest should be increased in response, and as the threat subsides the number of ants defending the nest should decrease.
In self-organized task allocation, it is up to the individual agent to decide which of possibly many tasks to actively participate in at any given time. There is no central coordinator dispensing tasks in self-organized task allocation. Each individual agent must make this decision on which task to perform based only on limited, local, and noisy information in a partially-observable and highly non-stationary environment. Therefore, key questions in the design of self-organized task allocation mechanisms center on how an individual agent decides what to work on at any given time. What does an agent need to make this decision on what task to perform and how can those needs be met in a particular implementation?
For example, what information might an agent need and how might this information be obtained? Information that could be useful includes: what tasks are currently active, how many agents are participating in each task, what is the workload of each task, what is the importance of each task, and how expensive is it to change tasks. The next question is, how might an agent acquire this information given that it only has access to limited, local information in a non-stationary world? The agents may be able to gather information through agent-agent interactions or through the task dynamics. Agent-agent interactions could be direct or indirect and they could be explicit (radio) or implicit (passive sensing of some characteristic of a nearby agent). Communication through the task dynamics, so called stigmergic communication, is the case where information is effectively communicated through the actual performance of a task. Other questions in task allocation are, what are the characteristics of specific task allocation mechanisms in terms of robustness, fault tolerance, and scalability (in both extremes)? In what domains are specific task allocation mechanisms appropriate. For example, in some cases all the tasks may be spatially co-located and in others they may be disjoint or there may be temporal constraints between tasks that must be met.
To begin addressing these issues in task allocation, we have begun developing some task allocation mechanisms and experimentally investigating their performance in various domains.
Figure 1. Left: Sequential foraging results in various environments Right: Standard deviation of results
A second domain we are looking at is that of concurrent task execution of a set of spatially co-located tasks. In this case, as opposed to sequential task execution, all the tasks are active at once and the proportion of agents involved in each task must be regulated by some mechanism. The experimental domain is again a variation on the foraging task. In these experiments, a collection of different object types, red and green food, are to be collected and transported to the appropriate home region. Each agent is either foraging for red food or green food at any given time; however, all agents are capable of foraging either type of food and can switch between types when they determine it is appropriate to do so. The division of labor between the two agent types should be maintained roughly equivalent to the proportion of each food type. At any time food may be added or removed and agents may be added or removed and the colony will quickly adapt to the change and converge to the correct division of labor.
Two mechanisms are explored, one using stigmergic communication through the task dynamics and the other using both stigmergic communication and implicit agent-agent interactions through sensing the “state” (what type of food it is foraging) of nearby agents. The purpose of these experiments is to determine information important in this particular domain and to explore methods for agents to obtain this information. In this first experiment, the information used is that of relative task workload and this information if obtained by each agent through sampling (stigmergic communication). Each agent samples the proportions of each food type it encounters and maintains an adaptive threshold dictating when that agent should switch foraging tasks. In the second experiment two types of information are used, the first is that of relative task workload which is obtained through sampling (stigmergic communication) and the second is that of current agent division of labor which is obtained through sampling the state of encountered agents. Each agent samples the proportions of food types encountered and also samples which foraging task each agent it encounters (runs into) is involved in. Using these two (sampled) proportions, the agent makes a decision on which task it should be involved to maintain the globally correct ratio of food types vs. foragers. Experimental results for this experiment are shown below in Figure 2.
Figure 2. Experimental results in concurrent task allocation using information on task workload and current division of labor.
We are currently developing an information theoretic approach to the analysis of large-scale distributed systems.
This work is supported in part by the DARPA TASK Program, in part by the DARPA MARS Grand DABT63-99-1-0015, and in part by ONR Grant N000140110354.