Constraint Programming in Music

Charlotte Truchet is an assistant professor at Nantes University in France. While she was earning her PhD, she worked on musical constraints in collaboration with contemporary composers at IRCAM/University of Paris 6. Gérard Assayag is head of the IRCAM-CNRS lab "Sciences and Technologies for Music and Sound" and a co-author of Open Music Computer-Assisted Composition software.

Introduction xiii
Charlotte TRUCHET and Gerard ASSAYAG

Chapter 1. Modeling Temporal Constraints for a System of Interactive Scores 1
Antoine ALLOMBERT, Myriam DESAINTE-CATHERINE and Mauricio TORO

1.1. Introduction 1

1.2. Formalism of interactive scores 2

1.2.1. Temporal relations 3

1.2.2. Interaction points 4

1.2.3. Modification behaviors 4

1.2.3.1. Fermata behavior 5

1.2.3.2. Chronological and anti-chronological behaviors 5

1.2.3.3. Proportional behavior 7

1.3. ECO machine 8

1.3.1. Supple intervals with fermata behavior 8

1.3.2. General case 10

1.3.3. Interval constraints 11

1.3.4. Constraint propagation 13

1.4. Concurrent constraint time model 15

1.4.1. Ntcc model 15

1.4.1.1. Control points 16

1.4.1.2. Temporal relations 16

1.4.1.3. Example 16

1.4.2. Discussion 17

1.5. Timed conditional branching model 18

1.5.1. Specification of the model 18

1.5.1.1. Control points 19

1.5.1.2. Intervals 19

1.5.1.3. Example 20

1.5.2. Ntcc model 20

1.5.2.1. Control points 21

1.5.2.2. Intervals 21

1.5.2.3. Example 22

1.5.3. Results and discussion 22

1.6. Concluding remarks and future work 22

1.7. Bibliography 23

Chapter 2. Variable Orderings for Solving Musical Constraint Satisfaction Problems 25
Torsten ANDERS

2.1. Motivation 25

2.2. Background: the constraint model based on computation spaces 28

2.2.1. Propagate-and-search 29

2.2.2. An example 33

2.2.3. Distribution strategy definition 35

2.3. Specializing the constraint model for music 37

2.3.1. Music representation and score contexts 37

2.3.2. Adapting the space-based constraint model 38

2.4. Score distribution strategies 39

2.4.1. Adapting the first-fail principle 40

2.4.2. Resolving inaccessible score contexts 41

2.4.3. Resolving multiple inaccessible score contexts in order 42

2.4.4. Combining the principles resolve-inaccessible-contexts and first-fail 44

2.4.5. The dynamic left-to-right variable ordering 44

2.5. An example: Florid counterpoint 46

2.5.1. The music theory model 47

2.5.2. Search process and results 49

2.6. Summary 51

2.7. Bibliography 52

Chapter 3. Constraints for an Unfolding Time 55
Georges BLOCH and Charlotte TRUCHET

3.1. Introduction 56

3.1.1. Composition? 56

3.1.2. Writing: the constraints of composition 57

3.1.3. Composition as a synthesis of time 59

3.2. A new set of musical problems: the tiling canons 60

3.2.1. The canon structure 60

3.2.2. Computer representation 63

3.2.3. Harmony? 64

3.2.4. What about time evolution? 66

3.3. Musical constraints on tiling canons 68

3.3.1. Harmonic constraints: virtual fundamental 69

3.3.2. Harmonic constraints: textures 71

3.3.3. Melodic constraint 72

3.3.4. Overconstrained and other constraints 73

3.4. Constraints in time 74

3.4.1. The solving algorithm 74

3.4.2. Constraint process as a musical process 76

3.4.3. Modifying constraints in time 77

3.5. Conclusion 79

3.6. Bibliography 79

Chapter 4. Global Constraints in Orchestration 81
Gregoire CARPENTIER

4.1. Introduction 81

4.2. The automatic orchestration problem 83

4.3. A unified syntax for global constraints 84

4.3.1. Preliminary definitions 84

4.3.2. Constraint operators 84

4.3.3. Cost functions 85

4.4. The CDCSolver heuristic 87

4.4.1. Conflict constraints versus design constraints 87

4.4.2. Avoiding cycles 89

4.4.3. Choosing the variable to update 90

4.4.4. Using CDCSolver in constrained optimization problems 92

4.5. Performance evaluation 93

4.6. Using CDCSolver in automatic orchestration 94

4.6.1. Timbre "fade in" 95

4.6.2. Speakings ostinato 96

4.7. Conclusions and future work 101

4.8. Bibliography 101

