  We formalize and analyze a new problem in formal language theory termed
control improvisation. Given a specification language, the problem is to
produce an improviser, a probabilistic algorithm that randomly generates words
in the language, subject to two additional constraints: the satisfaction of a
quantitative soft constraint, and the exhibition of a specified amount of
randomness. Control improvisation has many applications, including for example
systematically generating random test vectors satisfying format constraints or
preconditions while being similar to a library of seed inputs. Other
applications include robotic surveillance, machine improvisation of music, and
randomized variants of the supervisory control problem. We describe a general
framework for solving the control improvisation problem, and use it to give
efficient algorithms for several practical classes of instances with finite
automaton and context-free grammar specifications. We also provide a detailed
complexity analysis, establishing #P-hardness of the problem in many other
cases. For these intractable cases, we show how symbolic techniques based on
Boolean satisfiability (SAT) solvers can be used to find approximate solutions.
Finally, we discuss an extension of control improvisation to multiple soft
constraints that is useful in some applications.
