Carnegie Mellon University
Distributed Management of Flexible Times Schedules

Stephen Smith, Anthony T. Gallagher, Terry Lyle Zimmerman, Laura Barbulescu, and Zack Rubinstein
2007 Intl conf on Autonomous Agents and Multiagent Systems (AAMAS), May, 2007.

  • Adobe portable document format (pdf) (364KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

In this paper we consider the problem of managing and exploiting schedules in an uncertain and distributed environment. We assume a team of collaborative agents, each responsible for executing a portion of a globally pre-established schedule, but none possessing a global view of either the problem or solution. Each individual agent is aware of dependencies between its scheduled actions and those of other agents (providing a basis for online coordination), and each agent is also provided with a set of local contingency (fall-back) options. The goal is to maximize the joint quality obtained from the actions executed by all agents, given that unexpected events will force changes to some prescribed actions and reduce the utility of executing others as execution unfolds. We describe an agent architecture for solving this problem that couples two basic mechanisms: (1) a ``flexible times'' representation of the agent's schedule (using a Simple Temporal Network (STN)), which hedges against temporal uncertainty by promoting execution from a set of feasible solutions, and (2) an incremental rescheduling procedure, which acts to revise the agent's schedule when execution is forced outside of this set of solutions or when execution events reduce the expected value of this feasible solution set. Two layers of coordination augment this core local problem-solving infrastructure. Basic coordination with other agents is achieved simply by communicating schedule changes to those agents with inter-dependent actions. Then, as time permits, the STN is used to drive an inter-agent option generation and query process, aimed at identifying opportunities for solution improvement through joint change. Using a simulator to model the uncertain execution environment, we compare the performance of our multi-agent system with an expected optimal (but non-scalable) centralized MDP solver over a range of problem instances.

multi-agent scheduling, uncertainty

Sponsor: DARPA Coordinators
Grant ID: FA8750-05-C-0033
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory
Associated Project(s): Coordinators
Number of pages: 8

Text Reference
Stephen Smith, Anthony T. Gallagher, Terry Lyle Zimmerman, Laura Barbulescu, and Zack Rubinstein, "Distributed Management of Flexible Times Schedules," 2007 Intl conf on Autonomous Agents and Multiagent Systems (AAMAS), May, 2007.

BibTeX Reference
   author = "Stephen Smith and Anthony T Gallagher and Terry Lyle Zimmerman and Laura Barbulescu and Zack Rubinstein",
   title = "Distributed Management of Flexible Times Schedules",
   booktitle = "2007 Intl conf on Autonomous Agents and Multiagent Systems (AAMAS)",
   month = "May",
   year = "2007",