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 guar- anteed to maintain system with a sufficiently high probabil- ity. For many such domains, bounds on system safety can- not 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 fre- quently involve verifying that the probability of failure is be- low a low threshold ( < 0.01 ). Because the events we sam- ple have such low probabilities, we use Importance sam- pling (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 representa- tion and achieve a better bias.