RI: Small: Variation and self-organization in multi-agent systems
Summary
This project seeks to understand how to use inter-agent variation to improve the ability of swarm-based systems to solve the decentralized task allocation problem. Swarm-based systems consist of large numbers of independent agents that act collectively to accomplish goals beyond the scope of a single agent. Such systems may be applied to problems such as herding, forest fire containment, crowd control, perimeter protection, and hazardous waste clean up, which consist of multiple tasks with demands that may vary over time. The agents in a swarm may be physical robots or virtual software agents. Because these systems are decentralized and have no central controller, each agent decides independently what task to take on and when. Effective and efficient allocation and reallocation of agents among tasks (as task demands change over time) is crucial to good swarm performance. In addition to maintaining an appropriate number of agents on each task at any given time, swarms must also avoid or minimize problems such as extreme responses in which too many or too few agents respond, wasted energy when agents undo and redo each others' work, and deadlocks which may prevent accomplishment of the overall goal altogether. Studies on social insect societies indicate that inter-agent variation is a necessary element for effective and efficient division of labor in biological swarms. Taking inspiration from biology, this work investigates how inter-agent variation affects the decentralized task allocation problem in computational swarms and what types of variation are most effective in producing stable, robust, and adaptable swarms.We examine four specific types of inter-agent variation:
- Variation in response threshold
Response threshold refers to the threshold at which an agent responds to a task stimulius. Variation in response threshold desynchronizes agent actions. If all agents have the same response threshold, then all agents will respond identically and the system as a whole has only two possible responses to a stimulus: all agents act and no agents act. Variation in agent response thresholds allows agents to enter or leave the work force gradually, resulting in smoother, more tempered system responses to changes in stimuli, thus improving system stability and adaptability.
- Variation in response probability
Response probability refers to the probability that an agent will act on a task when its threshold for the task is met. If all agents have a response probability of 100%, the same, lowest-threshold agents will always respond to a given stimulus. When response probability is less than 100%, low threshold agents will sometimes not respond giving higher threshold agents an opportunity to respond and gain experience on a task. For tasks in which experience improves performance, this allows the system as a whole to build a backup pool of agents with experience on tasks. In the event that the lowest threshold agents for a task are lost or become otherwise unavailable, the backup pool means that there are still agents with experience on a task to act on that task, thus improving system robustness and adaptability.
- Variation in response duration
Response duration refers to the amount of time that an agent spends on a task before stopping to re-evaluate its actions. Variation in response durations desynchronizes agent actions which prevents agents from acting in lockstep and generates diversity in agent actions which improves system stability.
- Variation in response intensity
Response intensity refers to the magnitude of an agent's response to a task stimulus. Variation in response intensity allows a swarm as a whole to generate greater diversity in aggregate responses which improves system accuracy. In addition, variation in response intensity potentially allows for improved system efficiency over time, if action intensities increase with experience.
National Science Foundation