1

Intelligence Artificielle

ACADEMIE NAVALE DE MANZEL BOURGUIBA

Version Janvier 2008

Dr. Inès BENJAAFAR mailto:ines.benjaafar@gmail.com

Ou mailto:ines.benjaafar@isg.rnu.tn

2

Recherche Heuristique dans les Graphes d’Etats

Chapitre 5

3

Plan du chapitre VV.1 Introduction

V.2 Stratégies de recherche aveugle

Recherche en profondeur

Recherche en largeur

V.3 Stratégies de recherche heuristique

Recherche en profondeur Ordonnée

Recherche du meilleur Premier

…

Recherche Heuristique A*

4

V.1 Introduction!

Les Algorithmes de recherche constituent l’une des approches les plus puissantes pour la résolution en IA

Les algorithmes de recherche sont un mécanisme générl de résolution de problèmes qui :

Se déroule dans un espace appelé espace d’états Explore systématiquement toutes les alternatives Trouve la séquence d’étapes menant à la solution

5

V.1 Introduction!

Les différentes méthodes de recherche sont évaluées selon les critères suivants :

Complétude : est ce que la méthode garantit de trouver une solution si elle existe? Optimalité : est ce que la méthode trouve la meilleure solution s’il en existe plusieurs? Complexité en temps : Combien de nœuds faut-il produire pour trouver la solution? Complexité en espace : nombre maximum de nœuds à conserver en mémoire pour trouver la solution?

6

V.1 Introduction!

Les méthodes de recherche différent les unes des autres selon l’ordre dans lequel les nœuds sont étendus, On distingue :

Les Stratégies Aveugles, qui n’exploitent aucune information contenue dans un nœud donné

Les Stratégies Heuristiques qui exploitent certaines informations pour déterminer si un nœud est plus prometteur qu’un autre

7

V.1 Introduction!

Exemple : Problème de recherche de chemin

Il s’agit de trouver un chemin dans un réseau de villes reliées par des routes. Le chemin doit commencer à la ville source S et se terminer à la ville but G (voir figure)

La difficulté de la recherche d’un chemin se mesure à deux niveaux :

la découverte d’un chemin (le plus court ou quelconque) le parcours effectif de ce chemin

8

V.1 Introduction!

Exemple : Problème de recherche de chemin

Deux solutions sont possibles :Si le parcours entre S et G est fréquent alors il est préférable de trouver un chemin optimal

Si le parcours se fait une seule fois et si le réseau est complexe, on peut se satisfaire du premier chemin rencontré

Dans un premier temps, on considère la recherche d’un chemin quelconque, on présente ensuite la recherche de chemins optimaux!

9

V.2 Stratégies de recherche aveugles

Recherche en profondeur (depth first search)

Elle descend directement au fond de l’arbre de rechercheOn sélectionne à chaque nœud rencontré pour continuer la descente à partir de cette possibilité jusqu’à atteindre le but ou une feuilleDans le cas d’impasse (une feuille différente du but), on reprend la recherche à partir de l’ancêtre le plus proche dont au moins un fils n’a pas été exploréLes possibilités sont testées de gauche à droiteLa première action dans le parcours de l’arbre est de poursuivre les branches les plus à gauche

10

V.2 Stratégies de recherche aveugles

Procedure de Recherche en profondeur

1.Empiler la racine2.Jusqu’à ce que la pile soit vide ou que le nœud but soit atteint, si le sommet de la pile est égal au nœud but :

2.1 Si oui ne rien faire à cette étape2.2 Sinon dépiler le premier élément et empiler ses

fils, s’il en a, depuis celui le plus à droite jusqu’à celui le plus à gauche

3. La recherche aboutit si le nœud but a été atteint et échoue sinon

11

V.2 Stratégies de recherche aveugles

Remarques

1.L’algorithme peut dans un cas défavorable, nous obliger à parcourir l’intégralité de l’espace d’état avant de trouver la polution (au pire des cas)

