Algorithmic Improvisation

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 Daniel Fremont's Ph.D. thesis; our papers on its theory and applications are listed at the bottom of this page.

For an overview, see this keynote talk given at FSTTCS 2020: [video on youtube]

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/Talks on Algorithmic Improvisation

For a comprehensive overview of the history, theory, and applications of algorithmic improvisation, see this thesis:

Algorithmic Improvisation. [thesis]
Daniel J. Fremont.
Ph.D. dissertation, 2019 (University of California, Berkeley; Group in Logic and the Methodology of Science).

Talks on Algorithmic Improvisation

Algorithmic Improvisation for Dependable Intelligent Autonomy [video on youtube]
Sanjit A. Seshia.
Keynote Talk at FSTTCS 2020 (the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science).

Our individual papers on various aspects of algorithmic improvisation are listed below.

Papers on the Theory of Algorithmic Improvisation:

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 Donze, and Sanjit A. Seshia.
arXiv preprint, 2017. (extends the FSTTCS 2015 paper below)

Control Improvisation. [arXiv version]
Daniel J. Fremont, Alexandre Donze, 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. [full version] [implementation] [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. [doi]
Rafael Valle, Alexandre Donze, 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 Donze, 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 Donze, Rafael Valle, Ilge Akkaya, Sophie Libkind, Sanjit A. Seshia, and David Wessel.
At ICMC 2014 (the 40th International Computer Music Conference).