TL;DR
DARSY is an open-source Python tool that synthesizes control policies with formal "Probably Approximately Correct" (PAC) guarantees for stochastic systems with unknown dynamics. By combining data-driven abstractions (Interval MDPs) with robust dynamic programming, it allows researchers to bridge the gap between black-box simulators and formal verification.
What Problem Does This Paper Address?
Formal policy synthesis aims to create control strategies that guarantee a system will satisfy a specific requirement—like a robot reaching a goal while avoiding obstacles—with a high probability. Traditionally, this requires a "white-box" mathematical model of the system's dynamics and noise.
However, real-world systems (like drones or complex chemical processes) are often too messy to model exactly. We might only have access to a simulator or historical data. While reinforcement learning can handle these "black-box" scenarios, it rarely provides the rigorous safety guarantees required for critical applications. DARSY addresses this by creating a bridge: it uses data samples to build a formal abstraction that accounts for uncertainty, providing certified lower bounds on the probability of success even when the underlying equations are unknown.
Methods
DARSY transforms a continuous, unknown stochastic system into a finite, discrete abstraction called an Interval Markov Decision Process (IMDP).
- Data-Driven Abstraction: Instead of exact transition probabilities, DARSY calculates intervals (lower and upper bounds) for transitions between states. It uses a known Lipschitz constant (a measure of how "smooth" the dynamics are) and statistical techniques (Clopper-Pearson intervals) to ensure these bounds are sound with a user-defined confidence level ($\beta$).
- Two-Layer IMDP (2IMDP): A key innovation is the support for 2IMDPs. By grouping states into "blocks" and bounding transitions at both the state and block levels, DARSY can produce much tighter probability bounds than standard IMDPs, especially in data-sparse regions.
- Two-Phase Sampling: To keep the abstraction efficient, DARSY uses a clever two-phase approach. The first batch of samples identifies "candidate" successor states, and the second batch estimates the probabilities. This prevents the model from becoming an overly conservative "dense" graph where every state can transition to every other state.
- Formal Specifications: Users define tasks using syntactically co-safe Linear Temporal Logic (scLTL). DARSY uses the
Spotlibrary to convert these logic formulas into Deterministic Finite Automata (DFA). - Robust Synthesis: The tool performs robust dynamic programming on the product of the abstraction and the DFA to find the optimal policy and the certified PAC lower bound on the satisfaction probability.
Datasets
The authors evaluated DARSY on 13 benchmarks derived from 10 different stochastic systems, ranging from 1 to 4 dimensions:
- Linear Systems: Temp1D through Temp4D (room temperature control) and DoubleInt (double integrator).
- Nonlinear Systems: MountainCar (classic RL benchmark), Pendulum (with both triangular and Gaussian noise), and Dubins Car (2D and 3D versions).
- Noise Types: The benchmarks include additive and multiplicative noise with various distributions (Gaussian, Truncated Gaussian, and Triangular).
Key Insights and Ideas
- The Power of Lipschitz Continuity: You don't need to know the equations if you know how much they can "wiggle." The Lipschitz constant allows DARSY to extrapolate from a single data point to a whole region of the state space safely.
- Sparsity is Safety: Standard data-driven methods often result in "dense" abstractions where every transition is possible (with low probability). This leads to extreme conservatism. DARSY’s two-phase sampling (illustrated below) keeps the model sparse, which paradoxically leads to higher (better) certified lower bounds.
- JAX Integration: By implementing the core algorithms in JAX, the authors enable just-in-time (JIT) compilation and vectorized computation, making the tool fast enough to handle abstractions with hundreds of thousands of states and millions of transitions.
Key Results
- Tight Guarantees: In the "Pendulum-G" benchmark, the 2IMDP abstraction improved the certified lower bound ($\lambda$) from 0.622 (standard IMDP) to 0.743 using 100k samples.
- Sample Efficiency: The tool demonstrates a clear "sweet spot" for sampling. While more samples always improve the bound, the gains eventually become marginal compared to the increased abstraction time.
- Scalability: DARSY successfully handled the
Temp4Dsystem, creating an abstraction with over 20,000 states and 430 million transitions. - Non-Uniform Grids: To ensure the abstraction is "label-preserving" (i.e., every point in a grid cell has the same label like "goal" or "unsafe"), DARSY automatically refines user-requested grids into non-uniform partitions.
Limitations and Future Work
- The Lipschitz Requirement: DARSY requires a Lipschitz constant. While these can be estimated from data or expert knowledge, an incorrect constant breaks the formal soundness of the tool.
- Curse of Dimensionality: Like all abstraction-based methods, the number of states grows exponentially with the system's dimension. The current tool is effective up to 4 or 5 dimensions.
- Future Directions: The authors plan to extend DARSY to "gray-box" settings where some partial knowledge of the dynamics is available. They also aim to leverage GPU acceleration via JAX to scale to even higher-dimensional systems and finer grid resolutions.
Summary updated