  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.
