Recherche de chemins

Plan de la première séance

• Notion de système à bases de connaissances

  • mécanismes de raisonnements génériques

  • utilisant des connaissances spécifiques au domaine

• Illustration : recherche de chemin dans un graphe

  • raisonnement : algorithme de Dijkstra, A*

  • connaissances : modélisation du problème sous forme de graphe

  • différentes fonctions de coût possibles

  • notion d”heuristique

• Exemples: http://aispace.org/search/

  • activer l’option Search Options > Pruning > Multiple-Path Pruning

  • choix des algorithmes :

    • Lowest Cost First (Dijkstra)

    • A*

  • exemples:

    • grid1.xml

    • labyrinthe.xml (cas ou l’heuristique est ineffective, voire nocive)

• Autre démo interactive: https://qiao.github.io/PathFinding.js/visual/

Plan de la deuxième séance

• Notion d”espace d’états : représentation des connaissances sur un problème quelconque (pas nécessairement « géographique »)

  • problème du loup, de la chèvre et du chou: f123.xml (spoiler)

  • tours de Hanoi: hanoi.xml (Wikipedia fait allusion à l’espace d’états de ce problème)

• À vous de jouer :

  • Implémentez la résolution des Tours de Hanoi (avec un nombre arbitraire de plateaux) en utilisant cette implémentation de A* : https://forge.univ-lyon1.fr/PA.Champin/intro_ia_astar

  • On considérera que le coût de chaque mouvement est proportionnel à la taille du plateau déplacé (1 pour le plus petit, 2 pour le suivant, etc.).