Td1 avec correction – résolution de problèmes à l’aide de g

Intelligence Artificielle AI - Prolog : TD1 avec Correction – Résolution de problèmes à l’aide de g

Base de l’Intelligence Artificielle 2020-2021

TD1 – Résolution de problèmes à l’aide de graphes d’états

Nous avons vu en cours que pour résoudre un problème, nous pouvons le modéliser afin de construire un graphe d’états et utiliser des algorithmes permettant de rechercher une ou plusieurs solutions dans ce graphe. Une solution est donc un chemin dans le graphe, constitué de la liste des états par lesquels passer, associée aux opérateurs permettant de passer d’un état à un autre.

Il existe plusieurs classes de problèmes : les problèmes de satisfaction de contraintes où nous cherchons un état but respectant les contraintes, peu importe le chemin parcouru ; et les problèmes de planification où nous cherchons les étapes à effectuer pour arriver sur un état but connu.

PARTIE 1 - MODÉLISATION D’UN PROBLÈME DE PLANIFICATION : LE TAQUIN

Le taquin est un puzzle où il faut remettre les nombres dans l’ordre. Il est formé d’une grille de N × N cases avec N² - 1 tuiles numérotées de 1 à N² - 1, une case restant vide. Une tuile adjacente à la case vide peut être déplacée vers celle-ci. Les déplacements se font verticalement ou horizontalement, mais pas en diagonale.

Ce puzzle est souvent utilisé pour tester les algorithmes de recherche. En augmentant la taille de la grille, les problèmes deviennent plus complexes. Les algorithmes actuels résolvent les taquins 3 × 3 et 4 × 4 (avec des espaces d’états de 181 440 et environ 1,3 milliard respectivement), mais les instances 5 × 5 restent difficiles.

Nous souhaitons résoudre un taquin 3 × 3, où les tuiles sont numérotées de 1 à 8. Les états initial et final sont donnés ci-dessous.

État initial :
2 8 3
1 6 4
7 5 (vide)

État final :
1 2 3
4 5 6
7 8 (vide)

Q1 : Modélisation du problème du taquin

Pour modéliser le problème du taquin, nous utilisons le canevas suivant :

États : Chaque état est une configuration des 8 tuiles numérotées de 1 à 8 et de la case vide dans une grille 3 × 3.
État initial : V1=(1,2), V2=(1,1), V3=(3,1), V4=(3,2), V5=(3,3), V6=(2,2), V7=(1,3), V8=(2,1), VE=(2,3).
Opérateurs :
- Haut : Déplacer la case vide vers le haut.
  - Condition : La case vide n’est pas sur la première ligne (VE=(C,L) avec L > 1).
  - Fonction de successeur : La case vide (VE) passe à (C,L-1), et la pièce située en (C,L-1) passe à (C,L).
- Bas : Déplacer la case vide vers le bas.
- Gauche : Déplacer la case vide vers la gauche.
- Droite : Déplacer la case vide vers la droite.
Test de but : L’état but est unique et défini comme V1=(1,1), V2=(2,1), V3=(3,1), V4=(3,2), V5=(3,3), V6=(2,3), V7=(1,3), V8=(2,2), VE=(2,3).
Fonction de coût : Chaque déplacement a un coût de 1. Pour optimiser, on cherche le chemin le plus court.

Q2 : Les 3 premiers niveaux du graphe d’états

Niveau 0 : État initial :

2 8 3
1 6 4
7 5 (vide)

Niveau 1 : États obtenus en déplaçant la case vide vers le haut, le bas, la gauche ou la droite (si possible).

Déplacement vers le haut :
2 8 3
1 5 4
7 6 (vide)

Déplacement vers la gauche :
2 8 3
1 4 6
7 5 (vide)

Q3 : Heuristique pour guider la recherche

Plusieurs heuristiques peuvent être utilisées pour guider l’algorithme A* :

Heuristique W : Nombre de cases non encore en place par rapport à l’état but.
Heuristique P (Manhattan) : Somme des distances "en pâté de maison" entre chaque tuile et sa position dans l’état but.
Heuristique P + 3S : Pour un taquin 3 × 3, combine la distance Manhattan avec un score S basé sur la position des tuiles autour de la case centrale.

