Page web Vincent THOMAS


Atelier ISN - 22/03/2018
"Labyrinthe et recherche de chemins"

Sommaire


L'ensemble des fichiers de cette page seront sont disponibles en version compressée à partir de ce lien

Description de l'atelier

Les labyrinthes sont intéressants à étudier car ils constituent des cas typiques de problème de prise de décision dans lesquel un agent intelligent doit savoir raisonner sur le long terme: en effet, pour décider quel couloir emprunter, il faut déjà savoir ce qu'il sera possible de faire au bout des différents couloirs.

Au cours de cet atelier,

  • on regardera comment modéliser un labyrinthe avec un tableau à deux dimension;
  • on programmera ensemble (en python) l'algorithme de Lee, un algorithme très simple permettant de construire le chemin le plus court dans un labyrinthe.
  • on présentera dans un second temps, les principes de l'algorithme classique A* qui permet d'améliorer grandement la recherche en utilisant une connaissance du problème.
  • Enfin, on étendra les problèmes abordés pour montrer comment réutiliser ces algorithmes pour construire des agents intelligents capables de prendre des décisions sur le long terme dans des contextes divers (par exemple dans le cadre de projet étudiant).

Outils à installer

Dans cet atelier, le langage utilisé sera python 3.

Pour pouvoir aborder cet atelier, si vous souhaitez utiliser votre machine, on vous propose d'installer la distribution

EduPython (disponible à l'adresse http://edupython.tuxfamily.org/)

Si vous avez des idées de problèmes de décision ou de contrôle qui vous intéressent, nous pourrons en discuter ou les résoudre lors de l'atelier (vous pouvez aussi m'envoyer un mail au préalable - vincent.thomas@loria.fr)

Documents 2018

L'atelier 2018 s'est structuré autour des documents suivants

Contenu de l'atelier

1. Labyrinthe

Un Labyrinthe est simplement décrit par un tableau d'entiers à deux dimensions:
  • 1 signifie que la case comporte un mur
  • 0 sinifie que la case est accessible 
  def getLabyrinthe1():
      """
      construit et retourne un labyrinthe par defaut a parcourir
      (de taille 8x8)
      """

      # labyrinthe vide
      laby = []
      laby +=[[1,1,1,1,1,1,1,1]]
      laby +=[[1,0,0,1,0,0,0,1]]
      laby +=[[1,0,0,1,0,0,0,1]]
      laby +=[[1,0,1,1,1,1,0,1]]
      laby +=[[1,0,0,0,0,0,0,1]]
      laby +=[[1,0,1,1,0,1,0,1]]
      laby +=[[1,0,0,0,0,0,0,1]]
      laby +=[[1,1,1,1,1,1,1,1]]

      # nouveau laby
      return transpose(laby)

2. Algorithme de Lee

L'algorithme de Lee (aussi appelé algorithme de propagation ou de la vague - même si je ne suis pas sûr que ce soit le bon terme) consiste simplement à propager les valeurs de proche en proche dans le labyrinthe:
  • à t=0, seule le point de départ à une valeur nulle
  • au pas de temps t, on cherche les cases avec une valeur t et on met la valeur t+1 sur les cases voisines
    • si elles ne sont pas des murs
    • si elles ne sont pas déjaà marquées
  • il faut ensuite remonter les valeurs pour trouver le chemin
Cet algorithme repose sur le fait que toutes les cases ont un coût de 1. Il est possible de l'implémenter plus ou moins rapidement
  • soit, à chaque pas de temps, on reparcoure tout le tableau pour trouver les cases marquées avec le bon indice (gourmand en calcul)
  • soit on stocke dans une liste les cases modifiées à regarder au pas de temps suivant (plus rapide)

3. Algorithme de Dijkstra

L'algorithme de Dijkstra repose sur le même principe mais :
  • les cases ont des couts variables
  • on propage la case de distance minimale par rapport au départ

Pour des couts constants de 1, l'algorithme de dijkstra correspond à l'lagorithme de Lee. Dans le code fourni, l'algorithme choisit de développer le noeud de cout le plus faible (même si dans les faits cela revient à Lee)

4. Algorithme A*

L'algorithme A* repose sur une connaissance introduite par l'humain pour guider correctement la recherche. Cette connaissance est appelée heuristique (du grec "je trouve").

Dans le cadre du labyrinthe, cette heuristique consiste à préciser que le chemin restant est forcément plus petit que la distance de manhattan entre le point courant et le point d'arrivée.

L'algorithme A* consiste à chaque pas de temps à développer le noeud qui semble le plus prometteur si tout se passe bien (autrement dit celui pour lequel la distance + heuristique est la plus faible). En raisonnant de manière optimiste, l'algorithme A* se concentre sur ce qui semble le mieux (qui doit de toute façons être testé si on souhaite trouver le plus court chemin) et remettra en cause le chemin suivi lorsqu'un obstacle sera présent.

Références



Icons designed by {Freepik} from Flaticon.
    last mod. 15/01/2016 Copyright - Vincent Thomas - vthomas@loria.fr