The Mathematics of Dispatchability Revisited. Morris, P. In
The Mathematics of Dispatchability Revisited [link]Paper  abstract   bibtex   
Dispatchability is an important property for the efficient execution of temporal plans where the temporal constraints are represented as a Simple Temporal Network (STN). It has been shown that every STN may be reformulated as a dispatchable STN, and dispatchability ensures that the temporal constraints need only be satisfied locally during execution. Recently, it has also been shown that Simple Temporal Networks with Uncertainty, augmented with wait edges, are Dynamically Controllable provided every projection is dispatchable. Thus, the dispatchability property has both theoretical and practical interest. One thing that hampers further work in this area is the under-developed theory. The existing definitions are expressed in terms of algorithms, and are less suitable for mathematical proofs. In this paper, we develop a new formal theory of dispatchability in relation to execution. We exploit this to prove characterizations of dispatchability, including in terms of the structural properties of the STN graph. This facilitates the potential application of the theory to other areas.
@inproceedings {icaps16-117,
    track    = {​Main Track},
    title    = {The Mathematics of Dispatchability Revisited},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13002},
    author   = {Paul Morris},
    abstract = {Dispatchability is an important property for the efficient execution of temporal plans where the temporal constraints are represented as a Simple Temporal Network (STN).  It has been shown that every STN may be reformulated as a dispatchable STN, and dispatchability ensures that the temporal constraints need only be satisfied locally during execution.  Recently, it has also been shown that Simple Temporal Networks with Uncertainty, augmented with wait edges, are Dynamically Controllable provided every projection is dispatchable.  Thus, the dispatchability property has both theoretical and practical interest.

One thing that hampers further work in this area is the under-developed theory.  The existing definitions are expressed in terms of algorithms, and are less suitable for mathematical proofs. In this paper, we develop a new formal theory of dispatchability in relation to execution.  We exploit this to prove characterizations of dispatchability, including in terms of the structural properties of the STN graph.  This facilitates the potential application of the theory to other areas.},
    keywords = {Scheduling,Scheduling under uncertainty,Execution; monitoring and repair,Temporal planning}
}
Downloads: 0