Exploiter les conflits pour réduire l'effort de recherche en satisfaction de contraintes
Institution:
ArtoisDisciplines:
Directors:
Abstract EN:
The Constraint Satisfaction Problem framework (CSP) allows to deal with problems modeled using constraints. To solve this kind of problems, a classical complete approach consists in interleaving decision steps (variable assignments) and constraint propagation steps (reduction of the search space). When a conflict occurs (i. E. No solution can be found from the decisions already performed), instead of systematically backtracking on the last choice, it can be useful to identify the exact reasons of this failure. In the context of solving constraint satisfaction problems, we propose in this Phd Thesis several approaches to reduce the search effort by analysing and exploiting these conflicts. First we show that it is possible to efficiently guide search using the last encountered conflicts. The approach that we propose allows us to prevent thrashing (the fact of performing several times the same errors) by directing the search on the source of the last encountered conflict. Another well-known solution consists in exploiting restarts capabilities : the search algorithm is restarted several times in order to diversify the search. However, in this context, one can unnecessarily explore several times the same parts of the search space. To avoid this phenomenon, we propose to compute a posteriori, i. E. At each restart, some explanations of the failures occurring during search using a set of nogoods (sets of variable assignments considered as new constraints). These nogoods are recorded in a base exploited thanks to a lazy data-structure : the watched literals. Finally we underline the fact that some similar situations (i. E. Some states of the search at a given step) can occur during search. We introduce some original operators, based on the detection of inconsistent partial states, and use then to identify some situations considered as equivalent. An inconsistent partial state represents a subset of search state, sufficient to prove that no solution can be found from this state. We also show that these operators allow us to detect and dynamically break some kinds of symetries.
Abstract FR:
Le cadre "Problème de Satisfaction de Contraintes'' (ou CSP pour Constraint Satisfaction Problem) regroupe les problèmes modélisables sous la forme de contraintes. Pour résoudre ce type de problèmes, une approche classique, et complète, consiste à alterner prises de décisions (assignations de variables) et processus de propagation de contraintes (réduction de l'espace de recherche). Au lieu de remettre en cause systématiquement le dernier choix effectué lorsqu'un conflit (i. E. L'impossibilité de trouver une solution sur la base des décisions déjà prises) apparaît, il peut être intéressant d'identifier les raisons précises de cet échec. Nous proposons dans cette thèse plusieurs techniques d'analyse et d'exploitation des conflits qui permettent de réduire de façon significative l'effort de recherche nécessaire à la résolution des problèmes de satisfaction de contraintes. Nous montrons tout d'abord qu'il est possible de guider efficacement la recherche en se basant sur les derniers conflits rencontrés. L'approche que nous proposons permet de lutter contre le thrashing (le fait de reproduire plusieurs fois les mêmes erreurs) en orientant la recherche sur l'origine du dernier conflit rencontré. Une autre solution connue consiste à effectuer des redémarrages : l'algorithme de recherche est relancé plusieurs fois pour diversifier la recherche. Cependant, dans ce contexte, il n'est pas exclu d'explorer inutilement plusieurs fois les mêmes portions de l'espace de recherche. Pour éviter cela, nous proposons une technique consistant à calculer a posteriori, i. E. à chaque redémarrage, les explications des échecs rencontrés au cours de la recherche sous la forme d'un ensemble de nogoods (ensembles d'assignations de variables perçues comme de nouvelles contraintes). Ceux-ci sont enregistrés dans une base exploitée grace à une structure de données paresseuse : les watched literals. Finalement nous mettons en évidence le fait que des situations (i. E. Des états de la recherche à un instant donné) similaires peuvent apparaître au cours de la recherche. Nous introduisons des opérateurs originaux, basés sur la détection d'états partiels inconsistants, permettant l'identification de ces situations jugées équivalentes. Un état partiel inconsistant représente un sous-ensemble de l'état de la recherche à un instant donné, suffisant pour démontrer l'absence de solution à partir de cet état. Nous montrons également que ces opérateurs permettent de détecter et casser dynamiquement certaines formes de symétries.