[PDF] [PDF] INF4230 – Intelligence Artificielle Algorithme A* - GDAC

View - Download [PDF] INF4230 – Intelligence Artificielle Algorithme A* - GDAC

Previous PDF

Next PDF

INF4230 - Intelligence Artificielle

Recherche heuristique /

Algorithme A*

Hiver 2017

Sommaire

Rappels :

Agents.

Résolution de problème par recherche.

Espace d'Ġtats.

Recherche informée.

Recherche "meilleur en premier».

Algorithme A*.

Heuristiques.

Propriétés de A*.

INF4230 - Intelligence artificielle 2

Rappel : Agents rationnels

Agent :

Perçoit son environnement.

Agit dans son environnement

Se fait une représentation du monde (modèle).

Mesure de performance.

(Modèle PEAS).

Un agent a une fonction f: P* AE A .

INF4230 - Intelligence artificielle 3

Rappel : Environnements

Complètement observable vs partiellement

observable.

Déterministe vs stochastique.

Épisodique vs séquentiel.

Statique vs dynamique.

Discret vs continu.

Agent unique vs multi-agent.

Quasi synonymes : environnement et monde

(world).

INF4230 - Intelligence artificielle 4

Rappel : Paradigme de résolution de problème La fonction f d'un agent peut ġtre implĠmentĠe ă l'aide du paradigme ͨrĠsolution de problğmes par recherche». Construction d'un modğle du monde ă l'aide des données sensorielles provenant des capteurs. Un graphe est Ġtendu ă partir de l'Ġtat initial Les décisions séquentielles sont sélectionnées à l'aide d'une recherche dans un graphe.

INF4230 - Intelligence artificielle 5

Rappel : Types de problème

Déterministe + Complètement observable AE problème à

L'agent sait tout et peut simuler ses actions.

Non déterministe et/ou observabilité partielle AE problème de contingence. Solution = Plan contingent; Alternance recherche et exécution. Non observable AE problème sans capteurs ou problème de conformance (conformant planning). L'agent n'a aucune idĠe de son enǀironnement. Espace d'Ġtats inconnu AE problğme d'edžploration.

INF4230 - Intelligence artificielle 6

Rappel : Agent basé sur des buts

INF4230 - Intelligence artificielle 7

Exemple 1 - Agent sur une carte

v0 v3 v2 v1 v4 v6 v5 2 3 1 1 7 2 4 4 4

Monde:

Villes et routes.

Problème posé (état_initial, but):

v0: ville de départ (état initial) v6: destination (but)

INF4230 - Intelligence artificielle 8

Exemple 2 - Jeu de taquin (puzzle)

1 2 3 4 5 7 6 8 8 1 3 4 5 7 6 2 ? 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8

Nord Sud Ouest Nord Est

INF4230 - Intelligence artificielle 9

RECHERCHE INFORMÉE

INF4230 - Intelligence artificielle 10

Algorithme Meilleur en premier

(Best-First-Search)

La définition varie selon les auteurs :

Dans le livre de Norvig et Russell :

"Greedy Best-First-Searchͩ т ͨBest-First-Search» "Greedy Best-First-Search» (GBFS) est une recherche locale у hill climbing (chapitre 4). "Best-First-Search» est une recherche globale. Idée = choisir le prochain état qui "semble» le plus près du but (meilleur).

Ce choix est fait par une (fonction) heuristique.

INF4230 - Intelligence artificielle 11

Dans divers domaines, dont en informatique,

une heuristique est une méthode (~algorithme) qui calcule rapidement (ex: en temps constant, linéaire ou polynomiale) une solution pouvant être approximative et incomplète à un problème généralement trop complexe.

INF4230 - Intelligence artificielle 12

Algorithme de recherche en IA /

Fonction heuristique

Estimation de la distance (coût restant) entre un

état n et un but g.

Le but g peut être implicite.

Généralement notée h ou h(n).

h(n) : estime le coût restant pour atteindre le but

Exemple de fonctions heuristiques pour la

