Integrated Multi-Agent Coordination

1. Introduction

Much work in multi-agent systems focuses on coordinating the activities of agents so that the end result approximates the solutions possible if one were to centralize the activities being carried out by these agents. Research into coordination has taken different forms: negotiation, scheduling, planning, organizational approaches, etc. Multi-agent coordination, defined as managing inter-dependencies between activities (Malone & Crowston, 1994), addresses the special issues arising from the relationships between multiple agents’ tasks. We define interdependency as a relationship between agents’ tasks, where the execution of one changes some performance-related characteristics associated with the other. This definition gives rise to the following questions: (1) how are the dependencies represented, and (2) how to manage these dependencies? Previous approaches, including GPGP (Generalized Partial Global Planning) (Decker & Li, 2000; Lesser, Decker & Wagner, 2004), have concentrated on high level solutions: keeping semi-coherence between agents’ activities, representing the relationships between actions and goals, and developing coordination interaction protocols. For example, POMDP approaches (Boutilier, Dean & Hanks, 1999) have been influential in evaluating how system states will be affected by certain actions and thus make suitable decisions based on probabilistic analysis. A recent distributed POMDP approach (Nair, Pynadath & Yokoo, etc. 2003) has been focused on deriving joint policies to maximize certain rewards for a multi-agent group. However, there has been less concern about how an individual agent’s internal task structures (i.e., hierarchically represented task network organization) and reasoning capabilities affect its coordination behaviors. In other words, our approach assumes that an intelligent agent is capable of managing its own activities (e.g., the general reasoning capabilities of AI planning) and it is the uncertainty in other agents’ behaviors that affect its reasoning capabilities. Thus, it may be advantageous for the involving agents to coordinate on the estimates of their task executions so that they could remove the uncertainties by employing other agents’ estimates. For example, Agent_A needs to finish a particular goal task consisting of both Task_A and Task_B and Task_B enables Task_A. Agent_A is able to carry out Task_A on its own, but Task_B can only be executed by Agent_B due to resource or capability constraints. Although Agent_A knows how long it will take for itself to finish Task_A, it cannot plan and schedule its own activities effectively since it is unknown how long it will take Agent_B to finish Task_B. Thus, before Agent_A starts its own task executions (keeping in mind that there may be other tasks for Agent_A), it is beneficial for Agent_A to ask Agent_B that what time Agent_B could be estimated to finish Task_B. Consequently, Agent_A can then plan and schedule its own activities with this estimated information. In particular, in order to understand the underlying assumptions, capabilities, and limitations of our approach, we need to formalize these linkages and relationships within the explicitly represented task structures.