Distributed Management of Flexible Times Schedules

Abstract

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.