Chapter 5. Using Gecode to Solve Musical Constraint Problems 103
Serge LEMOUTON

5.1. Plan 104

5.2. Introduction 104

5.3. Why Gecode? 106

5.3.1. Constraints in OpenMusic and PWGL 106

5.3.2. Gecode 107

5.3.3. Gelisp 107

5.3.4. OMGecode implementation 108

5.4. A musical constraint repertoire 108

5.4.1. All-interval 108

5.4.1.1. Definitions 108

5.4.1.2. Results 109

5.4.1.3. Musical uses 110

5.4.2. Constrained melodic strings for Michael Jarrell's Congruences 111

5.4.2.1. Definition 111

5.4.2.2. "Historic" implementations 113

5.4.2.3. Gecode implementation and results 116

5.4.3. Generating chords by constraints: harmonic rules 117

5.4.3.1. Definition 117

5.4.3.2. Hamming 118

5.4.4. Stroppa vertical pitch structure constraints 119

5.4.4.1. Definition 119

5.4.5. Harmonic profiles 121

5.4.5.1. Definition 121

5.4.6. Melodic interpolations 122

5.4.7. Harmonic progression 123

5.4.7.1. Definition 123

5.5. Musical constraint specificities 123

5.5.1. Time-varying constraints 124

5.5.2. Soft constraints 124

5.5.3. Availability and installation 125

5.6. Conclusion 125

5.7. Bibliography 125

5.8. Appendix A: All-interval script command options 127

5.9. Appendix B: Jarrell problem implemented in C++, using Gecode 129

5.10. Appendix C: Jarrell script command options 130

Chapter 6. Concurrent ConstraintModels of Music Interaction 133
Carlos OLARTE, Camilo RUEDA, Gerardo SARRIA, Mauricio TORO and Frank D. VALENCIA

6.1. Introduction 133

6.2. Concurrent constraint programming 134

6.2.1. The language of CCP processes 135

6.2.2. Timed CCP 136

6.3. Dynamic interactive scores 137

6.3.1. Mobile behavior in tcc and a model of dynamic interactive scores 138

6.4. Non-determinism and verification of musical properties 140

6.4.1. The ntcc calculus 141

6.4.2. Logic characterization of ntccprocesses 142

6.4.3. Modeling rhythm patterns 143

6.5. Real time and preemption 146

6.6. Probabilistic extensions and musical improvisation 149

6.6.1. The factor oracle 149

6.6.2. Probabilistic transversal of the FO 151

6.7. Perspectives and future work 152

6.8. Bibliography 153

Chapter 7. From Rhythm Rules to Music Rules 157
Orjan SANDRED

7.1. Two constraint-solving systems for musical composition 157

7.2. Music representation 158

7.3. Rhythm representation and OMRC 159

7.4. OMRC and rhythm organization 159

7.5. Basic concepts for rules in OMRC 160

7.6. From OMRC to PWMC 161

7.7. Basic concepts in PWMC 163

7.8. The user interface 165

7.9. More about the domains 166

7.9.1. Motif and groupings of values 167

7.9.2. Metric units 168

7.9.3. Locked variables 168

7.10. Defining rules 169

7.10.1. Access boxes 170

7.10.2. Logic statements 172

7.11. Heuristic rules 173

7.12. A patch example 174

7.13. Strategy rules 177

7.14. Data representation 178

7.14.1. The domain 178

7.14.2. Score representation 179

7.15. Musical example: Labyrinths in the Wind 183

7.15.1. Rules for rhythm 183

7.15.2. Rules for pitch 185

7.15.3. A heuristic stochastic rule 185

7.15.4. Examining the solution 186

7.16. Conclusion and future developments of the systems 187

7.17. Bibliography 188

Chapter 8. OMClouds, a Library for Musical Constraints 189
Charlotte TRUCHET

8.1. Introduction 189

8.1.1. OpenMusic 190

8.1.2. Constraints in CAC 192

8.2. Some musical CSPs 193

8.2.1. All-intervals series 193

8.2.2. Sorting chords 194

8.2.3. Asynchronous rhythms 194

8.2.4. Spectral chords 196

8.2.5. Gestures 198

8.2.6. Tempo approximation 199

8.2.7. Accelerando 200

8.2.8. Other problems 201

8.2.9. Conclusions on the compositional CSPs 202

8.3. OMClouds 204

8.3.1. Adaptive search 204

8.3.2. CSP definition 205

8.3.3. Generation of the error functions 207

8.3.4. Solving 208

8.3.5. Edition of results 209

8.4. Conclusion 211

8.5. Bibliography 211

List of Authors 215

Index 219