PARTIE 2 – RECHERCHE HEURISTIQUE DANS UN GRAPHE D’ÉTATS

L’algorithme A* est une méthode de recherche informée qui utilise une fonction de coût (g) et une heuristique (h) pour trouver la solution optimale.

Q4 : Application de l’algorithme A*

Pour appliquer A* au taquin, nous suivons les étapes suivantes :

Initialisation :
- OUVERTS = {état initial}, FERMES = {}
- g(état initial) = 0, h(état initial) = distance Manhattan ou autre heuristique.
Itération :
- Retirer l’état u avec le plus faible f(u) = g(u) + h(u) de OUVERTS et l’ajouter à FERMES.
- Générer les successeurs v de u en appliquant chaque opérateur possible.
- Pour chaque v, calculer g(v) = g(u) + coût(u,v) et f(v) = g(v) + h(v).
- Si v n’est pas dans FERMES ou si g(v) est inférieur à la valeur précédente, ajouter v à OUVERTS.
Répéter jusqu’à ce que l’état final soit atteint ou que OUVERTS soit vide.

PARTIE 3 - MODÉLISATION D’UN PROBLÈME DE SATISFACTION DE CONTRAINTES : THÉORÈME DES QUATRE COULEURS

Le théorème des quatre couleurs stipule qu’il est possible de colorier n’importe quelle carte en régions connexes avec seulement quatre couleurs, de sorte que deux régions limitrophes aient toujours des couleurs distinctes.

Nous voulons colorier une carte des 13 régions métropolitaines françaises en utilisant uniquement quatre couleurs.

Q5 : Modélisation du problème de coloration

Pour modéliser ce problème selon le canevas donné, nous avons :

États : Chaque état est une configuration des 13 régions, où chaque région est soit vide, soit colorée avec l’une des quatre couleurs.
État initial : Aucune région n’est colorée (13 variables vides).
Opérateurs :
- Action : Affecter une couleur à une région vide.
- Condition : La couleur choisie ne doit pas être identique à celle des régions adjacentes.
- Fonction de successeur : La région sélectionnée prend la couleur choisie, et les autres restent inchangées.
Test de but : Toutes les régions sont coloriées et aucune région adjacente n’a la même couleur.
Fonction de coût :
- Simple : Coût de 1 par affectation de couleur.
- Heuristique : Utiliser le degré de saturation (DSAT) pour prioriser les régions difficiles à colorier.

Q6 : Les 3 premiers niveaux du graphe d’états

Niveau 0 : Aucune région colorée.

Niveau 1 : Une région colorée parmi les 13 possibles.

Niveau 2 : Deux régions colorées, respectant les contraintes d’adjacence.

Q7 : Heuristique pour guider la recherche

Une heuristique efficace pour ce problème est le degré de saturation (DSAT) :

DSAT(v) = nombre de couleurs différentes déjà utilisées par les régions adjacentes à v.
Heuristique : Choisir la région avec le plus grand DSAT pour la colorier en premier.

Q8 : Application de l’algorithme A*

L’algorithme A* peut être appliqué ici, mais il n’est pas optimal en raison du nombre élevé de successeurs à chaque étape. Il est préférable de traiter ce problème sous forme de CSP (Constraint Satisfaction Problem).

FAQ

1. Pourquoi l’algorithme A* est-il efficace pour le taquin mais pas pour le théorème des quatre couleurs ?

Dans le taquin, chaque état a un nombre limité de successeurs (au maximum 4). En revanche, pour le théorème des quatre couleurs, le nombre de successeurs explose rapidement (chaque région peut être colorée avec 4 couleurs différentes, sans contrainte de validité immédiate).

2. Qu’est-ce qu’une heuristique monotone ?

Une heuristique monotone est une fonction qui ne diminue jamais au fur et à mesure que l’on se rapproche de l’état but. Cela garantit que l’algorithme A* trouvera toujours une solution optimale.

3. Comment calculer la distance Manhattan pour le taquin ?

Pour chaque tuile, on additionne la valeur absolue de la différence entre sa ligne actuelle et sa ligne cible, et celle entre sa colonne actuelle et sa colonne cible. La somme de ces distances pour toutes les tuiles donne l’heuristique P.