Towards Efficient Anytime Computation and Execution of Decoupled Robustness Envelopes for Temporal Plans

Cashmore, Michael and Cimatti, Alessandro and Magazzeni, Daniele and Micheli, Andrea and Zehtabi, Parisa (2019) Towards Efficient Anytime Computation and Execution of Decoupled Robustness Envelopes for Temporal Plans. Working paper. arXiv.org, Ithica, N.Y..

[img]
Preview
Text (Cashmore-etal-Arxiv-2019-Towards-Efficient-Anytime-Computation-and-Execution-of-Decoupled-Robustness-Envelopes)
Cashmore_etal_Arxiv_2019_Towards_Efficient_Anytime_Computation_and_Execution_of_Decoupled_Robustness_Envelopes.pdf
Final Published Version

Download (357kB)| Preview

    Abstract

    One of the major limitations for the employment of model-based planning and scheduling in practical applications is the need of costly re-planning when an incongruence between the observed reality and the formal model is encountered during execution. Robustness Envelopes characterize the set of possible contingencies that a plan is able to address without re-planning, but their exact computation is extremely expensive; furthermore, general robustness envelopes are not amenable for efficient execution. In this paper, we present a novel, anytime algorithm to approximate Robustness Envelopes, making them scalable and executable. This is proven by an experimental analysis showing the efficiency of the algorithm, and by a concrete case study where the execution of robustness envelopes significantly reduces the number of re-plannings.