Improving Trust Estimates in Planning Domains with Rare Failure Events

摘要

In many planning domains, it is impossible to construct plans that are guaranteed to keep the system completely safe. A common approach is to build probabilistic plans that are guaranteed to maintain system with a sufficiently high probability. For many such domains, bounds on system safety cannot be computed analytically, but instead rely on execution sampling coupled with a plan verification techniques. While probabilistic planning with verification can work well, it is not adequate in situations in which some modes of failure are very rare, simply because too many execution traces must be sampled (e.g., 1012) to ensure that the rare events of interest will occur even once. The P-CIRCA planner seeks to solve planning problems while probabilistically guaranteeing safety. Our domains frequently involve verifying that the probability of failure is below a low threshold (< 0.01). Because the events we sample have such low probabilities, we use Importance sampling (IS) (Hammersley and Handscomb 1964; Clarke and Zuliani 2011) to reduce the number of samples required. However, since we deal with an abstracted model, we cannot bias all paths individually. This prevents IS from achieving a correct bias. To compensate for this drawback we present a concept of DAGification to partially expand our representation and achieve a better bias.