Lateral and Hierarchical Partial Centralization for Distributed Coordination and Scheduling of Complex Hierarchical Task Networks

Distributed Plan and Schedule Management

Volume

Papers from the 2006 AAAI Spring Symposium

Contents

We describe a new approach to coordinating the scheduling and execution of a complex hierarchical task structure distributed among a set of agents. Our approach decomposes allocation, scheduling, and monitoring into manageable local pieces that are coordinated with one another. Each agent is assigned mediator responsibilities for multiple tasks in the task structure so that each task has a mediator. We also establish mediator responsibilities to deal with task interrelationships that span portions of the task network located in different agents. In this mediator organization, each mediator is responsible for a small, tractable portion of the global scheduling and execution process. Mediators coordinate their allocation and scheduling decisions with other mediators, both hierarchically and laterally. Mediators communicate relevant local-agent activities using an abstract partial-order representation of resource availability and flexibility and combine these abstractions to make informed scheduling decisions for their portion of the global task structure. We detail how our approach operates in challenging hierarchical task settings, such as those being scheduled and executed in the DARPA COORDINATORS program, and we discuss how our approach differs from related techniques.