Embracing conflicts: Exploiting inconsistencies in distributed schedules using Simple Temporal Network representations

Simple Temporal Networks (STNs) provide key advantages in dealing with dynamic, uncertain schedule execution environments. However, they have received scant attention in distributed scheduling domains A key limitation has been that STNs require consistency of all temporal information for continued operation. Unfortunately, consistency cannot always be guaranteed, as agents frequently have conflicting information due to a variety of factors.;This thesis investigates three important issues surrounding the use of Simple Temporal Networks (STNs) in a distributed scheduling environment. We first present strategies to recover from the inconsistent information that naturally arises during schedule execution. We leverage the conflict analysis tools presented by the STN framework to detect, explain and resolve these inconsistencies. The conflict explanation produces an analysis of the inconsistency, identifying the conflicting temporal constraints. Using this analysis, we present a set of conflict resolution actions that an agent can use to restore its STN to a consistent state.;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. To enhance the fault-tolerance of a multi- agent schedule, we have developed Just-in-Time Backfilling (JIT-BF), a strategy for agents with a model of durational uncertainty to monitor their "close to execution" scheduled activities for potential failures, and take action to prevent these failures by scheduling redundant activities.;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, the resulting inconsistency can be analyzed 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 to perform these coordinated schedule updates. The strategies provide a trade-off between the amount of information an agent needs to initiate a coordination session, and the time needed for coordination.