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 ImprovisationFor a comprehensive overview of the history, theory, and applications of algorithmic improvisation, see my 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:
Daniel J. Fremont, Alexandre Donzé, and Sanjit A. Seshia.
arXiv preprint, 2017. (extends the FSTTCS 2015 paper below)
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 Scene Generation.
[2018 tech report]
Daniel J. Fremont, Tommaso Dreossi, Shromona Ghosh, Xiangyu Yue, Alberto L. Sangiovanni-Vincentelli, and Sanjit A. Seshia.
At PLDI 2019 (the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation).
Specification Mining for Machine Improvisation with Formal Specifications.
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.
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.
Alexandre Donzé, Rafael Valle, Ilge Akkaya, Sophie Libkind, Sanjit A. Seshia, and David Wessel.
At ICMC 2014 (the 40th International Computer Music Conference).