Algorithmes de réparation pour le raisonnement par Contraintes Dynamiques Centralisées et Distribuées.

Abstract

La programmation par contraintes (PC) est l'un des formalismes de l'intelligence artificielle pour traiter le problème NP-complet. CP est un formalisme élégant qui sépare les processus de modélisation/de résolution/à travers ses diverses extensions, il est capable d'exprimer/de résoudre de nombreux problèmes réels. Dans cette thèse, nous étendons l'état de l'art de la programmation par contraintes en proposant plusieurs modèles/algorithmes. Nous commençons par modéliser/résoudre un problème réel de planification i.e. la planification des stages médicaux dans les cas de satisfaction/d'optimisation. Après cela, parce que de nombreuses applications réelles sont dynamiques, nous avons proposé une heuristique appelée Pdeg qui est une extension profonde de l'heuristique connue deg, puis nous avons injecté/expérimenté cette heuristique pour améliorer l'algorithme Partial-order Dynamic Backtracking PDB. Deux algorithmes IPDB/LRB ont été proposés pour réparer la solution pré-perturbée des CSP dynamiques rapidement en termes de temps/efficacement en termes d'effort/de qualité de la solution. Toujours dans cette thèse, pour couvrir les CSP dynamiques distribués, nous proposons d'une part une nouvelle approche pour modéliser l'environnement de marché autonome intelligent (vente/achat de biens) pour faire face aux problématiques des e-marchés, d'autre part basée sur le célèbre algorithme ABT, nous avons proposé l'algorithme LiveABT pour traiter les CSP dynamiques distribués en temps réel, cet algorithme surpasse la version de réparation séquentiellement réalisée par l'algorithme DynABT.