Fast Dynamic Scheduling of Disjunctive Temporal Constraint Networks through Incremental Compilation

All Papers

Autonomous systems operating in real-world environments must plan, schedule, and execute missions while robustly adapting to uncertainty and disturbance. One way to mitigate the effect of uncertainty and disturbance is to dynamically schedule the plan online, through dispatchable execution. Dispatchable execution increases the efficiency of plan execution by introducing (1) a compiler that reduces a plan to a dispatchable form that enables real-time scheduling, and (2) a temporal plan dispatcher that schedules start times of activities (or controllable events) dynamically in response to disturbances. Previous work addresses efficient dispatchable execution of plans described as Simple Temporal Problems (STPs). While STPs have proven useful for many applications, Temporal Constraint Satisfaction Problems (TCSPs) provide a more rich language by introducing disjunctive constraints. However, previous approaches to dispatchable execution of disjunctive temporal plans are intractable for moderately-sized problems. The key contribution of this paper is an efficient algorithm for compiling and dynamically scheduling TCSPs. We present an incremental algorithm that compiles a TCSP to a compact representation, encoding the solution set in terms of the differences among solutions. We empirically demonstrate that this novel encoding reduces the space to encode the solution set by up to three orders of magnitude compared to prior art, and supports fast dynamic scheduling.