CoursIA 1

Introduction l'intelligence articielle Chapitre II: Logique des prdicats Langage Prolog : Notions de Base Repsentat
Repsentation et rsolution de problmes en IA
Formulation en espaces d'tats
Algorithmes de recherche
Support de cours Introduction l'Intelligence Articielle
108
Aymen Chaabouni ayman.chaabouni@ieee.org

Dnition formelle d'un problme
Un problme est dni par:
un tat initial
un ensemble d'actions
une fonction de successeur qui dnit l'tat rsultant de

l'xcution d'une action dans un tat
un ensemble d'tats buts
une fonction de cot, associant chaque action un nombre

non-ngatif (le cot de l'action)
Une solution est une squence d'actions joignant l'tat initial un

tat but.
109

Exemple: Jeu de taquin
Etats: emplacement des carreaux.

Actions : haut, bas, gauche, droite
Test de but: l'tat but est unique et x au dbut du jeu
Cot des actions: chaque mouvement a un cot de 1
110

Exemple: Robot manipulateur
Etats: conguration du bras, objets rassembler.

Actions : haut, bas, gauche, droite.
Test de but: l'tat but est unique et x au dbut du jeu.
Cot des actions: chaque mouvement a un cot de 1.
111

Exemple: Huit reines
Etats: Toute conguration de 0 8 reines sur la grille.

Actions : ajouter une reine sur l'chiquer
Test de but: Une conguration de huit reines avec aucune reine
sous attaque.
Cot des actions:
un cot constant pour chaque action.
112

Exemple: Le problme du loup, de la chvre et du choux
Un loup, une chvre et un choux se trouvent sur la rive gauche
d'une rivire. Comment les faire traverser de l'autre cot l'aide
d'une barque ne contenant que deux places (dont une pour le
fermier) sachant que si le loup et la chvre restent sur la mme rive
la chvre sera mange et que si la chvre et le choux restent
ensemble c'est le choux qui sera mang ?
Donner la description d'un tat et a dnition de l'tat initial

et l'tat nal.
Donner une reprsentation d'espace d'tats de ce problme.
113

Structure gnrale d'un algorithme de recherche
La plupart des algorithmes de recherche suivent peu prs le mme

schma :
s'il n'y a plus d'tats traiter, renvoyez echec
sinon, choisir un des tats traiter (?)
si l'tat est un tat but, renvoyez la solution correspondante
sinon, supprimer cet tat de l'ensemble des tats traiter, et

le remplacer par ses tats successeurs
Ce qui va direncier les dirents algorithmes est la manire dont

on eectue le choix l'tape (?).
114

Evalution des algorithmes de recherche
Les critres utilises pour comparer les dirents algorithmes de
recherche :
Complexit en temps Combien du temps prend l'algorithme

pour trouver la solution ?
Complexit en espace Combien de mmoire est utilise lors de

la recherche d'une solution ?
Compltude Est-ce que l'algorithme trouve toujours une

solution s'il y en a une ?
Optimalit Est-ce que l'algorithme renvoie toujours des

solutions optimales ?
115

Complexit
La complexit en temps et en espace sont mesures par :
b:
facteur de branchement maximal de l'arbre de recherche
(nombre d'tats successeurs d'un tat donn)
d: profondeur de la solution de moindre cot

m: profondeur maximale de l'espace de recherche
116

Algorithmes non informs

