A Mathematical Theory of Cyber-Physical Systems

Abstract:

Overview. The fundamental challenge in cyber-physical systems is the confluence of distinct scientific and engineering models, methods, and tools for cyber and physical systems. Cyber systems are primarily about processing information, formally modeled as patterns of bits. Physical systems are primarily about structure and dynamics, the evolution of the state of the system in time. There are certainly connections between these models, methods, and tools. For example, cyber methods may be used to build simulations of physical systems, and physical systems (e.g. computers) are built to “execute” cyber models. These two connections are mutual imitation. A cyber simulation “imitates” a physical system, and an integrated circuit chip “imitates” a cyber model of data transformation. But the CPS problem is not about mutual imitation; it is about conjunction and collaboration. The cyber and the physical collaborate to render a system that is simultaneously cyber and physical. Today, we have mature theories of computation, developed over the last 80 years or so, and mature theories of physical structure and dynamics, developed over the last 300 years or so. But we have only the barest beginnings of theories that conjoin the two. The field of “hybrid systems,” nurtured by NSF since the 1990s, conjoins automata theory (a cyber theory) with differential equations (a physical theory). The field of “synchronous languages,” a primarily European phenomenon, conjoins concurrency (in the cyber sense) with synchrony (a physical concept). This project will expand on these fledgling efforts by developing cyber models of time (a physical concept), and physical models of computation (a cyber concept). Intellectual Merit. The 20-th century notion of computation, dating back to Turing and Church, is about transformations of data, not about dynamics, the evolution of a system in time. While spectacularly powerful for information processing, the 20th century computational methods, models, and tools are not well suited to cyber-physical systems. The physical notion of time, a complex and subtle concept that is central to physical dynamics, shows up in computing only very weakly in the form of precedences and weak concurrency models. This project proposes to build a 21st century theory of computation that embraces models of time, concurrency, and dynamics. The utility of such a theory depends critically, of course, on the faithfulness of its models to physical realizations, and on our ability to design and build physical realizations that are faithful to the models. These will be the metrics for success of the project. Broader Impact. A critical enabler for the industrial revolution and the 20th century transformation of humanity was the development of good mathematical models enabling prediction and analysis of structural strength of materials, motion of mechanical parts, mixing of fluids, etc. These models include notably linear systems theory, differential equations, and thermodynamics. A critical enabler for the digital revolution was also the development of good mathematical models for digital circuits, computer programs, and communication systems. These models include notably synchronous digital logic, models of computation (imperative, functional, logic, etc.), and coding theory. These two traditions, however, the models for physical systems and those for computational systems, remain separate and distinct. The next phase of human technological progress relies on bringing them together, so that cyber-physical systems can confront the daunting problems facing humanity today, like climate change, energy management, health, and education. This project intends major steps towards such a cyber-physical confluence.

Keywords: Models of computation, time, CPS, semantics, concurrency.
Primary Research Target Area: Science of Cyber-Physical Systems