Graphics enhanced version of this site

Distributed Management of Flexible Times Schedules
S. Smith, A.T. Gallagher, T.L. Zimmerman, L. Barbulescu, and Z. Rubinstein
2007 Intl conf on Autonomous Agents and Multiagent Systems (AAMAS), May, 2007.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [363 KB]

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.

Sponsor: DARPA Coordinators
Grant ID: FA8750-05-C-0033

Associated center: CIMDS
Associated lab/group: Intelligent Coordination and Logistics Laboratory
Associated project: Coordinators

Number of pages: 8

S. Smith, A.T. Gallagher, T.L. Zimmerman, L. Barbulescu, and Z. Rubinstein, "Distributed Management of Flexible Times Schedules," 2007 Intl conf on Autonomous Agents and Multiagent Systems (AAMAS), May, 2007.

@inproceedings{Smith_2007_5707,
   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"
}