Explorer un espace d’étatsEtapes à suivre:

1. Bien définir les caractéristiques utiles de l’espace à explorer.

2. Définir l’état initial et l’état final (le but de l’exploration).

3. Définir un algorithme d’exploration (les opérateurs qui changent les états).

4. Si plusieurs algos, définir l’algo optimal selon un critère donné.

5. Coder les états de l’espace réel

6. Transformer l’algorithme en un programme (Lisp, C etc)

Sortir d’un labyrinthe

Le problème:

Un robot placé n’importe où dans un labyrinthe inconnu doit trouver par moyens propres la sortie.

Il doit marquer la voie correcte qui mène à la sortie ainsi que les essais infructueux qu’il a effectués sur le parcours.

S’il existe plusieurs chemins qui mènent à la sortie il doit choisir le chemin optimal selon un critère imposé.

Le programme LISP doit tenir compte de toutes ces exigences

Le labyrinthe réel

Sortie

Entrée

Algorithmes d’exploration

Il y a quatre directions à explorer: Droite, Bas, Gauche, Haut.On peut les combiner de différentes façons (combien ?)

On choisit une combinaison et on l’applique à chaque pas pour trouver la case libre suivante.

Si cul-de-sac, le robot doit retourner jusqu’à la dernière croisée pour essayer une autre direction.

Si la sortie est trouvée le robot retourne au point de départ en marquant le « bon » chemin.

Des explorations différentes mènent à des chemins différents.Il faut compter les pas pour mettre en évidence « le plus court chemin » après exploration de toutes les combinaisons.

Coder les états du labyrinthe

(transformer le labyrinthe en un tableau de symboles)

Chemin libre…………………………….tirets (-)

Murs……………………………………...dollars ($)

La sortie………………………………....l’atome « FIN »

Les voies explorées…….....................étoile (*)

Chemin correct entrée et FIN…………ronds (O)

Le labyrinthe codé (une liste de listes) j1 j2 colonnes

(- - - $ $ - - - - -) i1

($ $ - - - - $ - $ -) i2

(- - - - $ $ - - $ -) (- $ $ - - $ $ $ $ $) avant l’exploration

(- - - $ $ $ - - - -) (- $ - - - - - $ $ fin) lignes

(o o o $ $ * * * * *)

($ $ o o * * $ * $ *) après l’exploration

(o o o o $ $ * * $ *)

(o $ $ * * $ $ $ $ $)

(o o o $ $ $ o o o o)

(- $ o o o o o $ $ fin)

Préparation du programme LISP

On affecte à l’atome labyrinthe la valeur du tableau précédent:

(setq labyrinthe ‘( (…………………………..) (…………………………..) (…………………………..) (…………………………..) (…………………………..) (…………………………..) ) )

On crée une fonction laby qui a comme arguments le labyrinthe donné, les coordonnées d’une case (ligne i, colonne j) et qui implémente l’algo donné.

Appel de la fonction:(laby labyrinthe 0 0) (si l’on part de la ligne 0 et la colonne 0)(laby labyrinthe 3 4) (si l’on part de la ligne 4 et la colonne 5)

Fonctions auxiliaires – printab

printabTransforme une liste de listes en un tableau

Exemple:

? (printab ‘((a b c) (d e f) (g h i))) (a b c) (d e f) (g h i)

Définition:

( de printab ( liste) (until (null liste) (print (car liste)) (setq liste (cdr liste))))

La fonction tref

trefRetourne le terme de la ligne i et de la colonne j d’un tableau

Exemple:? (setq tab ‘((a b c) (d e f) (g h i)))? (tref tab 2 0) ;le terme de la ligne 2 et de la colonne 0=g

Définition:(de tref (tab i j ) (setq ligne (nth i tab)) ;affecte à l’atome ligne la ligne ‘i’ du tableau tab (nth j ligne)) ;retourne l’élément ‘j’ de la ligne respective

Le prédéfini (nth <n> <l>) retourne le <n> ième élément d’une liste <l>:? (nth 2 ‘(g h i))=i

? (nth 1 ‘((a b c) (d e f) (g h i)))= (d e f)

La fonction tset

tsetRemplace dans un tableau le terme < i > < j > par un autre

Exemple:? (tset ‘( (a b c) (d e f) (g h i) ) 1 1 ‘x ) = ((a b c) (d x f) (g h i))

Définition:( de tset (tab i j x) (setq nl (replace (nth i tab) j x)) ;nth retourne la ième ligne de tab

(replace tab i nl)) ;replace remplace le jème terme par x

;setq affecte à nl cette nouvelle ligne

;replace remet dans tab cette nouvelle ligne

