Recovering from inconsistency in distributed simple temporal networks

Simple Temporal Networks (STNs) are frequently used in scheduling applications, as they provide a powerful and gen-eral 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 exe-cution 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 dis-tributed environment these local changes must also be prop-agated to those other agents with interdependent decisions, and the asynchrony and latency of this communication can introduce inter-agent inconsistency. In this paper, we con-sider the problem of managing and recovering from detected inconsistencies in a distributed STN-based scheduling frame-work. Our approach exploits a higher, domain-level seman-tics 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 sched-ules that indicate the potential of our approach