Pachet, F., Roy, P. and Barbieri, G. Finite-Length Markov Processes with Constraints. Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI, pages 635-642, Barcelona, Spain, July 2011

Sony CSL authors: Gabriele Barbieri, Fran├žois Pachet, Pierre Roy


Many systems use Markov models to generate finite-length sequences that imitate a given style. These systems often need to enforce specific control constraints on the sequences to generate. Unfortunately, control constraints are not compatible with Markov models, as they induce long-range dependencies that violate the Markov hypothesis of limited memory. Attempts to solve this issue using heuristic search do not give any guarantee on the nature and probability of the sequences generated. We propose a novel and efficient approach to controlled Markov generation for a specific class of control constraints that 1) guarantees that generated sequences satisfy control constraints and 2) follow the statistical distribution of the initial Markov model. Revisiting Markov generation in the framework of constraint satisfaction, we show how constraints can be compiled into a non-homogeneous Markov model, using arc-consistency techniques and renormalization. We illustrate the approach on a melody generation problem and sketch some realtime applications in which control constraints are given by gesture controllers.

Keywords: Continuator, Markov constraints, Virtuoso


[PDF] Adobe Acrobat PDF file

BibTeX entry

@INPROCEEDINGS { pachet:11b, ADDRESS="Barcelona, Spain", AUTHOR="Pachet, F. and Roy, P. and Barbieri, G.", BOOKTITLE="Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI", MONTH="July", PAGES="635--642", TITLE="Finite-Length Markov Processes with Constraints", YEAR="2011", }