Eric Vin and Daniel J. Fremont
06/18/2021 09:33 AM
Computer Science and Engineering
The classic Control Improvisation problem allows one to extend traditional synthesis problems, by balancing control over what is generated, with how randomly it is generated. In this paper, we propose Labelled Control Improvisation, an extension of classic Control Improvisation that allows for greater control over randomness via the addition of a labelling specification. By assigning one and only one label to every improvisation, we avoid the immediate exponential time complexity of multiple soft constraints, while still allowing for more fine tuned control. We present two different problems, the simpler Labelled Control Improvisation problem, in which explicit randomness bounds are provided, followed by the more natural Maximum Entropy Labelled Control Improvisation problem, which forgoes some of the explicit constraints and instead seeks to generate improvisations in a way that maximizes entropy. We also present several motivating examples that illustrate the usefulness of Labelled Control Improvisation, and provide upper and lower bounds on the complexity of these problems when using a variety of constraint and labelling specifications.
