Probabilistic plan verification through acceptance sampling
Abstract
CIRCA is an architecture for real-time intelligent control. The CIRCA
planner can generate plans that are guaranteed to maintain system
safety, given certain timing constraints. To prove that its plans
guarantee safety, CIRCA relies on formal verification methods.
However, in many domains it is impossible to build 100% guaranteed
safe plans, either because it requires more resources than available,
or because the possibility of failure simply cannot be eliminated. By
extending the CIRCA world model to allow for uncertainty in the form
of probability distribution functions, we can instead generate plans
that maintain system safety with high probability. This paper
presents a procedure for probabilistic plan verification to ensure
that heuristically-generated plans achieve the desired level of
safety. Drawing from the theory of quality control, this approach
aims to minimize verification effort while guaranteeing that at most a
specified proportion of good plans are rejected and bad plans
accepted.
Sample citation
Håkan L. S. Younes and
David J. Musliner. 2002.
Probabilistic plan verification through acceptance sampling. In
Proceedings of the AIPS-02 Workshop on Planning via Model Checking, edited by Froduald Kabanza and Sylvie Thiébaux, 81–88, Toulouse, France.
Full paper (8 pages, 21 references)
Presentation (27 slides)