Integrated Multi-Agent Coordination

Integrated Multi-Agent Coordination

Wei Chen (Intelligent Automation, Inc., USA) and Keith S. Decker (University of Delaware, USA)
DOI: 10.4018/978-1-61520-605-6.ch003
OnDemand PDF Download:
List Price: $37.50


Planning and scheduling have been a key topic in both Operations Research and Multi-Agent Systems. Most approaches are concentrated at an abstract system level on developing interaction protocols to be imposed on agents. There has been less concern about how the internal task structures of individual agents affect these higher-level coordination behaviors. Collaborative multi-agent planning addresses problems like uncertainty in plan outcomes, anticipating likely contingencies, and evaluating how agent actions achieve worth-oriented goals. This article presents extensions and restrictions, called extended hierarchical task networks (EHTN), to the traditional plan and schedule representations that allow the formal definition of an integrated multi-agent coordination problem. This chapter discusses open issues in multi-agent coordination (e.g. what to coordinate among agents, how much information to be exchanged, how to evaluate a planning approach) and proposes a general solution towards successful distributed goal achievement by analyzing the task structures of participating agents.
Chapter Preview

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.

Complete Chapter List

Search this Book: