Foundations and Trends® in Systems and Control > Vol 10 > Issue 3-4

Formal Methods for Autonomous Systems

By Tichakorn Wongpiromsarn, Iowa State University, USA, nok@iastate.edu | Mahsa Ghasemi, Purdue University, USA, mahsa@purdue.edu | Murat Cubuktepe, The University of Texas at Austin, USA | Georgios Bakirtzis, The University of Texas at Austin, USA | Steven Carr, The University of Texas at Austin, USA | Mustafa O. Karabag, The University of Texas at Austin, USA | Cyrus Neary, The University of Texas at Austin, USA | Parham Gohari, The University of Texas at Austin, USA | Ufuk Topcu, The University of Texas at Austin, USA, utopcu@utexas.edu

 
Suggested Citation
Tichakorn Wongpiromsarn, Mahsa Ghasemi, Murat Cubuktepe, Georgios Bakirtzis, Steven Carr, Mustafa O. Karabag, Cyrus Neary, Parham Gohari and Ufuk Topcu (2023), "Formal Methods for Autonomous Systems", Foundations and TrendsĀ® in Systems and Control: Vol. 10: No. 3-4, pp 180-407. http://dx.doi.org/10.1561/2600000029

Publication Date: 21 Sep 2023
© 2023 T. Wongpiromsarn et al.
 
Subjects
Optimal control,  Verification,  Behavioral synthesis,  Software model checking,  Algorithmic game theory,  Computational complexity
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Models and Specifications
3. Verification and Model Checking
4. Closed-System Synthesis
5. Reactive Synthesis
6. Probabilistic Synthesis and Verification
7. Dealing with Information Limitations
8. Runtime Assurance via Shielding
9. Verifiable Learning-Based Synthesis
10. Some Future Directions
Acronyms
Acknowledgements
References

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.

DOI:10.1561/2600000029
ISBN: 978-1-63828-272-3
246 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-63828-273-0
246 pp. $300.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Models and Specifications
3. Verification and Model Checking
4. Closed-System Synthesis
5. Reactive Synthesis
6. Probabilistic Synthesis and Verification
7. Dealing with Information Limitations
8. Runtime Assurance via Shielding
9. Verifiable Learning-Based Synthesis
10. Some Future Directions
Acronyms
Acknowledgements
References

Formal Methods for Autonomous Systems

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.

In this monograph the authors review the current state of the art of applications of formal methods in the autonomous systems domain. They first consider correct-by-construction synthesis under various formulations in known environments before addressing the concept of uncertainty with systems that employ learning using formal methods including overcoming some limitations of such systems. Finally, they examine the synthesis of systems with monitoring to ensure a system can return to normalcy. They conclude with future directions for formal methods in reinforcement learning, uncertainty, privacy, explainability of formal methods, and regulation and certification.

Covering important topics such as synthesis and reinforcement learning it is a comprehensive resource for students, practitioners and researchers on the use of formal methods in modern systems.

 
SYS-029