La prise en compte des symétries dans CAIA
Jean-Yves Lucas1
1 EDF R&D, Département OSIRIS 7 boulevard Gaspard Monge 91120 Palaiseau, France
Revue Ouverte d'Intelligence Artificielle, Volume 3 (2022) no. 1-2, pp. 167-177.

Le système d’Intelligence Artificielle CAIA, conçu par Jacques Pitrat, est un chercheur artificiel capable de résoudre des problèmes de satisfaction de contraintes. Dans cet article, nous décrivons comment CAIA détecte les symétries du problème à résoudre, et ajoute des contraintes afin de casser ces symétries et réduire ainsi significativement la taille de l’espace de recherche. Une anecdote finale évoque une rencontre entre Jacques Pitrat et Douglas Hofstadter.

CAIA is an AI system designed by Jacques Pitrat. It is an artificial researcher capable of solving constraint satisfaction problems. In this paper, we describe how CAIA detects the symmetries of the problem and adds constraints in order to break these symmetries. As a result, the size of the search space is significantly reduced. A final anecdote evokes a meeting between Jacques Pitrat and Douglas Hofstadter.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/roia.26
Mot clés : Système CAIA, problème de satisfaction de contraintes, prise en compte des symétries
Keywords: CAIA System, Constraint Satisfaction Problem, Symmetry Handling

Jean-Yves Lucas 1

1 EDF R&D, Département OSIRIS 7 boulevard Gaspard Monge 91120 Palaiseau, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ROIA_2022__3_1-2_167_0,
     author = {Jean-Yves Lucas},
     title = {La prise en compte des sym\'etries dans {CAIA}},
     journal = {Revue Ouverte d'Intelligence Artificielle},
     pages = {167--177},
     publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
     volume = {3},
     number = {1-2},
     year = {2022},
     doi = {10.5802/roia.26},
     language = {fr},
     url = {https://roia.centre-mersenne.org/articles/10.5802/roia.26/}
}
TY  - JOUR
AU  - Jean-Yves Lucas
TI  - La prise en compte des symétries dans CAIA
JO  - Revue Ouverte d'Intelligence Artificielle
PY  - 2022
SP  - 167
EP  - 177
VL  - 3
IS  - 1-2
PB  - Association pour la diffusion de la recherche francophone en intelligence artificielle
UR  - https://roia.centre-mersenne.org/articles/10.5802/roia.26/
DO  - 10.5802/roia.26
LA  - fr
ID  - ROIA_2022__3_1-2_167_0
ER  - 
%0 Journal Article
%A Jean-Yves Lucas
%T La prise en compte des symétries dans CAIA
%J Revue Ouverte d'Intelligence Artificielle
%D 2022
%P 167-177
%V 3
%N 1-2
%I Association pour la diffusion de la recherche francophone en intelligence artificielle
%U https://roia.centre-mersenne.org/articles/10.5802/roia.26/
%R 10.5802/roia.26
%G fr
%F ROIA_2022__3_1-2_167_0
Jean-Yves Lucas. La prise en compte des symétries dans CAIA. Revue Ouverte d'Intelligence Artificielle, Volume 3 (2022) no. 1-2, pp. 167-177. doi : 10.5802/roia.26. https://roia.centre-mersenne.org/articles/10.5802/roia.26/

[1] D. Cohen; P. Jeavons; C. Jefferson; K. Petrie Constraint Symmetry and Solution Symmetry, AAAI 2006 - Proceedings of the 28th National Conference on Artificial Intelligence, 16-20 July 2006, Boston, Massachusetts, USA (2006)

[2] D. Cohen; P. Jeavons; C. Jefferson; K. E. Petrie; B. M. Smith Symmetry Definitions for Constraint Satisfaction Problems, Principles and Practice of Constraint Programming – CP 2005 (P. van Beck, ed.), Springer, 2005, pp. 17-31 | DOI

[3] P. Flener Topic 5 : Symmetry, Combinatorial Optimisation and Constraint Programming (Course 1DL441) (2020) (https://user.it.uu.se/~pierref/courses/COCP/slides/T05-Symmetry.pdf)

[4] E. C. Freuder Eliminating Interchangeable Values in Constraint Satisfaction Problems, AAAI 1991 – Proceedings of the 9th National Conference on Artificial Intelligence, 14-19 July 1991, Anaheim, California, USA (1991), pp. 227-233

[5] H. Gelernter A Note on Syntactic Symmetry and the Manipulation of Formal Systems by Machine, Information and control, Volume 2 (1959), pp. 80-89 | DOI

[6] I. P. Gent; W. Harvey; T. Kelsey Groups and Constraints : Symmetry Breaking during Search, Principles and Practice of Constraint Programming – CP 2002 (P. van Hentenryck, ed.), Springer, 2002, pp. 415-430 | DOI

[7] I. P. Gent; K. Petrie; J.-F. Puget Symmetry in constraint programming, Handbook of constraint programming – Chapter 10, Elsevier, 2006 | DOI

[8] J.-L. Laurière Un langage et un programme pour énoncer et résoudre des problèmes combinatoires, Ph. D. Thesis, Université Paris 6 (1976)

[9] J.-Y. Lucas Génération automatique de programmes par règles et compilation de base de règles : application à un système expert de diagnostic de signaux courants de Foucault, Ph. D. Thesis, Université Pierre et Marie Curie (1989)

[10] Jacques Pitrat A Step toward An Artificial Artificial Intelligence Scientist (2008) (http://jacques.pitrat.pagesperso-orange.fr)

[11] J-F. Puget Breaking Symmetries in All Different Problems, Proceedings of IJCAI’05 (2005), pp. 272-277

Cité par Sources :