Maintien asynchrone de la consistance d'arc dans la recherche distribuée synchrone
Abstract
Nous avons proposé récemment Nogood-Based Asynchronous Forward Checking (AFC-ng), un algo-rithme efficace et robuste pour résoudre des Problèmes de Satisfaction de Contraintes Distribués (DisCSPs). AFC-ng exécute de manière asynchrone une phase de vérification en avant pendant la recherche synchrone. Dans ce papier, nous proposons deux nouveaux algorithmes basés sur le même mécanisme qu'AFC-ng. Cependant, au lieu d'utiliser le forward checking comme propriété de filtrage, nous proposons de maintenir d'une manière asynchrone la consistance d'arc (MACA). Le premier algorithme que nous proposons, MACA-del, maintient la consistance d'arc grâce à un type de messages supplé-mentaire, des messages de suppression. Le deuxième algorithme, MACA-not, réalise la consistance d'arc sans aucun nouveau type de message. Nous fournissons une analyse théorique et uneévaluation expérimentale de l'approche proposée. Nos expérimentations montrent la bonne performance des algorithmes MACA et plus particulièrement ceux de MACA-not.
Domains
Artificial Intelligence [cs.AI]Origin | Files produced by the author(s) |
---|
Loading...