RI: Small: Variation and self-organization in multi-agent systems

点击翻译按钮获取中文摘要

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.This project consists of three phases. First, carry out a systematic study to build a model of the relationship between inter-agent variation and the self-organizing behavior of swarms. This phase will examine how different types of variation in agent decision making characteristics affect system level stability and adaptability. Second, investigate methods for and trade offs of dynamically evolving system variation. This phase will investigate how principles from machine learning methods such as evolutionary computation may be used to dynamically learn and adjust inter-agent variation in response to changing task demands. Third, apply and test conclusions from phase one and two to a multi-agent herding problem. The multi-agent herding problem is representative of a range of problems that require division of labor involving search, gathering, containment, and coordinated movement.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.