Organization and Reorganization of Multiagent Systems

The goal of the CoDA Project is to create intelligent control techniques for advanced multiagent systems, that is, systems of cooperating intelligent agents. Our first domain is controlling autonomous oceanographic sampling networks (AOSNs), which are groups of autonomous underwater vehicles (AUVs) and other instrument platforms that together form a system for gathering data over long term in an area of interest. CoDA, in fact, stands for Cooperative Distributed AOSN control.

AOSNs. AOSNs are important for many applications. The most obvious is for oceanography. It is very difficult and expensive to get data from the ocean for long periods of time, and the problem is compounded when one needs simultaneous data from widely-separated locations, often called synoptic data of an area. Multi-AUV systems are ideal for this. Environmental applications, such as global climate change measurements and pollution tracking, are another important area where multi-AUV systems can be employed. There are also military applications, for example, as a surveillance system or as a system that can detect and possibly destroy mines and unexploded ordnance. Search and rescue operations can also be considered from a multi-AUV approach. For example, should a plane go down in the ocean, one can envision a group of AUVs traveling to or being delivered (by submarine, air, etc.) to the general area, then the system organizing itself to carry out search tasks. Industrial applications are also possible, for example in aquaculture or fisheries management.

CoDA. The kinds of multiagent systems in which we are interested are those that will be deployed for long periods to perform complex missions with little or no direct human supervision. In these systems, agents (e.g., AUVs) will come and go over time for a variety of reasons, and the mission is likely to change as time goes by as well.

CoDA takes a cooperative distributed problem solving (CDPS) approach to the problem of controlling such systems. Agents are assumed to be cooperative and willing to abide by a set of protocols defined for the system. Although the agents may be self-interested up to a point, we also assume that the agents are at least willing to cooperate on some things with their peers.

Organization/reorganization. A primary goal of CoDA is to develop techniques for autonomous organization and reorganization of a multiagent system. This is important, since it may be difficult or even impossible for a human to prescribe an organization ahead of time: there may well be no way to know what AUVs will actually show up at the work site, or in what condition. Consequently, we assume that the system will need to autonomously self-organize based on those assets that are actually present, the mission, and the current environment. Since the situation is subject to change, CoDA needs the ability to reorganize as well.

A problem is that without knowing what agents are present, it is difficult to create an organization—or even to select who should attempt to create it. Any organization that makes few assumptions about the agents present is likely to be inefficient, and yet efficient organizations may not be possible to create ahead of time.

We take a two-level approach to this problem. Initially, when agents arrive at the work site, they “ping” each other to determine who else is present that has the intelligence to participate in CoDA. Following individual cooperation protocols, the agents discover this, then form a loose organization called the meta-level organization (MLO). The MLO’s sole task is to create an efficient organization to carry out the mission. It proceeds to try to discover the range of the system’s assets and to agree on the mission. Then it designs the task-level organization (TLO) that will carry out the mission. The MLO then dissolves, passing control to the TLO.

When something goes wrong, or when the situation changes in some other way, the TLO may have the flexibility to handle it. If not, however then the agents have protocols to re-create the MLO, which then repairs or redesigns the TLO.

Task assignment. Task assignment is an important focus of CoDA as well. Once the mission is known and the assets of the system are known, CoDA must assign agents to tasks. This is done via a variant of constrained heuristic search based on the advertised capabilities of the agents and their resource limits compared to the capabilities and resources required for the mission.

Simulator. To support work on CoDA as well as other multiagent systems projects, we have developed the CoDA simulator, a multi-fidelity simulation testbed for multiagent systems. CoDA can run as a discrete-event simulator, simulating the agents at a very high level of abstraction and faster than real time. This allows rapid development and testing of the cooperation protocols, for example. Later, more accurate simulation can be done by dropping in pieces of the code the agents would actually run. At the highest fidelity, agents would be simulated completely, including their decision-making capabilities. To provide high-fidelity vehicle simulation, CoDA has been interfaced to AUSI’s CADCON multi-AUV simulation testbed.

Related projects. There are three broad needs for multiagent systems: individual agent control, communication mechanisms, and cooperation (or at least interaction) protocols. CoDA addresses the latter. A sibling project, [Orca][orca], address the intelligent control of the agents themselves. Past project in our lab have focused on communication mechanisms as well.

Researchers: Roy Turner, Sonia Rode

Funding: CoDA has been funded in part by the Office of Naval Research (N0001-14-96-1-5009, N0001-14-98-1-0648)

Publications: See the MaineSAIL publications page

Status: After a hiatus, work has begun again on CoDA. In particular, the current simulator is being rewritten to use Lisa rather then CLIPS, thus keeping all code in Lisp. This is in preparation for further refinement and extension of the cooperation protocols. The simulator can be made available under GPL.

History: Work began on CoDA as an outgrowth of the MAVIS project at the Marine Systems Engineering Laboratory (now AUSI, the Autonomous Undersea Systems Institute); initially, it was called the MAUV (Multiple AUV) project. The CoDA project still enjoys ties to AUSI, who are also interested in multi-AUV control mechanisms.