Probabilistic Model Checking and Autonomy

Marta Kwiatkowska, Gethin Norman, David Parker

Abstract

Design and control of autonomous systems that operate in uncertain or adversarial environments can be facilitated by formal modelling and analysis. Probabilistic model checking is a technique to automatically verify, for a given temporal logic specification, that a system model satisfies the specification, as well as to synthesise an optimal strategy for its control. This method has recently been extended to multi-agent systems that exhibit competitive or cooperative behaviour modelled via stochastic games and synthesis of equilibria strategies. In this paper, we provide an overview of probabilistic model checking, focusing on models supported by the PRISM and PRISM-games model checkers. This includes fully observable and partially observable Markov decision processes, as well as turn-based and concurrent stochastic games, together with associated probabilistic temporal logics. We demonstrate the applicability of the framework through illustrative examples from autonomous systems. Finally, we highlight research challenges and suggest directions for future work in this area.

Introduction

As autonomous systems—from self-driving cars to warehouse robots—become more integrated into our lives, the stakes for their reliability skyrocket. Traditional testing is often insufficient because these systems operate in "messy" environments characterized by uncertainty (noisy sensors), partial information (hidden states), and strategic interactions (multi-agent competition or cooperation).

Probabilistic Model Checking (PMC) addresses these challenges by providing formal guarantees. Instead of relying solely on empirical testing, PMC allows researchers to mathematically prove that the probability of a critical failure is below a certain threshold. Crucially, it enables strategy synthesis, automatically generating the control logic required to ensure these safety and performance requirements are met.

Modeling Frameworks for Autonomous Systems

The applicability of PMC depends on the complexity of the system and its environment. The paper categorizes modeling into four primary frameworks supported by tools like PRISM and PRISM-games:

  • Markov Decision Processes (MDPs): The baseline for modeling a single agent making decisions in a stochastic environment.
  • Partially Observable MDPs (POMDPs): These account for sensor noise, where the agent maintains a "belief" (a probability distribution) about its current state rather than knowing it exactly.
  • Turn-based Stochastic Games (TSGs): These model multi-agent scenarios where players take turns, allowing for reasoning about coalitions of agents working against an adversary.
  • Concurrent Stochastic Games (CSGs): The most complex model, where agents act simultaneously. This requires finding Nash Equilibria—strategies where no player can improve their outcome unilaterally.
A 3x2 grid world modeled as a Markov Decision Process (MDP), illustrating states, probabilistic transitions, and labeled objectives.

Key Insights and Strategy Synthesis

A core strength of the PMC framework is its ability to handle multi-objective specifications. In real-world robotics, designers often face trade-offs between conflicting goals, such as minimizing energy consumption while maximizing safety. By using multi-objective model checking, researchers can identify the Pareto front—the set of optimal strategies where no objective can be improved without degrading another.

A 3D Pareto front visualizing the trade-offs between energy consumption, target reachability probability, and collision probability for a robotic rover.

Practical results demonstrate the impact of these methods:

  • Energy Efficiency: In rover experiments, PMC-synthesized strategies saved 60% to 75% of energy compared to standard approaches by optimizing sensor usage while maintaining 100% safety guarantees.
  • Human-in-the-loop: TSG models have successfully quantified trade-offs between mission time and safety based on varying levels of human operator accuracy.

Future Directions

While PMC provides a robust safety net, several challenges remain. The "state-space explosion" problem makes verification of very large systems computationally expensive. Future research is directed toward combining the learning capabilities of Reinforcement Learning (RL) with the formal guarantees of PMC, as well as improving the efficiency of equilibrium computation in concurrent games. Bridging the gap between high-level formal models and low-level neuro-symbolic reasoning represents the next frontier for ensuring the safety of autonomous systems.

Summary updated

Abstract

Design and control of autonomous systems that operate in uncertain or adversarial environments can be facilitated by formal modelling and analysis. Probabilistic model checking is a technique to automatically verify, for a given temporal logic specification, that a system model satisfies the specification, as well as to synthesise an optimal strategy for its control. This method has recently been extended to multi-agent systems that exhibit competitive or cooperative behaviour modelled via stochastic games and synthesis of equilibria strategies. In this paper, we provide an overview of probabilistic model checking, focusing on models supported by the PRISM and PRISM-games model checkers. This includes fully observable and partially observable Markov decision processes, as well as turn-based and concurrent stochastic games, together with associated probabilistic temporal logics. We demonstrate the applicability of the framework through illustrative examples from autonomous systems. Finally, we highlight research challenges and suggest directions for future work in this area.
BibTeX
@inproceedings{kwiatkowska2022probabilistic,
  author = {Marta Kwiatkowska and Gethin Norman and David Parker},
  title = {{Probabilistic Model Checking and Autonomy}},
  booktitle = {Annu. Rev. Control. Robotics Auton. Syst},
  year = {2022},
  url = {https://openreview.net/forum?id=NlI74cn6fA},
}
Figure