Page web Vincent THOMAS


Atelier ISN - 07/03/2019
"Labyrinthe et recherche de chemins"

Sommaire


L'ensemble des fichiers de cette page 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 2019

L'atelier 2019 s'est structuré autour des documents suivants Les labyrinthes exemples sont disponibles ici :

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)
Il est possible d'accéder à un labyrinthe avec la méthode getLabyrinthe en passant en parametre le nom du labyrinthe :
  • 'default'
  • 'moyen'
  • 'grand'
  • 'tresgrand'
Il est aussi possible d'accéder au labyrinthe via le main 
python3 00_labyDonne.py grand

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 (ici différence altitude + 1)
  • on propage la case de distance minimale par rapport au départ

Les slides associés à l'algorithme Dijkstra sont disponibles ici:


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.

5. Extension à d'autres problèmes

Il est possible d'étendre l'algorithme de Lee ou Dijkstra à d'autres problèmes. Cela consiste à raisonner sur une structure de graphe remplaçant le labyrinthe.

  • les noeuds du graphe correspondent aux situations possibles
  • les arcs aux actions permettant de changer de situation (passer d'un noeud à un autre)

La difficulté repose dans l'écriture des classes décrivant les régles du problème (ou autrement dit le calcul de l'état atteint à partir d'un état en effectuant une certaine action). On propose de représenter les problèmes avec

  • la liste des actions possibles dans la méthode actions()
  • et les conséquences de chaque action avec la méthode transition(s,a) qui retourne l'état atteignable quand on fait l'action a dans l'état s.

Des modélisations de problème sont proposées dans les classes suivantes:

L'algorithme reste quasiment inchangé : au lieu de considérer les cases voisines pour propager les valeurs, il suffit de considérer les actions possibles et les cases atteignables à partir de ces actions.

Pour faciliter la construction du chemin, il est aussi possible de stocker en plus de la distance associée à chaque noeud, l'action et le noeud qui permettent d'y parvenir (cela évite de devoir calculer les antécédants sur l'ensemble du graphe)

Le code suivant permet de charger un problème et de le résoudre de manière générique

Il est possible de le tester avec les problèmes fournis 

  # probleme cafe
  python3 AlgoLee.py cafe

  # probleme sokoban simple
  python3 AlgoLee.py sokoban

  # probleme sokoban complexe
  # ATTENTION: l'affichage prend du temps (le supprimer dans AlgoLee si besoin)
  python3 AlgoLee.py sokoban_dur

Application JAVA

Une application JAVA a été développée en projet tutoré de DUT informatique (2017-2018) par

  • Valentin Berard
  • Luca Oberhausser
  • Johan Saltutti
  • Matthieu Sommer

L'application permet de créer des labyrinthes, d'experimenter Dijkstra et A*, d'éxecuter des comportements donnés à priori (algorithme de la main droite, pledge, ...) et de résoudre des problèmes simples de localisation pour un robot autonome.

Références



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