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

Authors: Sims, Mark; Mostafa, Hala; Horling, Bryan; Zhang, Haizheng; Lesser, Victor; Corkill, Dan
Title: Lateral and Hierarchical Partial Centralization for Distributed Coordination and Scheduling of Complex Hierarchical Task Networks
Abstract: 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.
Keywords: Cooperative Negotiation, Coordination, Distributed Search, DTC, GPGP, Multi-Agent Systems, Scheduling
Publication: AAAI 2006 Spring Symposium on Distributed Plan and Schedule Management
Location: Stanford University
Date: March 2006
Sources: PDF: /Documents/msims/SS0604SimsM.pdf
PS: /Documents/msims/SS0604SimsM.ps.gz
Reference: Sims, Mark; Mostafa, Hala; Horling, Bryan; Zhang, Haizheng; Lesser, Victor; Corkill, Dan. Lateral and Hierarchical Partial Centralization for Distributed Coordination and Scheduling of Complex Hierarchical Task Networks. AAAI 2006 Spring Symposium on Distributed Plan and Schedule Management. March 2006.
bibtex: 
@article{Sims-423,
  author    = "Mark Sims and Hala Mostafa and Bryan Horling and
               Haizheng Zhang and Victor Lesser and Dan Corkill",
  title     = "{Lateral and Hierarchical Partial Centralization
               for Distributed Coordination and Scheduling of
               Complex Hierarchical Task Networks}",
  journal   = "AAAI 2006 Spring Symposium on Distributed Plan and
               Schedule Management",
  month     = "March",
  year      = "2006",
  address   = "Stanford University",
  url       = "http://mas.cs.umass.edu/paper/423",
}