Algorithmes d’exploration
Luc LamontagnePLT [email protected]
Tiré du matériel de Brahim Chaib-draa (A09)
1
Planification de trajectoire
Représentation continue(espace des configurations)
Discrétisation
Recherche dans un graphe(blind, best-first, A*) Le contenu de
cette section
Recherche dans un graphe
3
environnement représentation discrète
représentation par graphe
Plan
Agent de résolution de problèmes
Stratégies de recherche
Recherche non-informée
Largeur d’abord, profondeur d’abord, etc.
Recherche informée
Meilleur d’abord, A*, etc.
Quelques exemples
4
5
Rappel - Agent basé sur les buts
Capteurs
Comment le monde est maintenant?
Quelle action dois-je faire maintenant?
Effecteurs
Agent
En
viron
nem
ent
État
Comment le monde évolue?
Quel est l’impact de mes actions? Comment sera le mondesi je fais l’action A?
Buts
Goal-based agent
6
Agent basé sur les buts :
Agent de résolution de problèmes
1. Formulation d’un but: Un état à atteindre.
2. Formulation du problème: Les états et les actions à considérer.
3. Exploration de solution: Examiner les différentes séquences d’actions
menant à un état but; Et choisir la meilleure.
4. Exécution: Accomplir la séquence d’actions sélectionnées.
7
Agent basé sur les buts :
Agent de résolution de problèmes
8
Exemple de formulation de problèmes :
Planification de route
9
Exemple de formulation de problèmes :
Planification de route On est à Arad et on veut aller à Bucharest
Problème: États : villes Actions : aller d’une ville à une autre.
But : Être à Bucharest
Solution : Une séquence de villes. Par ex. Arad, Sibiu, Fagaras, Bucharest
Coût : Distance entre les deux villes (en km)
Environnement simple statique, observable, discret et déterministe
10
Exemple de formulation de problèmes :
8-puzzle
États : Positions des huit tuiles dans les cases.
État initial : Les huit tuiles dans n’importe quelle case.
Actions : Déplacement du trou
droite, gauche, haut, bas. Test de but :
Un état qui correspond à l’état final. Coût :
Chaque action coûte 1.
1 2 3
4 5 6
7 8
État but
5 7 3
8
6
1
4 2
État initial
11
Exemple de formulation de problèmes :
8-reines États
Une configuration de 0 à 8 reines sur l’échiquier.
État initial Aucune reine sur l’échiquier.
Actions Ajouter une reine sur une case vide.
Test de but Les 8 reines sont placés sur
l’échiquier sans attaque. Coût
Chaque action coûte 1 (sans intérêt!).
12
Exploration de solutions dans un arbre
Exloration obtenue par simulation On simule l’exploration de l’espace d’états en générant
des successeurs pour les états déjà explorés. Exploration de type hors-ligne (offline)
13
Exemple d’exploration dans un arbre
14
Exemple d’exploration dans un arbre
15
Exemple d’exploration dans un arbre
16
Exploration dans un arbre : Mise en oeuvre
17
Exploration de solutions dans un arbre
Simuler l’exploration de l’espace d’états en générant des successeurs pour les états déjà explorés.
Nœud de recherche État: l’état dans l’espace d’état. Nœud parent: Le nœud dans l’arbre de recherche qui a généré ce
nœud. Action: L’action qui a été appliquée au parent pour générer ce nœud. Coût du chemin: Le coût g(n) du chemin à partir de l’état initial jusqu’à
ce nœud. Profondeur: Le nombre d’étapes dans le chemin à partir de l’état initial.
18
Stratégies d’exploration
Détermine l’ordre de développement des nœuds. Explorations non informées
Aucune information additionnelle. Elles ne peuvent pas dire si un nœud est meilleur qu’un autre. Elles peuvent seulement dire si l’état est un but ou non.
Explorations informées (heuristiques): Elles peuvent estimer si un nœud est plus prometteur qu’un
autre.
19
Évaluation des stratégies
Complétude: Est-ce que l’algorithme garantit de trouver une
solution s’il y en a une? Optimalité:
Est-ce que la stratégie trouve la solution optimale? Complexité en temps:
Combien de temps pour trouver une solution? Complexité en espace:
Quelle quantité de mémoire a-t-on besoin?
20
Complexité
Elle est exprimée en utilisant les quantités suivantes B : le facteur de branchement
c.-à-d. le nombre maximum de successeurs à un nœud. D : la profondeur du nœud but le moins éloigné. M : la longueur maximale d’un chemin dans l’espace d’états.
Complexité en temps le nombre de nœuds générés pendant la recherche.
Complexité en espace le nombre maximum de nœuds en mémoire.
21
Stratégies d’exploration non informées
Largeur d’abord (Breath-first - BFS)
Coût uniforme (Uniform-cost - UFS)
Profondeur d’abord (Depth-first - DFS)
Profondeur limitée (Depth-limited - DLS)
Itérative en profondeur (Iterative deepening - IDS)
Bidirectionnelle (Bidirectional search)
22
Largeur d’abord (BFS)
Approche Développer tous les noeuds au niveau i Développer par la suite tous les nœuds au niveau i+1 Et ainsi de suite…
Implémenté à l’aide d’une file. Les nouveaux successeurs vont à la fin.
23
A
B C
D E F G
Exemple largeur d’abord
A
B C
D E F G
B C
File:
D E F G
Ordre de visite: A – B – C – D – E – F - G
24
Propriétés de largeur d’abord
Complétude : oui, si b est fini Complexité en temps : O(bd)
1 + b + b2 + b3 + … + bd = O(bd) Complexité en espace : O(bd)
Garde tous les nœuds en mémoire Optimal : non en général.
Oui si le coût des actions est le même pour toutes les actions
Profondeur Nœuds (b=10)
Temps(1 millions nœuds/sec)
Mémoire(1000 octets/ nœuds)
8 108 2 minutes 103 gigaoctet
12 1012 13 jours 1 pétaoctets
25
Coût uniforme (UCS)
Développe le nœud ayant le coût le plus faible.
g(n) := coût du nœud initial au nœud développé.
File triée selon le coût.
Si le coût des actions est toujours le même
Équivalent à largeur d’abord !
Coût uniforme (UCS)
26
80
99
177310
278
27
Coût uniforme
Complète : oui, si le coût > e Complexité en temps :
nombre de nœuds avec g(n) ≤ coût(solution optimale)
O(b1+ C*/ ϵ)où C* est le coût de la solution optimale.
Complexité en espace : même que celle en temps Optimal : oui
Les nœuds sont développés en ordre de g(n).
28
Profondeur d’abord (DFS)
Développe le nœud le plus profond.
Implémenté à l’aide d’un pile. Les nouveaux nœuds générés vont sur le
dessus.
29
A
B C
D E
H I J K
D
Exemple profondeur d’abord
A
B C
D E
B
C
Pile:
H I J K
H
E
I
K
J
Ordre de visite: A – B – D – H – I – E – J – K - C
30
Propriétés de profondeur d’abord
Complétude : Non si la profondeur est infinie, s’il y a des cycles. Oui, si on évite les états répétés ou si l’espace de
recherche est fini. Complexité en temps : O(bm)
Très mauvais si m est plus grand que d. Mais si les solutions sont denses, il peut être
beaucoup plus rapide que largeur d’abord. Complexité en espace : O(bm), linéaire Optimal : Non
31
Profondeur limitée (DLS)
L’algorithme de profondeur d’abord, mais avec une limite de l sur la profondeur. Les nœuds de profondeur l n’ont pas de successeurs.
Complétude : Seulement si l > d Complexité en temps : O(bl) Complexité en espace : O(bl), linéaire Optimal : Non!
32
A
B C
D E
H I J K
D
Exemple profondeur limité
A
B C
D E
B
C
Pile:
E
Ordre de visite: A – B – D – E - C
Limite l = 2
33
Itérative en profondeur (IDS)
Profondeur limitée, mais en essayant toutes les profondeurs: 0, 1, 2, 3, …
Évite le problème de trouver une limite pour la recherche profondeur limitée.
A les avantages de largeur d’abord (complète et optimale), Mais a la complexité en espace de profondeur
d’abord. Donc une combinaison des deux stratégies.
34
Exemple - itérative en profondeur
Ordre de visite: A – A – B – C – A – B – D – E – C – F – G – A – B – D – H – I – E – J – K – C – F – L – M – G – N – O
A
B
D E
H I J K
C
F G
L M N O
1
10
2
34
5
6
7 8
9
12
13
1114 17
15 16 18 19 22 23 25 26
20
21 24
Limite: 0Limite: 1Limite: 2Limite: 3
35
Propriétés itérative en profondeur
Complétude: Oui Complexité en temps:
(d+1)b0 + db1+ (d-1)b2 + bd = O(bd) Complexité en espace: O(bd) Optimal?
Oui, si le coût de chaque action est de 1. Peut être modifiée pour une stratégie de coût
uniforme.
Stratégie de recherche non-informées : Sommaire
36
Dans ce tableau:
(1) b est le facteur de branchement;
(2) d est la profondeur du but le - profond;
(3) m est la profondeur max;
(4) l est la profondeur limite
37
Répétition d’états
La répétition d’états fait perdre du temps Dans le pire cas, la recherche tourne en rond dans
les cycles créés. Détection de répétitions
Normalement faite en comparant les nouveaux nœuds aux nœuds déjà développés.
Avant d’éliminer le nouveau nœud On doit vérifier s’il est meilleur que le nœud que l’on a
déjà.
38
Répétition d’états :
Exploration de type Graph-Search
Exploration de type Graph-Search
39
40
Stratégies d’exploration informées
Stratégies d’exploration non informées Ne sont pas très efficaces dans la plupart des
cas. Elles ne savent pas si elles approchent du but.
Stratégies d’exploration informées Elles utilisent une fonction d’estimation
Fonction heuristique. Pour choisir les nœuds à visiter.
41
Stratégies d’exploration informée
Meilleur d’abord (BFS - Best-first) Meilleur d’abord gloutonne (Greedy best-first) A* (A-Star) Algorithmes heuristiques à mémoire limitée
IDA*, RDFS et SMA* Par escalade (Hill-climbing) Par recuit simulé (Simulated annealing) Exploration locale en faisceau (Local beam) Algorithmes génétiques
42
Exemple d’exploration:
Voyage en Roumanie (avec coûts en km)
43
Meilleur d’abord L’idée principale
Utiliser une fonction d’évaluation Estimer l’intérêt des nœuds Développer le nœud le plus intéressant.
Le nœud à développer est choisi selon une fonction d’évaluation f(n)
Une composante importante de ce type d’algorithme est une fonction heuristique h(n) Elle estime le coût du chemin le plus court pour se
rendre au but. Deux types de recherche meilleur d’abord
Meilleur d’abord gloutonne. A*
A
B
but
g(B)
h(B)
.
.
.
f(B)= g(B) + h(B)
44
Meilleur d’abord gloutonne
f(n) = h(n)
Donc on choisit toujours de développer le
nœud le plus proche du but.
45
Exemple meilleur d’abord gloutonne
Arad366
Sibiu Timisoara Zerind253 329 374
Arad Fagaras Oradea Rimnicu Vilcea366 176 380 193
Sibiu Bucharest253 0
But atteint, l’exploration arrête.
46
Propriétés - Meilleur d’abord gloutonne
Complétude : Non Car elle peut être prise dans des cycles. Mais oui, si l’espace de recherche est fini avec vérification des
états répétés. Complexité en temps : O(bm)
Mais une bonne fonction heuristique peut améliorer grandement la situation.
Complexité d’espace : O(bm) Elle retient tous les nœuds en mémoire.
Optimale : Non Elle s’arrête à la première solution trouvée.
47
A* (A-star)
Fonction d’évaluation: f(n) = g(n) + h(n) g(n) : coût du nœud de départ jusqu’au nœud n h(n) : coût estimé du nœud n jusqu’au but f(n) : coût total estimé du chemin passant par n pour se rendre
au but. A* utilise une heuristique admissible
c’est-à-dire h(n) ≤ h*(n) h*(n) est le véritable coût pour se rendre de n au but.
Demande aussi que : h(n) ≥ 0, et que h(G) = 0 pour tous les buts G.
48
Exemple A*Arad366 = 0 + 366
Sibiu Timisoara Zerind393 = 140 + 253 447 = 118 + 329
449 = 75 + 374
Arad Fagaras Oradea Rimnicu Vilcea
646 = 280+ 366
415 = 239 + 176
671 = 291 + 380
413 = 220 + 193
Sibiu Bucharest
591 = 338 + 253 450 = 450 + 0
Craiova Pitesti Sibiu
553 = 300 + 253
417 = 317 + 100
526 = 366 + 160
CraiovaBucharest Rimnicu Vilcea
607 = 414 + 193615 = 455 + 160418 = 418 + 0
But atteint, la recherche arrête.
49
Propriétés de A*
Complétude : Oui À moins qu’il y est une infinité de nœuds avec f ≤ f(but).
Complexité de temps : Exponentielle Selon la longueur de la solution.
Complexité en espace : Exponentielle Selon la longueur de la solution. Elle garde tous les nœuds en mémoire.
Optimale : Oui Habituellement, on manque d’espace longtemps avant de
manquer de temps.
50
Exploration heuristique à mémoire limitée
A* est parfois trop gourmand en mémoire. Il existe des algorithmes pour surmonter ce
problème dont: IDA*; RBFS; SMA*.
Ces algorithmes permettent de préserver l’optimalité et la complétude.
L’augmentation du temps d’exécution est raisonnable.
51
Exploration heuristique à mémoire limitée
IDA* (Iterative-deepening A*)C’est un algorithme de profondeur itérative Utilise la valeur f(n) comme limite
Contrairement à la profondeur pour IDS. À chaque itération :
On fixe la limite à la plus petite valeur f(n) de tous les nœuds qui avaient une valeur plus grande que la limite au tour précédent.
52
Exemple IDA*Arad366 = 0 + 366
Sibiu Timisoara Zerind393 = 140 + 253 447 = 118 + 329
449 = 75 + 374
Limite: 366
53
Exemple IDA*Arad366 = 0 + 366
Sibiu Timisoara Zerind393 = 140 + 253 447 = 118 + 329
449 = 75 + 374
Arad Fagaras Oradea Rimnicu Vilcea
646 = 280+ 366
415 = 239 + 176
671 = 291 + 380
413 = 220 + 193
Limite: 393
54
Exemple IDA*Arad366 = 0 + 366
Sibiu Timisoara Zerind393 = 140 + 253 447 = 118 + 329
449 = 75 + 374
Arad Fagaras Oradea Rimnicu Vilcea
646 = 280+ 366
415 = 239 + 176
671 = 291 + 380
413 = 220 + 193
Craiova Pitesti Sibiu
553 = 300 + 253
417 = 317 + 100
526 = 366 + 160
Limite: 413
55
Exemple IDA*Arad366 = 0 + 366
Sibiu Timisoara Zerind393 = 140 + 253 447 = 118 + 329
449 = 75 + 374
Arad Fagaras Oradea Rimnicu Vilcea
646 = 280+ 366
415 = 239 + 176
671 = 291 + 380
413 = 220 + 193
Sibiu Bucharest
591 = 338 + 253 450 = 450 + 0
Craiova Pitesti Sibiu
553 = 300 + 253
417 = 317 + 100
526 = 366 + 160
Limite: 415
56
Exemple IDA*Arad366 = 0 + 366
Sibiu Timisoara Zerind393 = 140 + 253 447 = 118 + 329
449 = 75 + 374
Arad Fagaras Oradea Rimnicu Vilcea
646 = 280+ 366
415 = 239 + 176
671 = 291 + 380
413 = 220 + 193
Sibiu Bucharest
591 = 338 + 253 450 = 450 + 0
Craiova Pitesti Sibiu
553 = 300 + 253
417 = 317 + 100
526 = 366 + 160
CraiovaBucharest Rimnicu Vilcea
607 = 414 + 193615 = 455 + 160418 = 418 + 0
Limite: 417
57
Exemple IDA*Arad366 = 0 + 366
Sibiu Timisoara Zerind393 = 140 + 253 447 = 118 + 329
449 = 75 + 374
Arad Fagaras Oradea Rimnicu Vilcea
646 = 280+ 366
415 = 239 + 176
671 = 291 + 380
413 = 220 + 193
Sibiu Bucharest
591 = 338 + 253 450 = 450 + 0
Craiova Pitesti Sibiu
553 = 300 + 253
417 = 317 + 100
526 = 366 + 160
CraiovaBucharest Rimnicu Vilcea
607 = 414 + 193615 = 455 + 160418 = 418 + 0
But atteint, la recherche arrête.
Limite: 418
Plan
Agent de résolution de problèmes
Stratégies de recherche
Recherche non-informée
Largeur d’abord, profondeur d’abord, etc.
Recherche informée
Meilleur d’abord, A*, etc.
Prochain cours
Espaces de configuration
Discrétisation d’espaces
Quelques exemples d’exploration pour le projet
58