Résolution d'un problème de satisfaction de contraintes sur les intervalles

Chapitre 4

Conclusion générale

Pour conclure ce travail, nous résumons les étapes de notre recherche qui a portésur la résolution d'un problème particulier de satisfaction de contraintes.

Dans le deuxième Chapitre, nous avons définis les problèmes de satisfaction des contraintes, en donnant des modélisations sous la forme CSP de quelques problèmes connues, puis nous avons illustréle fonctionnement de quelques algorithmes complets de résolution des CSP. Nous avons conclus le chapitre par l'étude d'un type spécifique de CSP, qui est le problème de satisfactions des contraintes temporelles sous lequel s'inscrit le problème proposédans le Chapitre 3.

Le troisième Chapitre a étéconsacréà la résolution d'un problème spécifique qui fait intervenir des contraintes temporelles. Nous avons décrit ce problème, puis nous avons montré, sur un exemple, que les algorithmes complets de résolution de CSP sont inefficaces. Nous avons ensuite essayéde remédier à la défaillance de ces algorithmes en proposant notre propre algorithme, qui s'appuie essentiellement sur une méthode heuristique. Nous avons conclu ce chapitre par une expérimentation, sur des instances du problème générées aléatoirement, qui a montrél'efficacité(95.53%) de notre algorithme malgrésa simplicité.

Parmi les perspectives ouverte pour ce travail, nous proposons de trouver une méthode pour traiter des contraintes qui ont la même forme que celles que nous avons considérémais qui impliquent plus de variables, toujours en un temps raisonnable, et en utilisant une heuristique encore plus efficace que la nôtre.

59

Bibliographie

[1] Christine SOLNON, »Ant Colony Optimization and Constraint Programming »,2010, chapitre 3 ,3.1 What is a constraint?

[2] Christine SOLNON,»Ant Colony Optimization and Constraint Programming »,2010, 3.2 What is a constraint satisfaction problem?

[3] Charles Lutwidge Dodgson (plus connu sous le pseudonyme de Lewis Carroll) est un romancier, essayiste, photographe et professeur de mathématique à l'universitéd'Oxford, néle 27 janvier 1832 à Daresbury, dans le Cheshire et mort le 14 janvier 1898 à Guildford.

[4] J. F. Allen. An interval-based representation of temporal knowledge. In Proceedings of the 7th International Joint Conference on Artificial Intelligence (IJCAI'81), pages 221-226, 1981.

[5] James F. Allen: Maintaining knowledge about temporal intervals. In : Communications of the ACM. 26 November 1983. ACM Press. pp. 832-843, ISSN 0001-0782

[6] M. Vilain et H. Kautz. Constraint propagation algorithms for temporal reasoning. In AAAI-86 Proceedings, pages 377-382, 1986.

[7] Rina Dechter,»Constraint Processing», 2003, chapitre 12 :» Temporal Networks Constraint»

[8] http :// fr.wikipedia.org/wiki/Analyse de la complexit%C3%A9 des algorithmes

[9] http :// fr.wikipedia.org/wiki/Probl%C3%A8me de satisfaction de contraintes

[10] J. F. Allen. Towards a general theory of action and time. Artificial Intelligence, 23(2) :123-154, 1984.

[11] J.-F. Condotta et E. Würbel. Réseaux de contraintes temporelles et spatiales. In F. Le Ber, G. Ligozat,

et O. Papini, editors, Raisonnements sur l'espace et le temps : des modèles aux applications, Trai^téIGAT - Géomatique, chapitre 7, pages 181-223. Lavoisier, 2007.

[12]

60

Bassam Baki. Ordonnancement et planification sous contraintes temporelles et probabilistes. Alexandre Vautier, Sylvie Saget. MajecSTIC 2005 : Manifestation des Jeunes Chercheurs francophones dans les domaines des STIC, Nov 2005, Rennes, France. pp.323-330. <inria- 00000669>

[13] F. Le Ber, G. Ligozat, et O. Papini, editors. Raisonnements sur l'espace et le temps : des modèles aux applications. TraitéIGAT - Géomatique. Lavoisier, Paris, 2007.