Profound Degree: A Conservative Heuristic to Repair Dynamic CSPs

Abstract : For a better treatment of Dynamic Constraint Satisfaction Problems (DCSPs), several techniques have been developed to be used in repair algorithms. We cite, for example, the variables/values ordering heuristics and local search techniques.We distinguish between static heuristics, which calculate their values once at the beginning of the search, and dynamic heuristics that use an expensive intelligence in terms of solving time.In this paper, we propose a new static variable ordering heuristic, Profound Degree (pdeg), based on deg heuristic, which calculates the degree of influence of a given variable, on the whole constraints network, relatively to its position in the network.We evaluate this heuristic on the Extended Partial-order Dynamic Backtracking (EPBD) approach, which is an approach to repair DCSPs solutions, and we compare it to the best-known variables ordering heuristics (VOHs) for repairing. The evaluation of performance is on random binary problems and meeting scheduling problems, with the criteria of computation time, number of constraints checks and Hamming distance between the former and the current solution.
Type de document :
Communication dans un congrès
Lazaros Iliadis; Ilias Maglogiannis; Harris Papadopoulos. 10th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2014, Rhodes, Greece. Springer, IFIP Advances in Information and Communication Technology, AICT-436, pp.140-149, 2014, Artificial Intelligence Applications and Innovations. 〈10.1007/978-3-662-44654-6_14〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01391305
Contributeur : Hal Ifip <>
Soumis le : jeudi 3 novembre 2016 - 10:52:54
Dernière modification le : vendredi 1 décembre 2017 - 01:16:36
Document(s) archivé(s) le : samedi 4 février 2017 - 13:17:09

Fichier

978-3-662-44654-6_14_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Yosra Acodad, Amine Benamrane, Imade Benelallam, El Bouyakhf. Profound Degree: A Conservative Heuristic to Repair Dynamic CSPs. Lazaros Iliadis; Ilias Maglogiannis; Harris Papadopoulos. 10th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2014, Rhodes, Greece. Springer, IFIP Advances in Information and Communication Technology, AICT-436, pp.140-149, 2014, Artificial Intelligence Applications and Innovations. 〈10.1007/978-3-662-44654-6_14〉. 〈hal-01391305〉

Partager

Métriques

Consultations de la notice

38

Téléchargements de fichiers

20