Fondements de l’intelligence artificielle
Unité 3: Résolution de problème
Partie 1 : Modélisation et Espace de Recherche
Redoaune Ezzahir
[Link]@[Link]
Plan
Agents planifier à l’avance
Résolution de problèmes : quel type de problème?
Formalisation d’un problème de recherche
Espace d’états vs Espace du monde
État
Taille de l’espace
Composantes et considérations de la stratégie de recherche
Évaluation de la stratégie de recherche
Complète?
Optimale?
complexité spatiale et temporelle?
Agents planifier à l'avance
Agent basé sur but (Goal-based Agent)
Agent basé sur utilité (Utility-based agent)
Utilisé pour la résolution
de problème de recherche
Image from slides
SP14 CS188 Lecture 2
by Dan Klein and Pieter Abbeel for CS188 Intro to AI at UC Berkeley.
available at [Link]
Agent réflexe (Rappel)
Choisit une action en fonction de
la perception actuelle (et peut-être
de la mémoire)
Peut avoir une mémoire ou un
modèle de l'état actuel du monde
Mais ne tient pas en compte les
conséquences futures de ses
actions
Il considère seulement l’état du
Image from slides
monde au moment de SP14 CS188 Lecture 2
délibération. by Dan Klein and Pieter Abbeel for CS188 Intro to AI at UC Berkeley.
available at [Link]
Un agent réflexe peut-il être optimal/rationnel ?
Quiz (rappel)
Parmi les affirmations suivantes sur la rationalité, lesquelles sont vraies ?
A. Le fait qu'un agent soit rationnel dépend de sa mesure de performance,
de ses connaissances préalables, de ses actions possibles et de sa
séquence de perception.
B. Un agent qui est rationnel dans un environnement de réalisation de
tâches peut être irrationnel dans un autre environnement.
C. Si un agent entreprend une action et encourt une pénalité (basée sur la
mesure de la performance), alors c'est irrationnel même s'il n'aurait pas pu
anticiper la pénalité sur la base de sa connaissance préalable et de sa
séquence de perception.
Agent réflexe (Illustration)
agent réflexe pur rationnel agent réflexe pur irrationnel
from CS 188 Artificial Intelligence, UC Berkeley, Spring 2014 Lecture 2 Uninformed Search, Instructor: Prof. Pieter Abbeel
Agents planifier à l'avance
Pac-Man : Recherche d’un plan pour manger tous les points
from CS 188 Artificial Intelligence, UC Berkeley, Spring 2014 Lecture 2 Uninformed Search, Instructor: Prof. Pieter Abbeel
Agents planifier à l'avance
planifier de consommer le point le plus proche, puis planifier de consommer
Re-planifier le point suivant et ainsi de suite jusqu'à ce que le but est atteint
from CS 188 Artificial Intelligence, UC Berkeley, Spring 2014 Lecture 2 Uninformed Search, Instructor: Prof. Pieter Abbeel
Résolution de problèmes
Quel problème ?
Nous nous intéressons à la résolution des problèmes combinatoires qui se posent dans de nombreux
domaines de l’intelligence artificielle et des applications informatiques.
Exemples :
trouver les trajets aller-retour les plus courts et les moins coûteux;
planification, ordonnancement
Emplois des temps des infirmières
Un problème combinatoire est un problème dans lequel des solutions sont construites
en combinant un certain nombre d’objets (valeurs des variables) tout en satisfaisant
certaines conditions définies par le problème.
Problèmes de recherche
Un problème qui peut être abréger au problème
mathématique de recherche de chemin d’un noeud de
départ à un noeud but dans un graphe dirigé.
De nombreux problèmes réels peuvent être associés
à cette abstraction
Il est donc util de considérer ce niveau d’abstraction
Les problèmes de recherche sont des Modèles
by Leon Zernitsky from [Link]
from CS 188 Artificial Intelligence, UC Berkeley, Spring 2014
Lecture 2 Uninformed Search, Instructor: Prof. Pieter Abbeel Graphe dirigé
Qu’est-ce que la recherche?
La recherche est une classe d’algorithmes pour trouver ou construire systématiquement des
solutions aux problèmes de recheche.
Exemple de technique : Générer-et—tester.
Exemple de problème : Serrure à combinaison
1. Générer une solution possible.
2. Tester la solution.
3. Si la solution n’est pas trouvée ALORS
4. Retournez à l’étape 1.
Pourquoi la recherche est-elle intéressante?
De nombreux (tous?) problèmes d’IA peuvent être formulés
comme des problèmes de recherche!
Exemples :
panification/ordonnancement Jeux
Recherche de chemin
Problèmes de recherche
Un problème de recherche consiste en :
Problèmes de recherche
Un problème de recherche consiste en :
Un espace d’état :
Problèmes de recherche
Un problème de recherche consiste en :
Un espace d’état :
un état de départ:
Problèmes de recherche
Un problème de recherche consiste en :
Un espace d’état :
un état de départ:
"U", 1.0
une fonction successeur (avec actions, coûts) :
"R", 1,0
Problèmes de recherche
Un problème de recherche consiste en :
Un espace d’état :
un état de départ:
"U", 1.0
une fonction successeur (avec actions, coûts) :
"R", 1,0
et un test de l’objectif (c’est une fonction)
Une solution est une séquence d’actions (un plan) qui transforme l’état de départ en un état but
Etat de l’espace (State Space) ?
L’état du monde comprend tous les détails de l’environnement
Couleur pac-man, point, bornes, …
Un état de recherche ne conserve que les détails nécessaires à la recherche de
solution (plan d’action)
c’est une abstraction (ou modèle)
Problème : recherche de chemin (Pathing) Problème : Manger tous les points (PacMan)
États : les positions (x, y) États : { (x, y, b) / b: point booléen}
Actions : U, D, L, R
Actions : U, D, L, R
Successeur : mettre à jour l’emplacement
Successeur : emplacement de mise à et éventuellement un point booléen
jour seulement
Test de but : tous les points booléens sont
Test de but : est ce que (x, y) = FIN à faux
Quiz : Taille de l’espace d’état et de monde?
Combien
État du monde : États du monde?
Positions de l’agent : 120
Etats pour le problème
Nombre d’aliments : 30
Pathing?
Positions des fantômes : 12
Actions : U, D, L, R Etats pour le problème
Mangez tous les points?
Quiz : Taille de l’espace d’états et de monde?
Combien
État du monde : États du monde?
Positions de l’agent : 120 120x(230)x(122)x4
Etats pour le problème
Nombre d’aliments : 30
Pathing?
120
Positions des fantômes : 12
Actions : U, D, L, R Etats pour le problème
Mangez tous les points?
120x(230)
Graphe d’espace d’états
Graphe d’espace d’état : Représentation mathématique d’un problème de recherche
Les nœuds sont des configurations (abstraites) du monde
Les arcs représentent les successeurs (résultats de l’action)
Le test de buts: un noeud parmi l’ensemble des nœuds buts (peut être unique)
Dans un graphe d’espace d’état, chaque état ne se produit qu’une seule fois !
Nous pouvons (rarement) construire ce graphe complet en mémoire
(il est en générale de très grande taille), mais c’est une idée utile
a
b G
c
d
e r f
S h
p
q
Petit graphe de recherche pour un petit problème de recherche
Graphe d’espace d’états du monde robot aspirateur
États ? emplacement du robot et sa propreté
Actions? Left, Right, Suck
Test de but? Tous les pièces sont propres
Coût ? 1 par movement, 100 par aspiration de saleté
Exemple :Jeu du taquin
8-puzzle
État initial État but
États? Emplacements de huit carreaux (1,2,…,8) et blanc (0) dans les 9 carrés
==> Matrice, Vecteur ou liste ordonnée d’objets [{n, (x, y)}]
Actions? Déplacement du vide (dans le tableau): Left, Right, Up, Down
Test de but? Identique à l’état de l’objectif ci-dessus
Coût du parcours? 1 par mouvement
Exemple 2
Problème du monde des blocs ( blocks world problem)
Considérons une version simple du problème du monde des blocks, dans laquelle il y a cinq
blocs de forme et de taille identiques, numérotés de 1 à 5. La figure ci-dessous montre deux
configurations possibles de tels blocs ; noter que la position relative des blocs n'a pas
d'importance, donc la configuration de gauche est équivalente à celle au milieu. Chaque bloc
peut être soit sur la table (il n'y a pas de contraintes sur le nombre de piles) ou au sommet
d'un autre bloc. Le but est d'empiler les blocs en une seule pile, dans l'ordre indiqué dans le
configuration la plus à droite de la figure, à partir de n'importe quel ensemble de piles donné,
en déplaçant le plus petit possible nombre de blocs.
Seuls les blocs en haut des piles actuelles peuvent être déplacés, et ne peuvent être placés
que sur la table ou sur une autre pile.
5
2
3
2 1 4
3
1 4 5 2
2 3 5 3
1 4 5 1 4
1
3 2 2
2
1 4 5 1 3
3 3
1 4 5 2 4 5 4 5
2
3
1 4 5
Exemple 2 (Etats)
Formulation d’état : un ensemble de piles :
state = set(stack_1, stack_2, …, stack_p) tel que
2
2 3
3 3
1 4 5 2
1 4 5 1 4 5
1 = {[1, 2], [4, 3], [5], [], []} 2 = {[1], [4, 3, 2], [5], [], []} 3 = {[1], [4, 3], [2], [5], []}
Quelle est la taille de l’espace d’états ? def blocks_space_size(n):
if n==1:
Size(N) = 1 + N * Size(N-1) return 1
return 1+n*blocks_space_size(n-1)
Size(1) = 1
print(blocks_space_size(5)) # 206
𝑠
𝑠
𝑠
Arbres de recherche
Un arbre de recherche :
Un « scénario hypothétique » de plan d’actions (PLANS ) et de leurs résultats
c’est une hiérarchie de nœuds liés où chaque nœud représente un état particulier.
L’état de départ est le noeud racine
Les noeuds peuvent avoir plusieurs noeuds fils, un, ou aucun.
Les noeuds fils correspondent aux successeurs
Les nœuds indiquent les états, mais correspondent aux PLANS qui atteignent ces états
Pour la plupart des problèmes, nous ne pouvons jamais construire l’arbre entier
État de départ : noeud racine
"U", 1.0 "R" 1,0
Etats successeurs possibles
Recherche et modele
La recherche opère sur des modèles du monde
L'agent n'essaie pas vraiment tous les plans dans le
monde réel !
La planification est en faite "une simulation"
Votre recherche est aussi bonne que vos modèles ...
Arbres de recherche
Frontière et exploration a G
b c
e
d f
n Ensemble exploré (explored) : stocke les états que S h
nous avons déjà examinés (et n’ont pas besoin
p q r
d’être revus).
Souvent stocké à l’aide d’une structure de
données qui permet une recherche rapide S
pour les tests d’appartenance.
d e p
Frontière : stocke l’ensemble de nœuds qui sont b e h r q
n c
disponibles pour être examinés dans les
prochaines étapes de la recherche. Souvent a h r p q f
représenté comme une pile, une file d’attente ou a
une file d’attente prioritaire. p q f q c G
q c G a
Pas encore exploré ni à la frontière
Graphe de l’espace d’états vs arbres de recherche
Graph de l’espace d’état Chaque NŒUD dans Arbre de recherche
l’arbre de recherche est
un CHEMIN entier
dans le graphe de S
l’espace d’état.
un G d e p
b c
b c e h r q
e Nous construisons
d f h r p q f
les deux sur a a
S h demande
p q f q c G
p q r &
nous construisons le q c G a
moins possible.
a
Algorithme de recherche arborescente
Idée de base :
exploration simulée hors ligne de l’espace d’état en générant les
successeurs des états déjà explorés
function TREE-SEARCH( problem) returns a solution, or failure
initialize the frontier using the initial state of problem
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then
return the corresponding solution
expand the chosen node, adding the resulting nodes to the frontier
Question principale :
Quels sont les nœuds de la frontière à explorer ?
Stratégies
Quiz : Graphes d’espace d'état et arbres de recherche
Considérons le graphe à 4 états suivant: Quelle est la taille de son arbre de recherche (de S à G)?
Il est
∞ S
a
a b
S G
G b G a
b
G b
Important :
Beaucoup de structures répétées dans l’arbre de recherche!
La défaillance de détection des états répétés peut transformer un problème linéaire
en un problème exponentiel !
Les algorithmes qui oublient leur histoire sont condamnés à le répéter.
Recherche graphique
Recherche graphique
function TREE-SEARCH( problem) returns a solution, or failure
initialize the frontier using the initial state of problem
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then
return the corresponding solution
expand the chosen node, adding the resulting nodes to the frontier
function GRAPH-SEARCH( problem) returns a solution, or failure
initialize the frontier using the initial state of problem
initialize the explored set to empty
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then
return the corresponding solution
add the node explored set
expand the chosen node, adding the resulting nodes to the frontier
only if not in the frontier or explored set
Prochaine séance : Stratégie de recherche
Une stratégie de recherche est définie par l’ordre développement des nœuds
Recherche aveugle (Prochaine séance)
Recherche en largeur d’abord (BFS)
Recherche en profondeur d’abord (DFS)
Recherche en profondeur limitée (LDS)
Recherche d’approfondissement itératif (IDS)
Recherche éclairée :
UCS
recherche glouton
A*
Satisfaction de contraintes
Recherche pour des jeux avec des adversaires (adversarial search)