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 moderatelysized
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.