(replace <l> <n> <x>) ;remplace dans la liste l le terme de rang n par x? (replace ‘(a b c) 2 ‘x) = (a b x)

La fonction <replace>

Définition:(de replace (liste i x) (cond ((= i 0) (rplaca liste x)) ( t (cons (car liste) ( replace (cdr liste) (1- i) x ) ) ) ) )

Le prédefini (rplaca <liste> <x>) remplace le premier terme de la liste par x

Exemples:(rplaca ‘(a b c) ‘x) ( x b c )

(replace ‘(a b c) 2 ‘x) (a b x)

(tset ‘((a b c) (d e f) (g h i)) 1 1 ‘x) ((a b c) (d x f) (g h i))

Programme LISP(de laby (labyrinthe i j) (setq pas-trouve T) // initialisation du drapeau pas-trouvé à VRAI (cherche-sortie i j ) // fonction d’exploration à partir de la case i j (if pas-trouve (print "pas de sortie") (print "solution: " ) (printab labyrinthe) ) )

(de cherche-sortie (i j) 1 (if (equal (tref labyrinthe i j) 'fin ) 2 (setq pas-trouve ( ) )3 (tset labyrinthe i j ‘*) 4 (if (and pas-trouve (member (tref labyrinthe i (1+ j)) '(- fin))) (cherche-sortie i (1+ j))) 5 (if (and pas-trouve (member (tref labyrinthe (1+ i) j) '(- fin))) (cherche-sortie (1+ i) j)) 6 (if (and pas-trouve (member (tref labyrinthe i (1- j)) '(- fin))) (cherche-sortie i (1- j)))7 (if (and pas-trouve (member (tref labyrinthe (1- i) j) '(- fin))) (cherche-sortie (1- i) j)))8 (ifn pas-trouve (tset labyrinthe i j ‘o)))

Explication de la fonction «cherche-sortie »

1. Si la case < i j > est égale à fin (test du IF)2. On affecte à l’atome « pas-trouvé » ( la valeur ( ) (si oui) si non on évalue la suite des fonctions (de 3 à 8) à commencer par:3. On remplace le (-) par (*) (marquage du chemin )On choisit l’algorithme d’exploration: droite – bas – gauche – haut Exploration à droite:4. Test du IF (2 conditions reliées par AND): SI pas-trouve est VRAI (True) et si la case à droite est libre ou fin ALORS relancer <cherche-sortie> à droite SINON (mur à droite) explorer la case du Bas

5. Exploration en bas: <(1+ i), j >…..si elle échoue (mur en bas):6. Exploration à gauche < i, (1- j) > …si elle échoue (mur à gauche):7. Exploration en haut <(1+ i), j > (mur en haut)

Si 4,5,6,7 échouent cul-de-sac (toutes les directions bouchées) alors on passe à 8.

Suite

8. pas-trouve = T donc le test de IFN échoue

On remonte dans la pile en dépilant les appels récursifs précédents en attente(on remonte le chemin parcouru) en testant les choix restants toujours dans l’ordre droite-bas-gauche-haut..

-Quand le test (tref labyrinthe i j) = FIN test (1) VRAI on pose: (setq pas-trouve ( ) ) le si oui de (2) et l’on remonte dans la pile pour évaluer les fonctions en attente. Toutes échouent à cause du test « pas-trouve = ( ) »

-Seul le test du IFN (8) réussit et le « tset » marque le chemin correct (remplace les * par des o)

Exercices/Mini-projet

Exercices

1. Changez le type de labyrinthe (nombre de cases et/ou position des murs) et vérifiez que le programme fonctionne toujours correctement.

2. Modifiez le programme afin que l’atome FIN de la case sortie soit remplacé par un o (marquage habituel)

3. Insérez dans le programme donné un compteur qui permette d’afficher: - le nombre de pas corrects (le nombre de ronds ‘o’) - le nombre de pas ratés (le nombre d’étoiles ‘*’ ) Changez l’algorithme d’exploration du labyrinthe initial et vérifiez que le

nombre de pas (utiles et ratés) peut changer.

Mini-projet

Sachant qu’il y a 24 algorithmes d’exploration possibles (expliquez pourquoi) écrivez le programme qui permet de mettre en œuvre automatiquement ces algos, de calculer chaque fois le nombre de pas corrects et ratés et de mettre en évidence le ou les algos optimaux selon un critère d’optimalité choisi (par exemple nombre minimal de pas corrects ou bien nombre minimal de pas ratés ou bien nombre minimal de pas totaux).

Note: les étudiants qui rendent le mini-projet au plus tard le 4.01.05 (et le soutiennent correctement) seront exemptés du contrôle de IA du 23.03.