Abstract
Many systems depend on randomness to achieve robustness, variety, or unpredictability. For example, a synthetic data generator for a machine learning algorithm can use randomness to produce diverse training data, and a security robot can use randomness to make its patrol route less predictable. When synthesizing such systems, we must ensure not only that the system satisfies its functional requirements but that its behavior is sufficiently random: that is, having random behavior is part of the system's specification. This new type of specification requires new synthesis algorithms.
In this talk, I will present Algorithmic Improvisation, a mathematical framework for the correct-by-construction synthesis of randomized systems. I will give an overview of the framework, outlining the core computational problem, its extension to reactive systems, the theory of its solvability and complexity, and efficient synthesis algorithms. I will also describe applications of algorithmic improvisation we have explored in a variety of fields, including robotics, cyber-physical systems, computer music, and machine learning.