Towards Efficient Anytime Computation and Execution of Decoupled Robustness Envelopes for Temporal Plans
This addresses inefficiencies in practical planning applications by enabling more robust execution, though it is incremental as it builds on existing robustness envelope concepts.
The paper tackles the problem of costly re-planning in model-based planning by approximating Robustness Envelopes, which characterize contingencies a plan can handle without re-planning, resulting in a scalable algorithm that reduces re-planning instances in a case study.
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.