Recovering from Inconsistency in Distributed Simple Temporal Networks

Abstract

Simple Temporal Networks (STNs) are frequently used in scheduling applications, as they provide a powerful and general tool for managing temporal constraints. One obstacle to their use in multi-agent scheduling contexts, however, is the additional problem of maintaining consistency across agent models. Like in centralized applications, unexpected execution results (e.g., an activity taking longer to execute than planned) can introduce conflicts into an agent's local model that require changes to its current local schedule. But in a distributed environment these local changes must also be propagated to those other agents with interdependent decisions, and the asynchrony and latency of this communication can introduce inter-agent inconsistency. In this paper, we consider the problem of managing and recovering from detected inconsistencies in a distributed STN-based scheduling framework. Our approach exploits a higher, domain-level semantics of the temporal constraints posted in the STN to design a set of strategies to update the agent's schedule and resolve the STN conflict. We present experimental results on a suite of problems involving coordinated management of joint schedules that indicate the potential of our approach.