navigation dans sur une carte : Distance euclidienne (aussi appelĠe ă ǀol d'oiseau).

Distance de Manhattan (ville quadrillée).

INF4230 - Intelligence artificielle 13

Greedy Best-First-Search

Algorithme :

1.GBFS(n) :

2. tant que n ne satisfait pas le but

3. S Å Successeurs(n)

4. n' Å choisir n' dans S ayant le plus petit h(n')

5. si n' с n alors CHEC

6. n Å n'

INF4230 - Intelligence artificielle 14

Exemple de GBFS sur une carte

52e rue

51e rue

50e rue

10 th Ave

9e ave

8e ave

7e ave

6e ave

5e ave

4e ave

3e ave

2e ave

S G

53e rue

(Adaptée d'une illustration par Henry Kautz, U. of Washington)

INF4230 - Intelligence artificielle 15

Best-First-Search

Algorithme :

1.BFS(n0) :

2. open Å {n}

4. n Å choisir dans open qui minimise h(n)

5. si n satisfait le but, alors retourner solution

6. ajouter successeurs(n) dans open

INF4230 - Intelligence artificielle 16

Exemple de GBFS sur une carte

52e rue

51e rue

50e rue

10 th Ave

9e ave

8e ave

7e ave

6e ave

5e ave

4e ave

3e ave

2e ave

S G

53e rue

(Adaptée d'une illustration par Henry Kautz, U. of Washington)

INF4230 - Intelligence artificielle 17

Algorithme A*

A* est une edžtension de l'algorithme de Dijkstra. A* et les heuristiques sont à la base de beaucoup de travaux en IA:

Recherche de meilleures heuristiques.

Heuristiques indépendantes du problème.

Pour décrire A*, on décrit un algorithme

générique très simple, dont A* est un cas particulier.

INF4230 - Intelligence artificielle 18

Variables importantes : open et closed

open : présent dans le graphe. closed : c'est ă dire ă l'intĠrieur de la frontiğre dĠlimitĠe par open.

INF4230 - Intelligence artificielle 19

Une fonction f(n) donne ou estime la qualité de la meilleure par n, et arriǀant dans un Ġtat n' satisfaisant le but g.

INF4230 - Intelligence artificielle 20

Définition de la fonction f(n)

Par contre on connaît la distance optimale dans la partie explorée entre le Ainsi, on peut séparer f(n) en deux parties: f(n) = g(n) + h(n) la partie déjà explorée. satisfaisant le but. h(n) est une fonction heuristique.

INF4230 - Intelligence artificielle 21

Algorithme générique de recherche dans un graphe

Algorithme rechercheDansGraphe(n0)

1.open ÅCréer un ensemble ordonnées par f(n) // vide au départ

2.closed Å Créer un ensemble // vide au départ

3.insérer n0 dans open

4.while (true) // la condition de sortie (exit) est déterminée dans la boucle

5.si open

6.n1 = noeud au début de open avec le plus petit f(n)

7.enlever n1 de open closed

8.si n1 est le but, sortir de la boucle avec succès en retournant le chemin;

9.pour chaque noeud successeur n2 de n1

10.Initialiser la valeur g(n2) = g(n1) + coût de la transition (n1,n2)

11.mettre parent(n2) = n1

12.si open ou closed*

f(n2)13.sinon (c-à-dopen ni dans closed)

14.insèrer n2 dans open

INF4230 - Intelligence artificielle 22

Exemple A* avec recherche dans une ville

v0 v3 v2 v1 v4 v6 v5 9 2 3 2 2 5 0 2 3 1 1 7 2 4 4 4 h(v0) c(v0,v1)

Routes entre les villes :

v0: ville de départ v6: destination h: distance à vol C: distance réelle entre deux ville 1. (v0, 9, void)

Contenu de closed à la sortie

(noeud, f) : (v4,6), (v3,7), (v2,5), (v1,5), (v0,9)

Contenu de open à chaque

itération (état, f, parent) :

2. (v1,5,v0) (v2,6,v0), (v3,7,v0)

3. (v2,6,v0) (v3,7,v0), (v5,12,v1)

4. (v3,7,v0),(v4,9,v2),(v5,12,v1)

5. (v2,5,v3),(v4,6,v3),(v5,12,v1)

6. (v4,6,v3),(v5,12,v1)

7. (v6,7,v4), (v5,12,v1)

8. Solution: v0,v3,v4,v6

INF4230 - Intelligence artificielle 23

Exemple de recherche avec A*

52e rue

51e rue

50e rue

10 th Ave

9e ave

8e ave

7e ave

6e ave

5e ave

4e ave

3e ave

2e ave

S G

53e rue

f=6+2 f=1+7 f=7+3 (Illustration par Henry Kautz, U. of Washington)

INF4230 - Intelligence artificielle 24

Non-optimalité de Best-First Search

52e rue

51e rue

50e rue

10 e ave

9e ave

8e ave

7e ave

6e ave

5e ave

4e ave

3e ave

2e ave

S G

53e rue

Solution par Best-first-Search

Solution optimale par A*

(Illustration par Henry Kautz, U. of Washington)

INF4230 - Intelligence artificielle 25

Démos

Simulation des algorithmes :

A*, Recherche en profondeur, largeur, meilleur en premier http://ericbeaudry.ca/INF4230/demos/search/ (Applet Java)

INF4230 - Intelligence artificielle 26

JEU DE TAQUIN

INF4230 - Intelligence artificielle 27

Jeu de taquin

État: configuration légale du jeu

État initial: configuration initiale

État final (but): configuration gagnante

Transitions (fonction successeur)

1 2 3 4 5 7 6 8 8 1 3 4 5 7 6 2 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 . . . Nord 1 2 3 4 5 7 6 8 Est Ouest Sud

INF4230 - Intelligence artificielle 28

Heuristiques pour jeu de taquin

quotesdbs_dbs44.pdfusesText_44

[PDF] généralités sur les systèmes automatisés de production

[PDF] structure fonctionnelle d'un système automatisé

[PDF] méthodes heuristiques d'optimisation

[PDF] définition d'un système automatisé de production

[PDF] méthodes heuristiques et métaheuristique d'optimisation

[PDF] méthode heuristique optimisation

[PDF] système automatisé de production sap

[PDF] les métaheuristiques en optimisation combinatoire

[PDF] système automatisé de production pdf

[PDF] système automatisé de production ppt

[PDF] cours aide soignante module 1 pdf

[PDF] qcm module 1 aide soignante gratuit

[PDF] cours aide soignante module 2

[PDF] module 1 aide soignante résumé

[PDF] les 8 modules aide soignante