2.Un inconvénient de la recherche en profondeur : au lieu de correspondre à une impasse directe, on explore plusieurs niveaux de l’arbre avant de rencontrer le cas d’impasse

12

V.2 Stratégies de recherche aveugles

Recherche en Largeur

Elle descend uniformément dans l’arbre de rechercheLa recherche en largeur cherche le but souhaité parmi tous les nœuds d’un niveau donné avant de consulter leurs filsOn ne peut pas développer un nœud de niveau n si on n’a pas développer tous les nœuds de niveau n-1

L’arbre de recherche en largeur correspondant à l’exemple 1 est donné par la figre suivante :

13

V.2 Stratégies de recherche aveugles

Procedure de Recherche en Largeur

1.Mettre la racine en tête de la file2.Jusqu’à ce que la file soit vide ou que le nœud but soit atteint, si le premier élément de la file est égal au nœud but :

2.1 Si oui ne rien faire à cette étape2.2 Sinon le retirer de la file et placer ses fils, s’il en a,

depuis celui le plus à droite jusqu’à celui le plus à gauche

3. La recherche aboutit si le nœud but a été atteint et échoue sinon

14

V.2 Stratégies de recherche aveugles

Remarques

1.La procédure recherche en largeur ressemble à celle de la recherche en profondeur, la seule différence réside dans l’endroit d’insertion de nouveaux éléments. Ceci se traduit pr le fait qu’on utilise une file plutôt qu’une pile

2. Lorsque la recherche en profondeur s’avère inéfficace, une recherche en largeur peut donner des résultats plus surs

3.Ce type de recherche est très couteux lorsque tous les chemins mènent au but, à des profondeurs pratiquement identiques

15

V.3 Stratégies de recherche Heuristiques

Les algorithmes de recherche aveugle n’exploitent aucune information concernant la structure de l’arbre de recherche ou la présence potentielle de nœuds-solution pour optimiser la recherche

La majorité des problèmes réels sont susceptibles de provoquer une explosion combinatoire du nombre d’états possibles

Un algorithme de recherche heuristique qui utilise l’information disponible pour rendre le processus de recherche plus efficace s’avère une nécessité

Une information heuristique est une règle ou une méthode qui presque tjrs améliore le processus d la recherche

16

V.3 Stratégies de recherche Heuristiques

Recherche en profondeur Ordonnée (Hill climbing)

On peut améliorer l’efficacité d’une recherche si l’on dispose d’un moyen d’examiner en premier les choix les plus prometteur

On procède comme pour la recherche en profondeur, mais on ordonne les choix selon une mesure heuristique de la distance restante à parcourir depuis un nœud

Plus la mesure heuristique est fine, plus l’efficacité de l’algorithme est supérieure à la simple recherche en profondeur

Un exemple de mesure heuristique de la distance restante à parcourir est la distance euclidiènne (distance à vol d’oiseau)

17

V.3 Stratégies de recherche Heuristiques

Procedure de Recherche en Profondeur Ordonnée

1.Empiler la racine2.Jusqu’à ce que la pile soit vide ou que le nœud but soit atteint, si le sommet de la pile est égal au nœud but :

2.1 Si oui ne rien faire à cette étape2.2 Sinon dépiler le premier élément et empiler ses

fils, s’il en a, dans l’ordre décroissant de leur distance au but

3. La recherche aboutit si le nœud but a été atteint et échoue sinon

18

V.3 Stratégies de recherche Heuristiques

Remarque :

1.Cette procédure peut mener à une solution qui présente un optimum local et non pas global. La solution sera diférente de la solution globale au problème

19

V.3 Stratégies de recherche Heuristiques

Recherche du meilleur premier (best first search)

Cette recherche est un compromis entre une recherche en largeur et une recherche en profondeur en utilisant une fonction heuristique pour guider la génération des noeuds

Le mecanisme de cette recherche est le suivant : on développe à chaque étape le meilleur noeud non encore développé, quelque soit l’endroit où il se situe dans l’arbre partiel developpé et on recommence le processus

