Constraint programming is a paradigm for computing with mathematical relations named constraints. It is a declarative approach to describe many real-world problems including scheduling, vehicles routing, biology and musical composition. Constraint programming must be contrasted with procedural approaches that describe how a problem is solved, whereas constraint models describe what the problem is. The part of how a constraint problem is solved is left to a general constraint solver. Unfortunately, there is no solving algorithm efficient enough to every problem, because the search strategy must often be customized per problem to attain reasonable efficiency. This is a daunting task that requires expertise and good understanding on the solver's intrinsics. Moreover, higher-level constraint-based languages provide limited support to specify search strategies.
In this dissertation, we tackle this challenge by designing a programming language for specifying search strategies. It is constructed around two axes: (i) a novel theory of constraint programming based on lattice theory, and (ii) a programming language, called spacetime programming, building on lattice theory for its data structures and on synchronous programming for its computational model.
This paradigm opens the door to new, more complex, search strategies in constraint programming but also in applications requiring backtracking search. We demonstrated its usefulness in an interactive computer-aided composition system where we designed a search strategy to help the composer navigating in the state space generated by a musical constraint problem.
Pierre Talbot will defend his doctoral carried out in the Musical Representations team (STMS - CNRS/IRCAM/Sorbonne Université).
Carlos Agon, Sorbonne Université
Emmanuelle Encrenaz, Sorbonne Université
Antoine Miné, Sorbonne Université
Manuel Serrano, INRIA, Inde
Sylvain Soliman, INRIA, Lifeware
Peter Van Roy, Université Catholique de Louvain