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.
Révisé le :
Accepté le :
Publié le :
Keywords: CAIA System, Constraint Satisfaction Problem, Symmetry Handling
CC-BY 4.0
@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] 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] 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] Topic 5 : Symmetry, Combinatorial Optimisation and Constraint Programming (Course 1DL441) (2020) (https://user.it.uu.se/~pierref/courses/COCP/slides/T05-Symmetry.pdf)
[4] 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] A Note on Syntactic Symmetry and the Manipulation of Formal Systems by Machine, Information and control, Volume 2 (1959), pp. 80-89 | DOI
[6] 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] Symmetry in constraint programming, Handbook of constraint programming – Chapter 10, Elsevier, 2006 | DOI
[8] Un langage et un programme pour énoncer et résoudre des problèmes combinatoires, Ph. D. Thesis, Université Paris 6 (1976)
[9] 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] A Step toward An Artificial Artificial Intelligence Scientist (2008) (http://jacques.pitrat.pagesperso-orange.fr)
[11] Breaking Symmetries in All Different Problems, Proceedings of IJCAI’05 (2005), pp. 272-277
Cité par Sources :