Une heuristique basée sur l'historique des conflits pour les problèmes de satisfaction de contraintes

Djamal Habet (1) , Cyril Terrioux (1)

1 COALA - COntraintes, ALgorithmes et Applications

L’heuristique de choix de variables est une brique importante pour les algorithmes de résolution du problème de satisfaction de contraintes (CSP). Elle a une influence souvent considérable sur l’efficacité de la recherche et permet, d’une certaine manière, d’exploiter la structure des instances. Dans cet article, nous proposons l’heuristique CHS (pour Conflict-History Search) qui est une heuristique dynamique et adaptative pour la résolution d’instances CSP. Elle repose sur les échecs rencontrés durant la recherche et considère leur temporalité tout au long de la résolution. Une technique d’apprentissage par renforcement est exploitée pour estimer l’évolution de la difficulté des contraintes durant la recherche. Les expérimentations réalisées sur des instances au format XCSP3 permettent de montrer que l’intégration de CHS au sein d’un solveur basé sur l’algorithme MAC s’avère pertinente, conduisant notamment à des résultats meilleurs que ceux obtenus avec des heuristiques de l’état de l’art comme dom/wdeg et ABS.

Domaines: Intelligence artificielle [cs.AI]

Djamal Habet, Cyril Terrioux. Une heuristique basée sur l'historique des conflits pour les problèmes de satisfaction de contraintes. Actes des 15èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2019, Albi, France. pp.153-154. ⟨hal-02162856⟩