The adaptive search method for constraint solving and its application to musical csps

Abstract: We here propose a generic, domain-independent local search method called Adaptive Search for solving Constraint Satisfaction Problems (CSP). We design a new heuristics that takes advantage of the struc-ture of the problem in terms of constraints and variables and can guide the search more precisely than a global cost function to optimize (such as for instance the number of violated constraints). We also use an adaptive memory in the spirit of Tabu Search in order to prevent stagnation in local minima and loops. This method is generic, can apply to a large class of constraints (e.g. linear and non-linear arithmetic constraints, symbolic constraints, etc) and nat-urally copes with over-constrained problems. Preliminary results on some classical CSP problems show very encour-aging performances. We also applied this method is the area of computer-assisted composition in music and we also present results of an implementation of the Adap-tive Search algorithm for musical CSPs that come from collaboration with contemporary music composers