Algorithmic Improvisation is a framework for adding randomness to a system's behavior to improve variety, robustness, or unpredictability while preserving safety. Its core computational problem, control improvisation (CI), extends traditional synthesis problems by allowing a new kind of specification: a randomness constraint which requires the system to exhibit a certain amount of randomness. Additionally, a probabilistic soft constraint allows fine-tuning of how randomness is added.
Algorithmic improvisation has a wide range of applications:
- computer improvisation of music: listen to some blues and jazz samples here
- robotic planning: see a drone patrol randomly in the video below (plus simulations here)
- lighting control mimicking human behavior: running your lights while you're on vacation
- black-box fuzz testing of software: combining mutational and generative fuzz testing
- simulation-based verification: generating interesting stimuli for cyber-physical systems (in the VerifAI toolkit)
- designing machine learning algorithms: generating synthetic training data in an intelligent way (using Scenic, a domain-specific probabilistic programming language)
For a comprehensive overview of algorithmic improvisation, see my thesis; our papers on its theory and applications are listed at the bottom of this page.
Improvising a Drone's Patrol Route
Below, a drone uses CI to generate randomized patrol routes. The leftmost white region represents a charging station, while the others indicate locations to surveil. Hovering over a location represents visiting it for surveillance. The hard specification is that all 5 locations must be visited, but none twice in a row, and that the drone can visit at most three locations before recharging. The soft constraint is that 80% of the time, each location should be visited exactly once. We generated a maximally-randomized improviser, which generates no route with probability greater than about 1/2000. Many thanks to Ankush Desai, Brent Schlotfeldt, Yasser Shoukry, and Dinesh Thakur for setting up this demo.
Papers on Algorithmic Improvisation
For a comprehensive overview of the history, theory, and applications of algorithmic improvisation as of 2019, see my thesis:
Algorithmic Improvisation.
[thesis]
Daniel J. Fremont.
Ph.D. dissertation, 2019 (University of California, Berkeley; Group in Logic and the Methodology of Science).
Our individual papers on various aspects of algorithmic improvisation are listed below.
Papers on the Theory of Algorithmic Improvisation:
Randomized Synthesis for Diversity and Cost Constraints with Control Improvisation.
[arXiv version]
Andreas Gittis*, Eric Vin*, and Daniel J. Fremont.
At CAV 2022 (the 34th International Conference on Computer-Aided Verification).
Entropy-Guided Control Improvisation.
[paper]
Marcell Vazquez-Chanlatte, Sebastian Junges, Daniel J. Fremont, and Sanjit A. Seshia.
At Robotics: Science and Systems 2021.
Reactive Control Improvisation.
[full version]
[experiments]
Daniel J. Fremont and Sanjit A. Seshia.
At CAV 2018 (the 30th International Conference on Computer-Aided Verification).
Control Improvisation.
[arXiv version]
Daniel J. Fremont, Alexandre Donzé, and Sanjit A. Seshia.
arXiv preprint, 2017. (extends the FSTTCS 2015 paper below)
Control Improvisation.
[arXiv version]
Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia, and David Wessel.
At FSTTCS 2015 (the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science).
(N.B. This preliminary version of the Control Improvisation paper has been substantially extended: see the 2017 version above.)
For an early version of the CI problem motivating these papers, see the ICMC 2014 paper below.
Papers on Applications of Algorithmic Improvisation:
Scenic: A Language for Scenario Specification and Data Generation.
[paper]
[tool and documentation]
Daniel J. Fremont, Edward Kim, Tommaso Dreossi, Shromona Ghosh, Xiangyu Yue, Alberto L. Sangiovanni-Vincentelli, and Sanjit A. Seshia.
In Machine Learning, February 2022.
(N.B. This extends our PLDI 2019 paper [full version here].)
Specification Mining for Machine Improvisation with Formal Specifications.
[doi]
Rafael Valle, Alexandre Donzé, Daniel J. Fremont, Ilge Akkaya, Sanjit A. Seshia, Adrian Freed, and David Wessel.
In Computers in Entertainment, Vol. 14, No. 3, 2016.
Control Improvisation with Probabilistic Temporal Specifications.
[arXiv version]
Ilge Akkaya, Daniel J. Fremont, Rafael Valle, Alexandre Donzé, Edward A. Lee, and Sanjit A. Seshia.
At IoTDI 2016 (the 1st International Conference on Internet-of-Things Design and Implementation).
(best paper award)
Machine Improvisation with Formal Specifications.
[preprint]
Alexandre Donzé, Rafael Valle, Ilge Akkaya, Sophie Libkind, Sanjit A. Seshia, and David Wessel.
At ICMC 2014 (the 40th International Computer Music Conference).