Aucune connaissance sur le problme part l'espace d'tat et le
cot de dveloppement.
Largeur d'abord
Profondeur d'abord
Algorithmes informs
- Fonction d'valuation f(n) pour choisir le noeud dvelopper
- Utilisation d'une heuristique pour rduire la complexit.
Meilleur d'abord
A?
117
Recherche en largeur
tendre le noeud le moins profond
nous examinons d(abord l'tat initial, puis ses successeurs, puis

les successeurs des successeurs, etc.
Insertion des successeurs la n de la le d'attente
118
Recherche en largeur
119
Recherche en profondeur
tendre le noeud le plus profond
il faut tout simplement mettre des successeurs du noeud

courant au dbut de la liste de noeuds traiter (insertion des
successeurs en tte de la le d'attente)
120
Recherche en profondeur
121
Recherche en cot uniforme
tendre le noeud de cot le plus faible

insertion des successeurs dans l'ordre croissant des cots de
chemin
122

proprits de la recherche par heuristique
Les algorithmes de recherche simple n'exploitent aucune
information concernant la structure de l'arbre de recherche ou la

prsence potentielle de noeuds-solution pour optimiser la recherche.
Une heuristique doit guider le choix des tats tester et les
ordonner selon leurs promesses de rapprocher d'un but.
123

Recherche Heuristique
Soit n un noeud du graphe
g*(n) est dni comme le le cot minimum entre le noeud de

dpart n0 et le noeud n
h*(n) est le minimum du cot des chemins du noeud n un

noeud but quelconque.
f*(n) = g*(n) + h*(n) est le cot du chemin solution optimal

passant par n.
Il est donc ncessaire de dnir :
une heuristique h(n) qui estime h*(n)
g(n) le gain, le cot eectif du meilleur chemin connu pour

aller de n0 n (c'est un estimateur de g*(n))
f(n) = g(n) + h(n) , la fonction d'valuation du noeud n

124
Algorithme AF
tendre le noeud dont la valeur f(s) = g(s) + h(s) est la plus

faible
insertion des successeurs dans la liste dans l'ordre croissant des

valeurs de f(n)
125
Algorithme AF
126

proprits de la recherche par heuristique
Cas particuliers
F
si
n;
h(n) = 0, alors f(n)=g(n) ; l'algorithme est quivalent
une recherche en largeur
si
n;
f (n) = h(n), l'algorithme est quivalent une recherche
en profondeur
127
Problmes de satisfaction de contraintes
Dnition
Un problme de satisfaction de contraintes
ou
CSP
(Constraint Satisfaction Problem), est un problme o l'on cherche

des tats ou des objets satisfaisant un certain nombre de
contraintes ou de critres. Il est modlis sous la forme d'un
ensemble de contraintes poses sur des variables, chacune de ces
variables prenant ses valeurs dans un domaine.
128

Dnition et notations
De faon plus formelle, un
CSP est dni par un triplet (X,D,C) tel
que:
X = {X1 , ..., Xn } est un ensemble ni de variables rsoudre,

D est un ensemble des domaines {DX1 , ..., DXn } (ensembles des
valeurs possibles) pour ces variables
C = {C1 , ..., Cm } est un ensemble ni de contraintes.

Exemple
X = {a, b, c, d}
D(a) = D(b) = D(c) = D(d) = {0, 1}
C = {a
6=
b, c
6=
d, a + c < b}
129

Dnition et notations
Une aectation est un ensemble de couples (variables-valeurs):

A={Xj
vj }
avec
Xj
X et
vj D(Xj )
Une aectation est partielle si elle ne concerne qu'une partie

de variables et totale sinon.
Une aectation
A est valide par rapport C si la relation
dnie dans chaque contrainte

des variables aectes dans
A.
Ci
est vrie pour les valeurs
Une aectation est le fait d'instancier des variables.

A = (X1,V1), (X3,V3), (X4,V4)
associe la valeur V1 de D1 la variable X1...
Une
solution est une aectation totale consistante.
130

Problem
X = {a, b, c, d}
D(a) = D(b) = D(c) = D(d) = {0, 1}
C = {a
6=
b, c
6=
d, a + c < b}
A1
A2
= {(a, 1), (b, 0), (c, 0), (d, 0)}
A3
A4
= {(a, 1), (b, 0)}
= {(a, 0), (b, 0)}
= partielle, inconsistante
= partielle, consistante
= {(a, 0), (b, 1), (c, 0), (d, 1)}
A est donc une solution
= totale, inconsistante
= totale, consistante
4
Support
de cours Introduction l'Intelligence Articielle
131

Modlisation d'un CSP
Problme1: Send more money

On considre l'addition suivante :
SEND
+ MORE

= MONEY
o chaque lettre reprsente un chire dirent (compris entre 0 et
9). On souhaite connatre la valeur de chaque lettre, sachant que la
premire lettre de chaque mot reprsente un chire dirent de 0.
Modlisez ce problme sous la forme d'un CSP.
132

Problme1: Send more money (Solution)
Variables
on associe une variable chaque lettre

X = S,E,N,D,M,O,R,Y
Domaines
les variables correspondant au premier chire d'un mot (S et M)
doivent prendre une valeur dirente de 0.

D(S) = D(M) = {1,2,3,4,5,6,7,8,9}
les autres variables peuvent prendre n'importe quelle valeur entre
0 et 9.
D(E) = D(N) = D(D) = D(O) = D(R) = D(Y) =
{0,1,2,3,4,5,6,7,8,9}
133

Problme1: Send more money (Solution)
Contraintes
Une premire contrainte exprime le fait que
SEND+MORE=MONEY :
C1 = 1000*S + 100*E + 10*N + D
+ 1000*M + 100*O + 10*R + E
= 10000*M + 1000*O + 100*N + 10*E + Y
Une seconde contrainte exprime le fait que toutes les variables
doivent prendre des valeurs direntes. On peut utiliser pour cela la

contrainte globale toutes-direntes
C2 = toutesdirentes( S,E,N,D,M,O,R,Y)
134

Problme2: Coloriage d'une carte

Il s'agit de colorier les 14 rgions de la carte ci-dessous, de sorte
que deux rgions ayant une frontire en commun soient colories
avec des couleurs direntes. On dispose pour cela des 4 couleurs
suivantes : bleu, rouge, jaune et vert.
135

Problme2: Coloriage d'une carte (Solution)
Variable
X =
X1 , X2 ,
...,
X14
(On associe une variable
Xi
dirente par
rgion i colorier.)
Domaines
pour tout
Xi
lment de X, D(Xi ) = { bleu, rouge, vert, jaune }
(Chaque rgion peut tre colorie avec une des 4 couleurs.)
Contraintes
C = {
Xi 6= Xj
Xi
et
Xj
sont 2 variables de X correspondant
des rgions voisines }

(2 rgions voisines doivent tre de couleurs direntes.)
on peut dnir explicitement les relations de voisinage entre
rgions, par exemple l'aide d'un prdicat voisines/2, tel que
voisines(X,Y) soit vrai si X et Y sont deux rgions voisines.

136

Problme2: Coloriage d'une carte (Solution)

?
on peut dnir explicitement les relations de voisinage entre
rgions, par exemple l'aide d'un prdicat voisines/2, tel que

voisines(X,Y) soit vrai si X et Y sont deux rgions voisines.
Ce prdicat peut tre dni en extension, en listant l'ensemble
des couples de rgions ayant une frontire en commun :

voisines(X,Y)
(X,Y) lment-de { (1,7), (1,9), (1,10), (1,11),
(1,12), (1,13), (2,8), (2,12), (2,14), (3,7), (3,10), (3,14), (4,9),

(4,11), (4,14), (5,8), (5,11),
.....
(14,2), (14,3), (14,4), (14,6), (14,7), (14,10), (14,12), (14,13) }
137

Exercice : le retour de monnaie

On s'intresse un distributeur automatique de boissons.
L'utilisateur insre des pices de monnaie pour un total de T
centimes d'Euros, puis il slectionne une boisson, dont le prix est de
P centimes d'Euros (T et P tant des multiples de 10). Il s'agit
alors de calculer la monnaie rendre, sachant que le distributeur a
en rserve
centimes,
E2 pices de 2 e , E1 pices de 1e , C50 pices de 50

C20 pices de 20 centimes et C10 pices de 10 centimes.
Modlisez ce problme sous la forme d'un CSP.
138

Exercice : le retour de monnaie

Variables
X = {XE 2 ,
o
XE 2
XE 1 , XC 50 , XC 20 , XC 10 }
dsigne le nombre de pices de 2 Euros retourner, , ...
Domaines
D(XE 2 ) = {0,1,...,E2 },
D(XC 50 ) = {0,1,...,C50 },
D(XC 10 ) = {0,1,...,C10 }
Contraintes
D(XE 1 ) = {0,1,...,E1 }
D(XC 20 ) = {0,1,...,C20 }
Les contraintes spcient que la somme retourner doit tre gale

la somme insre moins le prix payer :
C = { 200*XE 2 + 100*XE 1 + 50*XC 50 + 20*XC 20 + 10*XC 10 =
T-P }
139

CoursIA 1

Transféré par

Droits d'auteur :

Formats disponibles

CoursIA 1

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

CoursIA 1

Transféré par

Droits d'auteur :

Formats disponibles

Introduction l'intelligence articielle Chapitre II: Logique des prdicats Langage Prolog : Notions de Base Repsentat

Repsentation et rsolution de problmes en IA

Formulation en espaces d'tats

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

une fonction de successeur qui dnit l'tat rsultant de

un ensemble d'tats buts

une fonction de cot, associant chaque action un nombre

Une solution est une squence d'actions joignant l'tat initial un

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

Etats: emplacement des carreaux.

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

Etats: conguration du bras, objets rassembler.

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

Etats: Toute conguration de 0 8 reines sur la grille.

Cot des actions:

un cot constant pour chaque action.

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

Donner la description d'un tat et a dnition de l'tat initial

Donner une reprsentation d'espace d'tats de ce problme.

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

La plupart des algorithmes de recherche suivent peu prs le mme

s'il n'y a plus d'tats traiter, renvoyez echec

sinon, choisir un des tats traiter (?)

si l'tat est un tat but, renvoyez la solution correspondante

sinon, supprimer cet tat de l'ensemble des tats traiter, et

Ce qui va direncier les dirents algorithmes est la manire dont

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

Complexit en temps Combien du temps prend l'algorithme

Complexit en espace Combien de mmoire est utilise lors de

Compltude Est-ce que l'algorithme trouve toujours une

Optimalit Est-ce que l'algorithme renvoie toujours des

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

La complexit en temps et en espace sont mesures par :

facteur de branchement maximal de l'arbre de recherche

(nombre d'tats successeurs d'un tat donn)

d: profondeur de la solution de moindre cot

Support de cours Introduction l'Intelligence Articielle

Repsentation et rsolution de problmes en IA

Algorithmes non informs

Support de cours Introduction l'Intelligence Articielle

tendre le noeud le moins profond

nous examinons d(abord l'tat initial, puis ses successeurs, puis

Insertion des successeurs la n de la le d'attente

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

tendre le noeud le plus profond

il faut tout simplement mettre des successeurs du noeud

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

tendre le noeud de cot le plus faible

Support de cours Introduction l'Intelligence Articielle

Introduction l'intelligence articielle Chapitre II: Logique des prdicats Langage Prolog : Notions de Base Repsentat

Support de cours Introduction l'Intelligence Articielle

une fonction de successeur qui dnit l'tat rsultant de

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Etats: conguration du bras, objets rassembler.

Support de cours Introduction l'Intelligence Articielle

Etats: Toute conguration de 0 8 reines sur la grille.

Support de cours Introduction l'Intelligence Articielle

Donner la description d'un tat et a dnition de l'tat initial

Support de cours Introduction l'Intelligence Articielle

Ce qui va direncier les dirents algorithmes est la manire dont

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Insertion des successeurs la n de la le d'attente

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

g*(n) est dni comme le le cot minimum entre le noeud de

f(n) = g(n) + h*(n) est le cot du chemin solution optimal

Il est donc ncessaire de dnir :

g(n) le gain, le cot eectif du meilleur chemin connu pour

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

CSP est dni par un triplet (X,D,C) tel

X = {X1 , ..., Xn } est un ensemble ni de variables rsoudre,

C = {C1 , ..., Cm } est un ensemble ni de contraintes.

Support de cours Introduction l'Intelligence Articielle

Une aectation est un ensemble de couples (variables-valeurs):

Une aectation est partielle si elle ne concerne qu'une partie

dnie dans chaque contrainte

est vrie pour les valeurs

Une aectation est le fait d'instancier des variables.

solution est une aectation totale consistante.

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle

doivent prendre une valeur dirente de 0.

Support de cours Introduction l'Intelligence Articielle

doivent prendre des valeurs direntes. On peut utiliser pour cela la

Support de cours Introduction l'Intelligence Articielle

Support de cours Introduction l'Intelligence Articielle