Algorithms for Validation

A broad, rigorous introduction to algorithms for validating safety-critical systems.

Validation is a critical component of the development process for decision-making systems used in high-stakes settings, from autonomous vehicles and aviation to finance and healthcare. As these systems and their operating environments increase in complexity, understanding the full spectrum of possible behaviors becomes more difficult and requires a rigorous validation process. This comprehensive textbook presents a variety of computational methods for validating autonomous systems, introducing the underlying mathematical problem formulations and the algorithms for solving them. Unifying techniques from multiple fields under a common validation framework, it provides advanced undergraduate and graduate students objective strategies for validation. 

The text first covers techniques required to formulate validation problems in a common structure. It then addresses sampling-based failure analysis techniques such as falsification and failure probability estimation, followed by formal methods for reachability analysis, explainability, and runtime monitoring. Algorithmic implementations are provided throughout. 

• Offers unified framework for formulating validation problems 
• Presents both sampling-based and formal methods 
• Accessibly introduces failure probability estimation algorithms and reachability algorithms for linear, nonlinear, and discrete systems
• Emphasizes practical considerations for applying algorithms to real-world systems