LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
On Thursday 28/09/2017 and Friday 29/09/2017 due to system maintenance you might experience some downtimes to claim, search and validator services that will also affect the portal. We apologize for the inconvenience.
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Languages: French
Types: Article
Subjects: Intelligence Artificielle, Problèmes de Satisfaction de Contraintes, Ensembles de solutions, Interchangeabilité, 000, Artificial Intelligence, Constraint Satisfaction Problems, Sets of solutions, Interchangeability
Le formalisme des problèmes de satisfaction de contraintes (CSP) et les méthodes associées offrent un cadre théorique de plus en plus utilisé pour traiter les problèmes d'Intelligence Artificielle. Toutefois, la plupart des méthodes se concentrent sur le calcul d'une solution ce qui constitue un objectif trop limité. Nous introduisons dans cette thèse la notion de relation complète qui permet de calculer et de représenter de façon compacte des ensembles de solutions. Nous proposons d'abord une méthode qui génère une partition des solutions d'un CSP binaire par relations complètes Cette méthode met en œuvre une décomposition structurelle et une décomposition des contraintes par identification de symétries (calcul d'interchangeabilité). Sa complexité, qui est fonction de la taille d'un transversal minimal du graphe, n'est pas liée au nombre de solutions, à l'inverse des méthodes énumératives. Une évaluation expérimentale sur des problèmes jouets en démontrent le bon comportement. Nous montrons ensuite que cette méthode relève d'un schéma plus général qui consiste a résoudre le CSP dual d'un CSP pour obtenir une partition de ses solutions. Il est possible de construire un dual binaire pour tout CSP binaire : certaines classes polynomiales s'avèrent alors êtres stables par passage au dual binaire, assurant ainsi un coût polynomial pour le calcul d'un sous-ensemble des solutions. Nous proposons enfin une extension de l'algorithme backtrack standard pour le calcul de quelques solutions. Expérimentée sur problèmes aléatoires, cette extension entraîne un surcoût modeste par rapport au calcul d'une seule solution bien qu'elle fournisse en meilleur cas un nombre exponentiel de solutions. The framework of the Constraint Satisfaction Problems is widely used to tackle Artificial Intelligence problems. However, most CSP methods focus on the computation of a single solution which does not meet the requirements of real-life problems. We introduce in this thesis the notion of a complete relation which allows a compact representation of sets of solutions and eases their computation. We first present a method to partition the set of the solutions of a binary CSP with complete relations. This method combines structural decomposition and decomposition of the constraints by identifying symetries. Its time-complexity depends on the size of a minimal transversal of the graph but not on the number of solutions, the oppositive of enumerative methods. Experimental comparisons on puzzles confirm its efficiency. This method can be abstracted to define a general scheme that solves a dual CSP of a CSP to get a partition of its solutions. It is feasible to associate a binary dual CSP to every binary CSP: some polynomial CSP classes then prove to be stable via dual construction, hence ensuring a polynomial-time computation of a subset of the solutions. We eventually propose an extension of the standard backtrack algorithm to compute some solutions. Experiments on random problems show this extension has minimal overhead compared to the search for a single solution although it provides an exponential number of solutions in the best case.
  • No references.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article