La recherche du meilleur premier nécessite comme dans la recherche en profondeur ordonné un tri, mais cette fois toute la file devra être triée

20

V.3 Stratégies de recherche Heuristiques

Procedure du meilleur premier

1.Mettre la racine en tête de la file2.Jusqu’à ce que la file soit vide ou que le nœud but soit atteint, si le premier élément de la file est égal au nœud but :

2.1 Si oui ne rien faire à cette étape2.2 Sinon le retirer de la file et placer ses fils, s’il en a,

et trier la file entière par ordre croissant des distances calculées au but

3. La recherche aboutit si le nœud but a été atteint et échoue sinon

21

V.3 Stratégies de recherche Heuristiques

Remarque :

1.Les chemins trouvés par la procédure du meilleur premier sont souvent meilleurs que ceux trouvés par les autres méthodes, parce qu’on poursuit toujours la recherche à partir du nœud qui semble être le plus proche du but

22

V.3 Stratégies de recherche Heuristiques

Procedure du British Museum (énumération explicite) Une technique (la plus simple pour trouver le chemin le plus court consiste à rechercher tous les chemins possibles puis à conserver le chemin le plus courtBritish Museum : musée réputé par la complexité de ramification de ses galeries avant de trouver celle qqui l’interesse Pour trouver tous les chemins possibles on peut utiliserr ou bien la recherche en largeur ou bien la recherche en profondeur mais avec une legère modification :la recherche ne s’arrête pas dès qu’on trouve le premier chemin conduisant au butL’utilisation d’une telle procédure est acceptable tant que la largeur et la profondeur de l’arbre restent raisonnables

23

V.3 Stratégies de recherche Heuristiques

Branch and Bound (méthode de séparation et évaluation)

Ce type de recherche heuristique fournit une méthode moins couteuse pour trouver les chemins optimauxL’idée de base étant de développer le chemin partiel à moindre coûtAinsi, on développe le nœud situé à la fin du plus court chemin partiel ouvert à ce stadeSi on prend un exemple simple de carte routière figure suivante :….

24

V.3 Stratégies de recherche Heuristiques

Procedure Branch and Bound1.Initialement, la file des chemins partiels contient le chemin de longeur nulle contenant la racine2.Jusqu’à ce que la file soit vide ou que le nœud but soit atteint, si le premier chemin de la file atteint le but :

2.1 Si oui ne rien faire à cette étape2.2 Sinon

2.2.1 Le défiler2.2.2 Former les nouveaux chemins obtenus en prolongeant d’un niveau le chemin supprimé2.2.3 Enfiler ces nouveaux chemins2.2.4 Trier la file par cout de chemin croissant (distance totale du chemin parcuru)

3. La recherche aboutit si le nœud but a été atteint et échoue sinon

25

V.3 Stratégies de recherche Heuristiques

Branch and Bound et estimation minorante

l’efficacité du branch and bound peut être améliorée si o utilise en plus de la longeur du chemin déjà parcouru une estimation des distances restantes à parcourirSi on peut se fier à la distance restante à parcourir en lui ajoutant la distance connue du chemin déjà parcouru, on aura une bonne estimation de la longueur totale du chemin E(longueur totale du chemin) = distance déjà parcourue + E(distance restante)Ainsi on développe le chemin dont la longueur estimée est la plus courte jusqu’à ce qu’on trouve un autre chemin de longueur estimée plus courte

26

V.3 Stratégies de recherche Heuristiques

Branch and Bound et estimation minorante

Si les estimations sont parfaites, cette recherche trouve le chemin optimal, mais en général, les estimations ne sont pas parfaites et une mauvaise sur évaluation du véritable chemin optimal peut nous en faire dévierUne sous estimation ne peut pas risquer de faire manquer le chemin optimalUne sous estimation de la distance restante conduit à une sous estimation d la longueur totale du cheminSi dans ce type de recherche heuristique on garantit l’utilisation d’une heuristique minorante alors on est sur d’atteindre le chemin optimal

27

V.3 Stratégies de recherche Heuristiques

Procedure Branch and Bound avec heuristique minorante1.Initialement, la file des chemins partiels contient le chemin de longeur nulle contenant la racine2.Jusqu’à ce que la file soit vide ou que le nœud but soit atteint, si le premier chemin de la file atteint le but :

2.1 Si oui ne rien faire à cette étape2.2 Sinon

2.2.1 Le défiler2.2.2 Former les nouveaux chemins obtenus en prolongeant d’un niveau le chemin supprimé2.2.3 Enfiler ces nouveaux chemins2.2.4 Trier la file par coût de chemin croissant ( somme de distance déjà parcourue et d’une estimation minorante de la distance restante à parcourir)

3. La recherche aboutit si le nœud but a été atteint et échoue sinon

28

V.3 Stratégies de recherche Heuristiques

Remarques :

1.L’heuristique minorante garantit l’obtention de la solution optimale

2.L’approche est plus efficace d’autant mieux que les estimations minorantes sont plus proches des distances réelles, car dans ce cas il devient impossible de sortir du droit chemin

29

V.3 Stratégies de recherche Heuristiques

Recherche heuristique par programmation dynamique

Il existe une autre façon d’améliorer la recherche heuristique, Il s’agit de supprimer les chemins redondants

voir exemple..

30

V.3 Stratégies de recherche Heuristiques

Procedure recherche heuristique par programmation dynamique1.Initialement, la file des chemins partiels contient le chemin de longeur nulle contenant la racine2.Jusqu’à ce que la file soit vide ou que le nœud but soit atteint, si le premier chemin de la file atteint le but :

2.1 Si oui ne rien faire à cette étape2.2 Sinon

2.2.1 Le défiler2.2.2 Former les nouveaux chemins obtenus en prolongeant d’un niveau le chemin supprimé2.2.3 Enfiler ces nouveaux chemins2.2.4 Trier la file par coût de chemin croissant (distance totale du chemin parcouru )2.2.5 Si deux chemins ou plus atteignent le même nœud, ne conserver que celui ayant la longueur minimale

3. La recherche aboutit si le nœud but a été atteint et échoue sinon

31

V.3 Stratégies de recherche Heuristiques

Recherche heuristique A*

La recherche heuristique A* est une recherche heuristique avec estimation de la distance restante combinée avec le principe de la programmation dynamique

Cet algorithme apparait avec de nombreuses variantes dans la littérature, on l’expose dans ce chapitre sous une formulation simple

32

V.3 Stratégies de recherche Heuristiques

Procedure A*1.Initialement, la file des chemins partiels contient le chemin de longeur nulle contenant la racine2.Jusqu’à ce que la file soit vide ou que le nœud but soit atteint, si le premier chemin de la file atteint le but :

2.1 Si oui ne rien faire à cette étape2.2 Sinon

2.2.1 Le défiler2.2.2 Former les nouveaux chemins obtenus en prolongeant d’un niveau le chemin supprimé2.2.3 Enfiler ces nouveaux chemins2.2.4 Coût de chaque chemin (f) = distance déjà parcourue (g) + estimation minorante de la distance restante à parcourir (h)2.2.5 Trier la file par coûts (f) croissants2.2.6 Si deux chemins ou plus atteignent le même nœud, ne conserver que celui ayant la longueur minimale

3. La recherche aboutit si le nœud but a été atteint et échoue sinon

33

H. Farreny et M. Ghallab, Eléments d’Intelligence Artificielle, Edition HERMES, 1987 J.-G. Ganascia, L’intelligence Artificielle, Coll. DOMINOS, Flammarion, 1993J.-G. Ganascia, L’âme machine, Seuil, 1990 M. Ginsberg, Essentials of Artificial Intelligence, Morgan Kaufmann, 1997 J.-L. Laurière, Intelligence Artificielle : résolution de problèmes par l’homme et la machine, Eyrolles, 1987Russel and Norvig, Artificial Intelligence a Modern Approach, Prentice Hall Series in Artificial Intelligence, 1995

Bibliographie!