Intelligence Artificielle
- Résolution automatique de problèmes -

Christine Solnon

1997


Remarque préliminaire : ce support de cours correspond à un module de 20 heures, destiné à des étudiants en deuxième année d'IUT. Ce cours n'est plus maintenu...



  1. Problèmes de plannification



1. Problèmes de plannification

De nombreux problèmes d'intelligence artificielle, pour lesquels on ne connait souvent pas d'algorithme déterministe, relèvent du problème général de plannification : étant donnés un état initial, un état final et un ensemble d'actions élémentaires ``valides'' permettant de passer d'un état à un autre, l'objectif est de trouver une séquence d'actions à exécuter pour passer de l'état initial à l'état final. La résolution automatique de ces problèmes consiste à essayer successivement toutes les possibilités jusqu'à trouver une solution. Cette recherche est fortement combinatoire : à partir d'un état donné, on peut généralement effectuer plusieurs actions élémentaires différentes qui débouchent sur des états différents. L'``intelligence'' consiste à trouver de bonnes règles -- appelées heuristiques -- permettant de choisir en premier les actions ``ayant le plus de chance d'aboutir''.
 
 

1.a. Qu'est ce qu'un problème de plannification ?

Plus formellement, un problème de plannification sera défini par un quadruplet tex2html_wrap_inline368tel que

1.b. Comment résoudre un problème de plannification ?

Résoudre un problème de plannification tex2html_wrap_inline368consiste à trouver une séquence

displaymath366

telle que tex2html_wrap_inline390tex2html_wrap_inline392, ..., tex2html_wrap_inline394et tex2html_wrap_inline396.

Pour cela, on peut effectuer une recherche globale et complète a travers l'espace des états, en construisant un arbre de recherche. L'arbre de recherche associé au problème tex2html_wrap_inline368est tel que:

Une solution d'un problème tex2html_wrap_inline368est alors un chemin dans l'arbre de recherche associé allant de la racine de l'arbre à une feuille étiquetée par un état final.

Remarques:

Algorithme de plannification en profondeur d'abord:

