Formal Methods for Autonomous Systems

Abstract

Formal methods refer to rigorous, mathematical approaches to system development and have played a key role in establishing the correctness of safety-critical systems. The main building blocks of formal methods are models and specifications, which are analogous to behaviors and requirements in system design and give us the means to verify and synthesize system behaviors with formal guarantees. This monograph provides a survey of the current state of the art on applications of formal methods in the autonomous systems domain. We consider correct-by-construction synthesis under various formulations, including closed systems, reactive, and probabilistic settings. Beyond synthesizing systems in known environments, we address the concept of uncertainty and bound the behavior of systems that employ learning using formal methods. Further, we examine the synthesis of systems with monitoring, a mitigation technique for ensuring that once a system deviates from expected behavior, it knows a way of returning to normalcy. We also show how to overcome some limitations of formal methods themselves with learning. We conclude with future directions for formal methods in reinforcement learning, uncertainty, privacy, explainability of formal methods, and regulation and certification.

References in corpus (20)

• Adam: A Method for Stochastic Optimization
• Fundamentals of Recurrent Neural Network (RNN) and Long Short-Term Memory (LSTM) Network
• Deep Recurrent Q-Learning for Partially Observable MDPs
• Memory-based control with recurrent neural networks
• Qualitatively characterizing neural network optimization problems
• Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning
• Deep Neural Network Compression for Aircraft Collision Avoidance Systems
• Solving POMDPs by Searching the Space of Finite Policies
• Privacy in Deep Learning: A Survey
• Successive Convexification: A Superlinearly Convergent Algorithm for Non-convex Optimal Control Problems
• Human Trust-based Feedback Control: Dynamically varying automation transparency to optimize human-machine interactions
• Learning Efficient Multi-agent Communication: An Information Bottleneck Approach
• Optimal Temporal Logic Planning in Probabilistic Semantic Maps
• Deception in Supervisory Control
• Trust-Aware Decision Making for Human-Robot Collaboration: Model Learning and Planning
• Low-Effort Specification Debugging and Analysis
• Robust Predictable Control
• On the Complexity of Reachability in Parametric Markov Decision Processes
• A Coordinated MDP Approach to Multi-Agent Planning for Resource Allocation, with Applications to Healthcare
• Dynamic Certification for Autonomous Systems