Strategic Constraint Satisfaction Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2006

Strategic Constraint Satisfaction Problems

Abstract

The Quantified constraint satisfaction problem (QCSP) has been introduced to express situations in which we are not able to de- cide the value of some of the variables (the universal ones). Despite the expressiveness of QCSP, many problems, such as two-player games or motion planning of robots, remain difficult to express. In this paper, we propose Strategic CSP, an extension of QCSP where universal vari- ables adapt their domain to be compatible with previous choices. This new framework permits an easy encoding of many two-player games. We give examples of such encodings and provide a preliminary experimental evaluation.
Fichier principal
Vignette du fichier
cp06ws-scsp.pdf (127.43 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00134937 , version 1 (08-03-2007)

Identifiers

  • HAL Id : lirmm-00134937 , version 1

Cite

Christian Bessiere, Guillaume Verger. Strategic Constraint Satisfaction Problems. ModRef 2006 - 5th International Workshop on Constraint Modelling and Reformulation, Sep 2006, Nantes, France. pp.17-29. ⟨lirmm-00134937⟩
96 View
466 Download

Share

More