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:

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, 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:

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 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 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).