CAREER: Analysis and Synthesis of Systems over Finite Alphabets: Theoretical Foundations, Analytical Methods and Algorithmic Tools

Johns Hopkins University, Baltimore MD

Investigators

Abstract

Abstract: Cyber-physical systems comprising hardware interacting with control and computational units are omnipresent in our lives from high-tech cars to smart infrastructure. The tight interaction between analog and discrete dynamics gives rise to complex verification and synthesis problems. The challenge of synthesizing correct-by-design controllers for these systems remains daunting. This proposal presents an ambitious research agenda dedicated to fundamentally and holistically addressing this challenge. Specifically, we propose to develop a unifying framework built around the use of finite state automata as nominal models of both physical and computing processes. Intellectual Merit: The proposed research addresses fundamental problems at the interface of control theory, computer science and mathematics, potentially leading to transformative breakthroughs. Anticipated theoretical contributions include understanding the fundamental limitations of using finite memory models to approximate infinite memory systems, and developing analytical methods for establishing both a priori and a posteriori error bounds. Anticipated algorithmic contributions include developing efficient recursive schemes for constructing the approximate models as well as efficient techniques for solving specific combinatorial optimization problems. Finally, it is the hope that the ubiquitous problem of scalability can be finally overcome through the combined use of theoretical and algorithmic developments. Broader Impacts: The proposed research project would result in a computer-aided approach for systematically synthesizing cyber-physical systems in a verifiably correct manner, a freely distributed collection of software toolboxes, and a carefully crafted set of benchmark problems that can be used to evaluate and guide further research progress. The proposed research will drive the development of a new curriculum for undergraduate control education employing finite state automata as vehicles for introducing advanced control concepts. The research results will be incorporated in the development of a new graduate level course and manuscript on hybrid systems.