Coordination is the process of managing interdependencies between activities. The lack of effective cooperation can lead to significant degradation in system performance due to inefficient and wasteful use of resources, missed deadlines and even the inability to solve the problem. Coordination behaviors can be divided roughly into specification behaviors (creating shared goals), planning behaviors (expressing potential sets of tasks or strategies to accomplish goals), and scheduling behaviors (assigning tasks to groups or individuals, creating shared plans and schedules, allocating resources, etc.). This research is primarily concerned with scheduling behaviors. By concentrating on this aspect of coordination, it is possible to construct coordination approaches that are generic (i.e. not specific to the agent architecture and its problem-solving paradigm nor to the application domain) and to make more general statements about the effectiveness of different coordination strategies based on the characteristics of the operating environment.
Our approach to coordination has evolved from our work on Partial Global Planning (PGP). In this work, as implemented in the Distributed Vehicle Monitoring Testbed (DVMT) environment, agent coordination is improved by scheduling the timely generation of partial results, avoiding redundant activities, and shifting tasks to idle nodes. In making it domain independent, we realized that the basis of PGP is the ability to recognize and react to quantitative relationships among tasks of different agents. One example of such a relationship is facilitates which indicates that the results of one task if used by another task will provide valuable information/constraints so that the task will either produce a higher quality result or take less time to execute. Understanding the quantitative characteristics of this task relationship allows us to determine how important it is to coordinate agent activity so that this potential facilitating activity among agents actually occurs. From this perception, we developed TAEMS which is a domain independent language for modeling agent task structures and their relationships. Another insight was that appropriate coordination among agents could be achieved through the creation and refinement of an agent's local scheduling constraints (modulating local control) in response to the recognition of relationships among tasks of different agents. In the above example of the facilitates relationship, the local scheduling constraints involve trying to set up a scheduling relationship (commitment) among agents so that the facilitating task completes execution and transfer its results prior to the initiation of the facilitated task.
This led to the development of GPGP: Generic Partial Global Planning which is a distributed and domain independent approach to real-time coordination among collaborative agents. It consists of a set of domain-independent coordination mechanisms associated with each agent that posts constraints to the local real-time scheduler about the importance of certain tasks and appropriate times for their initiation and completion. Each coordination mechanism is defined as a response to certain features in the current task environment. In order to construct a generic approach to coordination, it is necessary to have an underlying framework that can represent the wide diversity of tasks, task properties, and task relationships in order to arrive at effective coordination among the activities of different agents in a wide variety of domains.
This research involves further work on the development of this domain independent approach to real-time, distributed coordination of multiple agents. We are extending GPGP in the following significant ways. In order to be able to model a wider set of task domains, the TAEMS framework is being extended to explicitly represent uncertainty about the duration and quality that tasks can achieve and uncertainty about the quantitative characteristics of the relationship among tasks in the task structure. We have also added in cost to the representation and more complex criteria for specifying tradeoffs among these different aspect of agent activities. In order to be more responsive to the characteristics of the environment and the specifics of the task structure, situation-specific coordination mechanisms are being introduced. Coordination mechanisms will be able to be turned on and off depending on both static characteristics of the application and dynamic characteristics involving the specific tasks that are encountered and meta-characteristics such as load in the system. Additionally, new coordination mechanisms are being developed that are both more sophisticated and less than the current set. This set of extensions will permit the system to dynamically tradeoff overhead in coordination for more or less coherent behavior; the decrease in resources used as a result of more coherent agent behavior may not always warrant the coordination overhead to achieve such a behavior. Finally, we are introducing a learning component into GPGP that allows the system to construct on-line, situation-specific coordination strategies. The hoped for result of this work will be the development of a generic coordination module which developers of multiagent systems can use to build coordination strategies.
See the following WWW pages for more details: http://dis.cs.umass.edu/research/gpgp.html, http://dis.cs.umass.edu/research/taems-learn.html, and http://dis.cs.umass.edu/research/dtc.html.