Construction de l'arbre ``en profondeur'', et recherche de la premiere solution ayant moins de K transitions.
Schéma d'appel de l'algorithme: cherche(E_0,{E_0},K)
fonctioncherche(E_i, Deja_vus, Nretourne un booleen
-- cherche(Ei,Deja_vus,N) = vrai
-- s'il existe une solution a (S,E_i,F,T) en moins de N  transitions.
-- Deja_vus est l'ensemble des etats par lesquels on est passe pour aller de E_0 a E_i.
debut
si E_i est un etat final de F  alors retourner vrai finsi
si N=0 alorsretourner faux finsi
Pour tout couple (A_j,E_j)  faisant partie de T(E_i)
     et tel queE_j n'appartienne pas a Deja_vus   faire
si cherche(E_j, Deja_vus U {E_j},N-1)=vrai
alors afficher(A_j,E_j)
      retourner vrai
finsi
finpour
retourner faux
fin

1.c. Différents types de problèmes de plannification

On distingue essentiellement trois types de problèmes de plannification :

1.d. Exemples de problème de plannification


2. Problèmes de Satisfaction de Contraintes

De nombreux problèmes sont définis en termes de contraintes (de temps, d'espace, ... ou plus généralement de ressources): Ces différents problèmes sont désignés par le terme générique CSP (Constraint Satisfaction Problems), et ont la particularité commune d'être fortement combinatoires: il faut envisager un grand nombre de combinaisons avant de trouver une solution. La programmation par contraintes est un ensemble de méthodes et algorithmes qui tentent de résoudre ces problèmes de la façon la plus efficace possible.

2.a. Qu'est ce qu'un CSP ?

Un CSP (Problème de Satisfaction de Contraintes) est un problème modélisé sous la forme de contraintes.

Définition

Un CSP est un triplet (X,D,C) tel que

Définition

Une affectation est un ensemble de couples variable/valeur

displaymath476

tel que tex2html_wrap_inline478et tex2html_wrap_inline480.
Une affectation est partielle si elle ne concerne qu'une partie des variables de X, et totale si elle concerne toutes les variables de X.
Une affectation A est valide par rapport à un ensemble de contraintes C si pour toute contrainte tex2html_wrap_inline490de C, la relation définie par tex2html_wrap_inline490est vraie pour les valeurs des variables définies dans A.
 
 

Définition

Une solution d'un CSP est une affectation totale et valide.
 
 

2.b. Comment résoudre un CSP ?

Certains CSPs bien délimités peuvent être résolus par des algorithmes spécialisés. Ces algorithmes tirent parti de leur connaissance sur la forme des contraintes ou sur le domaine des variables (CSP numériques, CSP booléens). L'objet de ce cours n'est pas d'étudier ces algorithmes spécialisés, mais de voir un certain nombre d'algorithmes généraux, qui peuvent être appliqués à n'importe quel CSP sur des domaines finis. Ces algorithmes sont parfois moins efficaces que des algorithmes spécialisés, mais ils peuvent être appliqués directement. Ces algorithmes sont notamment implémentés dans Charme, Chip, Ilog solver, Spart, clp(FD), PrologIV et Oz.

D'une façon générale, un CSP est un cas particulier de problème de plannification: les états sont des affectations valides (partielles ou totales), l'état initial est l'affectation vide, l'ensemble des état finaux est l'ensemble des affectations valides et totales, on passe d'un état à un autre en affectant une variable non encore affectée. De façon plus formelle, le CSP (X,D,C) correspond au problèmetex2html_wrap_inline368tel que:

Remarques:

L'algorithme "simple backtrack"

Principe: On affecte successivement des valeurs aux variables. A chaque fois qu'on affecte une valeur à une nouvelle variable, on vérifie que la nouvelle affectation est valide. Cet algorithme correspond à un parcours en profondeur d'abord de l'arbre de recherche.
fonction simple_backtrack( X,D,C ) retourne une affectation
   tex2html_wrap_inline514 
    Pour i de 1 a n faire
        /* l'affectation partielle  tex2html_wrap_inline522  est valide */ 
        Choix (*) d'une valeur  tex2html_wrap_inline524 ,
        si  tex2html_wrap_inline526  est valide alors  tex2html_wrap_inline528 
        sinon retour arriere au dernier point de choix (*) finsi
    finpour
    retourne A
Cet algorithme permet de construire de façon incrémentale une suite de valeurs cohérentes entre elles. Cet algorithme peut être amélioré, notamment:

L'algorithme d'``anticipation par vérification en avant''

Principe: On affecte successivement des valeurs aux variables. A chaque fois qu'on affecte une valeur à une nouvelle variable, on supprime du domaine des variables non affectées les valeurs qui ne sont pas compatibles avec l'affectation partielle.
fonction anticipation( tex2html_wrap_inline512 ) retourne une affectation
    tex2html_wrap_inline514 
    Pour i de 1 a n faire
    /* l'affectation partielle  tex2html_wrap_inline522  est valide */
    /* et  tex2html_wrap_inline542  est valide */
        Choix (*) d'une valeur  tex2html_wrap_inline524 ,
        tex2html_wrap_inline528 
        Pour j de i+1 a n faire
            tex2html_wrap_inline554  est valide }
            si  tex2html_wrap_inline556 
            alors retour arriere au dernier point de choix (*) finsi
        finpour
    finpour
    retourne A
 

 

L'algorithme ``choix du plus petit domaine''

Principe: A chaque itération, on choisit d'affecter la variable dont le domaine est le plus petit, puis on restreint les domaines des variables non affectées par vérification en avant.
fonction min_domaine( tex2html_wrap_inline512 ) retourne une affectation
    tex2html_wrap_inline514 
    Pour i de 1 a n faire
        Soit  tex2html_wrap_inline568  la variable de X non affectee dans A
        et telle que la taille de  tex2html_wrap_inline574  soit minimum
        Choix (*) d'une valeur  tex2html_wrap_inline576 ,
        tex2html_wrap_inline578 
        Pour toute variable  tex2html_wrap_inline580  de X  non affectee dans A
        faire
            tex2html_wrap_inline554  est valide }
            si  tex2html_wrap_inline556   
            alors retour arriere au dernier point de choix (*) 
            finsi
        finpour
    finpour
    retourne A
 

2.d. Exemples de CSP


Bibliographie


Christine SOLNON

Thu Jul 10 10:26:38 METDST 1997