Algorithms for Deciding the Safety of States in Fully Observable Non-deterministic Problems

---

Suppose you have a learned policy for a Fully Observable Non-deterministic (FOND) problem. How can you be sure that it is safe? One approach is via fault analysis, which relies on algorithms that find whether individual states are safe or not. This work shows that the existing state-of-the-art algorithm for this has an exponential worst-case time complexity, and then we present a practical alternative.

---

ICAPS 2026 Short Paper

This short paper was accepted at ICAPS 2026!

---

Technical Report [arxiv]

Extended version of the paper with more experimental results in the appendix.

---

Source Code, Benchmarks, and Data [zenodo] [github]

The code, benchmarks, and experimental results are all here.