CPS: Breakthrough: Control Improvisation for Cyber-Physical Systems

Abstract: Inspired by the manner in which humans improvise in everyday life, this NSF project is creating a theory of algorithmic improvisation for cyber-physical systems design. It is developing a mathematical framework, supported by tools, to address the challenge of designing systems that adapt to uncertainty in their operating environment and to changing requirements. Moreover, this framework has broad relevance to many fields in computer science and engineering. Results from the proposed work are being incorporated into teaching, with a particularly strong impact on courses at UC Berkeley on cyber-physical systems and formal methods, and on undergraduate projects conducted under broader outreach programs at UC Berkeley. Additionally, through collaborations with industry partners, the project is improving the state of the art in verification and control in the cyber-physical systems industry. Uncertainty in the design process, in the behavior of sub-systems that evolve over time, and in the operating environment remains a challenge for CPS design. There is a need to design automatic controllers that improvise to handle challenging situations as a skilled human would. This project addresses this need with a foundation approach that is developing a theoretically-sound definition of algorithmic improvisation that is also grounded in practice. It is exploring the full range of variations of the problem definition, analyzing their computational complexity, and devising efficient algorithms where shown to be theoretically possible. Additionally, it is developing new applications to verification, in novel algorithms for simulation-driven verification and verification of machine learning components, and to control, using improvisation for randomized robot path planning and for controlled exploration in adaptive, learning-based control. Together, this tight combination of theoretical work and practical applications seeks to break new ground in the science of cyber-physical systems.