Embracing Conflicts: Exploiting Inconsistencies in Distributed Schedules using Simple Temporal Network Representations

Abstract

Simple Temporal Networks (STNs) have gained increasing acceptance in scheduling applications, and provide key features for dealing with dynamic, uncertain execution environments. STNs provide strong support for flexible-times schedules, which can absorb some of the deviations encountered during schedule execution, lessening the need for rescheduling. Further, they lend assistance to incremental scheduling techniques, which revise the existing schedule instead of formulating a new solution from scratch. This reduces the changes from one schedule to the next, increasing stability. Despite these advantages, STNs have received scant attention in distributed scheduling. A key limitation has been that STNs require consistency of all temporal information: An inconsistent STN provides no solution. Unfortunately, consistency cannot be guaranteed in a distributed, dynamic, and uncertain environment, where agents frequently have conflicting information due to various factors (such as communication lags). Previous pproaches have concentrated on designing conservative schedules that do not encounter inconsistencies during execution. However, such guarantees are often impractical, and can lead to diminished performance. This thesis investigates three important issues surrounding the use of Simple Temporal Networks (STNs) in a distributed scheduling environment. We start by presenting strategies to recover from the inconsistent information that naturally arises during schedule execution, and restore the STN to a consistent state. We leverage the conflict analysis tools presented by the STN framework to detect, explain and resolve inconsistencies as they arise. Our strategies extend previous work on explaining STN conflicts in centralized scheduling domains, adapting this technology to the additional complexities presented by a distributed environment. We present a set of "local" and "non-local" conflict resolution actions that an agent can apply to resolve inconsistencies. Local actions make changes to the agent's local schedule. Non-local actions, on the other hand, make assumptions about other agent's activities, restoring consistency while waiting for updated information. Our results show that a team of agents using these conflict resolution actions significantly outperforms a second team of agent that makes conservative assumptions to prevent inconsistencies from arising during execution. Conflict explanation can also be used on inconsistencies encountered during the scheduling process to enhance the multi-agent schedule. This thesis develops strategies that increase the robustness of the schedule, and enable agents to update previous commitments they had made to each other. Assuming a model of durational uncertainty, we have developed Just-in-Time Backfilling (JIT-BF), a framework that monitors the scheduled activities that are close to execution for potential failures, and takes action to prevent these failures by scheduling redundant activities. JIT-BF extracts low-probability durations from the uncertainty model and inserts them into the STN in a "what-if" mode to see what would happen if the duration does occur. Inconsistencies point to potential impending failures. By analyzing the inconsistency, its effect on the schedule can be determined, and preventative action taken to reinforce the schedule. Our results show that a team of agents that uses JIT-BF significantly outperforms a reactive team of agents that recovers from inconsistencies once they arise. We conclude this thesis by presenting a conflict-driven coordination approach to updating existing temporal commitments between agents. When an agent fails to schedule a new activity because of conflicts with the scheduled activities of other agents, it can analyze the resulting inconsistency to discover what these conflicting activities are and by how much they need to move to allow the new activity to be scheduled. We present two alternative strategies that provide a trade-off between the amount of information an agent needs to initiate a coordination session, and the time needed for coordination. Our results show that agents using either strategy significantly outperform an agent team that unconditionally maintains inter-agent commitments once formed. Further, we show that agents using either strategy deliver equivalent performance, yet, the less information-heavy strategy significantly reduces the amount of communication at a negligible computational cost increase.