Quantified Constraint Handling Rules

Barichard & I. St ephan This work is licensed under the Creative Commons Attribution License. Quantified Constraint Handling Rules Vincent Barichard LERIA, University of Angers Angers, France vincent.barichard@univ-angers.fr Igor St ephan LERIA, University of Angers Angers, France igor.stephan@univ-angers.fr We shift the QCSP (Quantified Constraint Satisfaction Problems) framework to the QCHR (Quantified Constraint Handling Rules) framework by enabling dynamic binder and access to user-defined constraints. QCSP offers a natural framework to express PSP ACE problems as finite two-players games. But to define a QCSP model, the binder must be formerly known and cannot be built dynamically even if the worst case won't occur. To overcome this issue, we define the new QCHR formalism that allows to build the binder dynamically during the solving. Our QCHR models exhibit state-of-the-art performances on static binder and outperforms previous QCSP approaches when the binder is dynamic. 1 Introduction We shift the QCSP (for Quantified Constraint Satisfaction Problems) framework to the QCHR (for Quantified Constraint Handling Rule) framework. Such shift is motivated by the difficulties for developing real applications in QCSP . QCSP [7, 26, 15, 4, 22, 20, 3] are a generalization of Constraint Satisfaction Problems (CSP) in which variables may be quantified existentially (as in CSP) and universally. A QCSP is an alternation of existentially and universally quantified variables over finite domains, the binder, followed by a CSP . Universally quantified variables represent uncontrollable parameters such as meteorological events.