caa a22 4500 445879335 CHVBK 20180317145537.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s10601-010-9101-4 doi (NATIONALLICENCE)springer-10.1007/s10601-010-9101-4 Markov constraints: steerable generation of Markov sequences [Elektronische Daten] [François Pachet, Pierre Roy] Markov chains are a well known tool to model temporal properties of many phenomena, from text structure to fluctuations in economics. Because they are easy to generate, Markovian sequences, i.e. temporal sequences having the Markov property, are also used for content generation applications such as text or music generation that imitate a given style. However, Markov sequences are traditionally generated using greedy, left-to-right algorithms. While this approach is computationally cheap, it is fundamentally unsuited for interactive control. This paper addresses the issue of generating steerable Markovian sequences. We target interactive applications such as games, in which users want to control, through simple input devices, the way the system generates a Markovian sequence, such as a text, a musical sequence or a drawing. To this aim, we propose to revisit Markov sequence generation as a branch and bound constraint satisfaction problem (CSP). We propose a CSP formulation of the basic Markovian hypothesis as elementary Markov Constraints (EMC). We propose algorithms that achieve domain-consistency for the propagators of EMCs, in an event-based implementation of CSP. We show how EMCs can be combined to estimate the global Markovian probability of a whole sequence, and accommodate for different species of Markov generation such as fixed order, variable-order, or smoothing. Such a formulation, although more costly than traditional greedy generation algorithms, yields the immense advantage of being naturally steerable, since control specifications can be represented by arbitrary additional constraints, without any modification of the generation algorithm. We illustrate our approach on simple yet combinatorial chord sequence and melody generation problems and give some performance results. The Author(s), 2010 CSP nationallicence Markov chains nationallicence Sequence constraints nationallicence Global constraints nationallicence Interactive applications nationallicence Pachet François Sony CSL, 6, rue Amyot, Paris, France aut Roy Pierre Sony CSL, 6, rue Amyot, Paris, France aut Constraints Springer US; http://www.springer-ny.com 16/2(2011-04-01), 148-172 1383-7133 16:2<148 2011 16 10601 https://doi.org/10.1007/s10601-010-9101-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10601-010-9101-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Pachet François Sony CSL, 6, rue Amyot, Paris, France aut NATIONALLICENCE 700 1- Roy Pierre Sony CSL, 6, rue Amyot, Paris, France aut NATIONALLICENCE 773 0- Constraints Springer US; http://www.springer-ny.com 16/2(2011-04-01), 148-172 1383-7133 16:2<148 2011 16 10601 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer