As robots and other autonomous agents become more widespread, there will be a greater need for them to work cooperatively to accomplish complex, long-duration tasks. Such groups of agents will often be highly heterogeneous and open: that is, agents will enter or leave the system while the task is being performed. This presents a formidable problem for organizing and controlling the agents. In this paper, we present an approach to this problem for autonomous oceanographic sampling networks (AOSNs), which are groups of robots and sensor platforms that cooperate to sample an area over a long period of time. The approach uses two organizations to control the agents. A task-level organization (TLO) controls the system during the actual mission, and a meta-level organization (MLO) is responsible for self-organization of the system, design of the TLO to fit the situation, and reorganization as necessary. This approach allows the TLO to be highly efficient, while allowing the MLO to give the overall system a great deal of flexibility in adapting to change.
Autonomous oceanographic sampling networks (AOSNs) [Curtin et al., 1993] are multi-robot systems being developed to collect data from the ocean over long periods of time. During deployment, the AOSN may alter its task in response to previously-collected data or new instructions from scientists. An AOSN will be composed of a wide variety of components, including autonomous underwater vehicles (AUVs), remotely-operated vehicles (ROVs), and non-mobile instrument platforms. Because underwater robots are so expensive to develop, and because so few exist, components of the AOSN will include AUVs and ROVs that have been loaned to the AOSN by undersea robotics laboratories.
Like all multi-agent systems, the AOSN requires a mechanism for organizing its components. However, AOSNs have several characteristics which make existing approaches for organization inappropriate. We believe these characteristics will be shared by an increasing number of systems as more robots become available and are used to perform more complex missions over longer periods of time. These characteristics are:
Excellent performance is expected. As robotics research advances, users will have elevated expectations about the performance of the system. Systems, at a minimum, will have to perform their task effectively. In addition, the systems should be efficient and reliable. For example, an AOSN will need to guarantee its users high levels of data quality and coverage. To these ends, there must be some global control to ensure efficiency and monitor expected results.Existing CDPS approaches fall short on addressing one or more of these characteristics. For example, Partial Global Planning (PGP) [Durfee & Lesser, 1987] requires all agents to have sophisticated problem-solving abilities, and it does not take the sort of global perspective necessary to ensure data quality. The Contract Net Protocol (CNP) [Smith, 1980] also fails to take a global approach to designing the organization it creates, and it is not clear how well it handles the failure or exit of mid-level or top-level managers. Multiagent planning approaches [Cammarata et al., 1983,Georgeff, 1983, e.g.,], though taking a global perspective, do not cope well with the possibility of the planning agent(s) failing or leaving the system. Limited bandwidth is a problem for almost all approaches. In addition, most existing approaches suffer from a trade-off between flexibility and efficiency. Efficient approaches are not particularly adaptable when the situation changes, and flexible approaches are not as efficient as might be desired. A middle-ground approach is worse than either: the system will be neither adaptive enough nor efficient enough.
We have developed a two-level approach to controlling AOSNs to address these problems. Two organizations are used to control the agents. A task-level organization (TLO) controls the actual mission-related tasks, and a meta-level organization (MLO) is used to design as efficient a TLO as possible. Only the robots in the MLO are required to reason about the organization. The MLO self-organizes and can take a global perspective to design a TLO. The TLO then conducts the mission until there is a change beyond its capability to adapt. At that point, the MLO again regains control to reorganize the system by repairing or designing a new TLO. This provides both efficiency and flexibility.
In the remainder of this paper, we first discuss the approach in general, then look more closely at task assignment and at how reorganization takes place in the system. We then describe the simulation testbed in which this work is being developed.
Our overall approach is shown in Figure 1. The operation of the system is partitioned into two general phases, one controlled by the meta-level organization and one controlled by the task-level organization. Within these are smaller phases. All activities of the system and the agents are controlled by protocols that dictate acceptable actions given the situation and the phase the system is in. All vehicles and instrument platforms (VIPs) that participate in the system must abide by the protocols or a subset of the protocols appropriate for their level of participation. Thus those that can participate in the MLO must be able to follow most of the protocols, while those that can participate only in the TLO must follow the TLO protocols relevant to them.
The meta-level organization is composed of those agents present that have the capability to reason about which organization is appropriate for the mission. This means that these agents, called MLO agents, must be fairly sophisticated. The MLO, then, will contain a subset of the VIPs present.
When first deployed, the task facing the AOSN's agents is to self-organize into a meta-level organization capable of designing the task-level organization. We assume that the system may not initially have much knowledge of itself. This could happen, for example, if the VIPs were deployed by air drop, in which case not all may survive, or if they were supposed to rendezvous at a location, in which case not all may have arrived. Thus, the MLO cannot be created a priori, nor should it rely on the presence of particular VIPs.
Consequently, our MLO formation protocol makes few assumptions about which agents will be present. The agents capable of participating in the MLO (called MLO agents) each carry out a simple sequence of actions designed to identify their peers. Figure 2 shows the protocol used for forming the MLO. The result is a ``flat'' meta-level organization in which each member can communicate with all the others and no single agent is in charge. As long as there is a single MLO agent present, the MLO can form and the mission can continue.
The exchange of information specified by the MLO-formation protocol establishes common knowledge of the MLO's membership and location of the agents. The next task is to determine the total capabilities available to the AOSN to conduct its task. This is done by the MLO discovery protocol (see Figure 3), which guides the MLO agents in querying non-MLO VIPs about their abilities.
We treat each agent as a black box with advertised capabilities [Turner et al., 1993, see, e.g.,]. This simplifies designing the TLO, as it abstracts away unnecessary detail about the specifics of the agent's implementation. It also facilitates interoperability of disparate agents, since a ``vocabulary'' of capabilities provides a common interface to the agents and a standard way of communicating about them. In many ways, the benefits are similar to those from object-oriented programming. This representation of agents means that, practically speaking, any VIP can participate in the system as long as it is capable of responding appropriately to queries about its capabilities.
At the end of the protocol shown in Figure 3, the MLO knows all the capabilities of all agents in the system. To reduce bandwidth requirements, our current MLO organization distributes responsibility for this knowledge among the MLO agents. Each MLO agent is responsible for knowing about the capabilities of those VIPs closest to it.
At this point, the MLO can proceed to design the TLO. The current protocol, shown in Figure 4, calls for a single planner to be selected by convention from among the MLO agents. The planner gathers information from its peers about capabilities related to accomplishing the mission at hand, then it designs a task-level organization. In the future, we will examine how and when to distribute the planning task among multiple MLO agents.
We currently restrict the kinds of organizations considered for the TLO to be hierarchies. Hierarchical organizational structures have several benefits, including efficiency of communication [Malone, 1987], effectiveness in the face of uncertainty [Fox, 1981], and the possibility of global coherence of actions, since there is a top-level manager. Even with this restriction, however, the problem of designing a TLO is rich enough to be interesting, since hierarchies can vary along a number of axes, including the kind and timing of communication allowed, number of levels, and whether or not peers are allowed to cooperate outside the management structure. In the future, we plan to broaden our consideration to include other kinds of task-level organizational structures.
The planner designs the TLO by matching VIP capabilities to mission tasks, creating the hierarchy's management structure, and assigning VIPs to management roles, based again on their advertised capabilities. Our first implementation of task assignment used a very simple first-fit mechanism, and the assignment of management roles is done using simple heuristics (e.g., pick a manager from among the agents working on a task, if possible). The second version is based on constrained heuristic search [Fox et al., 1989], in which task assignment is treated as a constraint satisfaction problem. This is described in more detail in Section III. In the future, we intend to examine the feasibility of using an enhanced version of the distributed constrained heuristic search algorithm [Sycara et al., 1991] for task assignment to allow the entire MLO to participate. We will also extend the approach to organizational design in two ways. First, we are developing a representation for organizations that will allow an agent to analyze the situation, then quickly choose an organization type and specific parameters based on the situation's features. Second, we will ultimately examine the feasibility of incorporating management roles into the ``tasks'' assigned by CHS.
Once the TLO is designed, the planner informs the new managers of their roles and whom they control and tells the top-level manager to begin work. The planner then sends a message to its peers in the MLO informing them that the MLO is now dissolved.
Once formed, the task-level organization controls the AOSN until the mission is complete or there is a change severe enough to be beyond the TLO's ability to accommodate.
Figure 5 shows the major protocol used in hierarchical TLOs. When a TLO manager receives notification of its assignment, it analyzes itself and its subordinates to identify any slack resources (e.g., unused capabilities). This information is passed to the TLO's top-level manager, which keeps a record of the slack capabilities and VIPs present in the system. This gives the TLO a limited ability to respond to changes in the task or its own composition, as discussed in Section IV. When the manager receives a ``begin work'' message, it passes it along to its subordinates (which pass it along to their subordinates, etc.) and begins work on its own task(s).
We have not yet defined protocols governing mission-related aspects of the AOSN control such as communication between manager and subordinate during work on tasks. To a large extent, this will depend on the specifics of the task, manager, and subordinate. Protocols will be needed, however, to allow the managers of the TLO to gather and maintain current information about the state of the TLO and the mission. This will be addressed in future work.
Task assignment is currently implemented using a variant of constrained heuristic search (CHS) [Fox et al., 1989] that has been extended for task decomposition trees [Turner & Turner, in press]. CHS was chosen as the basis for our task assignment algorithm because it efficiently finds a solution if one exists. CHS ties constraint satisfaction to heuristic search by supplying operators which add constraints and variables to the constraint graph. The alternative methods for carrying out the task are selected using heuristics which indicate how likely it is that an assignment can be found within the resource constraints of the VIP. The selected capabilities are placed in a constraint graph as variables whose values are constrained by the resource limitations of the VIPs. Then constraint satisfaction techniques are used to find a solution.
If an agent has time and sufficient knowledge, it may be able to gracefully leave the system by notifying the MLO or TLO, whichever currently exists. A protocol for doing this in the context of the TLO is shown in Figure 6. This protocol is specific for hierarchical TLOs and requires the top-level manager to maintain a list of slack resources present in the system. If the top-level manager itself needs to leave, it can consult this list to determine if there is another agent present that can take over for it. If not, then the manager has exhausted the TLO's ability to adapt and initiates reorganization via re-forming an MLO, as discussed below. If the exiting agent is not the top-level manager, it signals its manager and, if that manager has knowledge about resources under its control that can be assigned to replace the agent, it replaces the agent and passes information up the hierarchy about the change. Otherwise, it notifies its own manager about the agent's intention to exit and lets that manager attempt to handle the change in the context of its more global viewpoint. Ultimately, if no other manager can handle the change, then the top-level manager will attempt to replace the exiting agent. If it cannot, it will initiate reorganization by the MLO.
It would be overly optimistic to assume that in all (or even most) cases, agents can exit gracefully. When an agent fails, it often will not have the time or the ability to signal its manager. In such cases, the agent's manager and peers will have to determine that the agent has failed. This is, in general, a very difficult problem that we will address in future work. Once failure is detected, however, it can be treated similarly to a more graceful exit.
The entry of new agents is also important. A new agent's arrival will not force the TLO or MLO to reorganize, but the availability of its capabilities will often provide an opportunity to achieve a task more effectively or to work on a task impossible to achieve previously. For example, at the time the TLO was created, perhaps the only vehicle present that could take data samples of a particular kind was one whose navigational precision was poor enough that some data points would be missed. Later, if a vehicle with the required sensor and a much better navigational system enters the AOSN, it would make sense to assign it to take over the old agent's task.
Our agent entry protocols are sufficiently complex, due to the need to handle agent entry in any phase of AOSN operation, that space does not permit a discussion here. They are, however, discussed elsewhere [Chappell et al., 1997].
The task-level organization will not always be able to accommodate to agents entering or leaving, since it is meant to be efficient, not flexible. In these cases, the MLO regains control to reorganize the system. Other sorts of changes can also lead to reorganization. For example, the environment may change significantly, the mission can be changed by a user, or a task can fail. In these cases, some agent or agents in the TLO must detect the change. The agent can then either send a message up the hierarchy or attempt to initiate a reorganization without the participation of the top-level manager. The latter may be the case if the agent detecting the change has more information or is more intelligent than the top-level manager.
Figure 7 shows a reorganization protocol. When the top-level manager requests a reorganization, the MLO is immediately re-formed. Other agents follow a different protocol. First, they broadcast a message to ensure that all agents agree to the reorganization. If so, the MLO is re-formed. This protocol is tentative, and will be changed as work progresses.
MLO re-formation is identical to its initial formation. This is because the situation will likely have changed significantly since the last time the MLO existed. Consequently, we cannot rely on the presence of any of the MLO agents that participated previously. In the future, we will evaluate the usefulness of allowing the MLO to remain in existence while the TLO is controlling the system. This will likely decrease the time necessary to reorganize at the expense of increased bandwidth utilization during the mission.
A simulation testbed was created in which to develop and evaluate the approach described above. Instead of building the usual sort of AI simulator, in which the decision-making processes of individual agents is simulated in detail, we chose to create a rule-based simulator that focuses on the aggregate properties of a group of agents following the protocols. This allows us to focus on the protocols rather than on how the agents are implemented.
This approach has several advantages. Development time is saved by not concerning ourselves with the internal decision-making of agents. Time that would normally be spent designing and programming the agents is instead available for developing and evaluating the protocols. This is also in keeping with the approach being simulated, since this does not over-commit to the kinds of agents that will be in the simulated system: agents are treated as black boxes with well-defined behavior (i.e., as governed by the prototocols). The rule-based approach makes it very easy to implement new protocols or change existing ones, since protocols are readily implemented as sets of rules. This allows rapid testing of new ideas in the simulator. A very important benefit of this kind of simulator is that we can concentrate on evaluating the protocols without worrying about how the particular decision-making processes of the agents impacted the results. This type of simulator also allows higher-fidelity rules and algorithms to replace lower-fidelity versions as they become available.
The simulator is written in the CLIPS [Giarratano, 1993] forward-chaining rule-based system. There are approximately 270 rules currently in the simulator that implement the protocol simulation itself, the environment, vehicle motion, and discrete-event simulation capabilities. In addition, the simulator includes C and Lisp code. The CLIPS and C portions of the simulator are available on the Web. Figure 8 shows example output from the simulator.
As robots and other autonomous agents become more widely used, there will be a greater need for them to work cooperatively to accomplish complex, long-duration tasks. Often these systems of agents will have characteristics and requirements similar to those of autonomous oceanographic sampling networks: autonomous organization/reorganization will be needed, the system will be highly heterogeneous, its composition and tasks will change over time, communication bandwidth will be limited, and rigorous performance measures will have to be satisfied.
In this paper, we have discussed our approach to controlling such systems. We have developed a two-level organizational approach that addresses concerns of flexibility and efficiency without trading them off against one another. The task-level organization can be designed to be highly efficient, though inflexible, with the meta-level organization stepping in to reorganize when the situation changes.
We are currently developing and evaluating protocols that implement this approach. Future work will refine and extend the protocols based on the results of empirical simulation studies that are currently in progress. We will explore distributing the task assignment mechanisms across multiple MLO agents. Characteristics of organizational structures will be delineated, along with features of situations in which they are appropriate. This will allow the development of a mechanism for quickly selecting an appropriate organizational structure based on the current situation. In the longer term, we anticipate testing this approach in a fielded AOSN.
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 -t ICRA 98 paper - Copyright 1998 IEEE -local_icons -split 0 -address email@example.com body.tex.
The translation was initiated by Roy Turner on 6/8/1998