Reformulating temporal plans for efficient execution
Nicola Muscettola, Paul H. Morris, Ioannis Tsamardinos · 1998
The Simple Temporal Network formalism permits significant flexibility in specifying the occurrence time of events in temporal plans. However, to retain this flexibility during execution, there is a need to propagate the actual execution times of past events so that the occurrence windows of future events are adjusted appropriately. Unfortunately, this may run afoul of tight real-time control requirements that dictate extreme efficiency. The performance may be improved by restricting the propagation. However, a fast, locally propagating, execution controller may incorrectly execute a consistent plan. To resolve this dilemma, we identify a class of dispatchable networks that are guaranteed to execute correctly under local propagation. We show that every consistent temporal plan can be reformulated as an equivalent dispatchable network, and we present an algorithm that constructs such a network. Moreover, the constructed network is shown to have a minimum number of edges among all such n...