Intelligence Artificielle AI - Prolog : TD 2 Représentation et résolution de problème (2)
Télécharger PDFProblème de planification : illustration avec le monde des cubes
Un bras articulé équipé d'une pince permet de manipuler un cube : le saisir, le déplacer, le poser sur une table ou l'empiler sur un autre cube. La pince ne peut prendre qu'un seul cube à la fois, et seul un cube sans empilement peut être saisi.
2.1 Description d'un état et opérateurs de transition
Pour décrire un état, il faut identifier les variables représentant la position de chaque cube (par exemple, "sur la table", "empilé sur X", ou "dans la pince"). Les opérateurs doivent refléter les actions possibles de la pince : saisir un cube, le déplacer, le poser sur la table ou l'empiler sur un autre cube.
Pour tester la satisfaction d'un objectif, il faut vérifier si la configuration finale correspond à l'état souhaité (par exemple, tous les cubes empilés dans un ordre précis).
2.2 Construction de l'hypergraphe correspondant
Sur la base de cette modélisation, l'hypergraphe doit inclure les états possibles comme sommets et les actions de la pince comme hyperarêtes reliant ces états.
2.3 Comparaison des configurations finales
a) Configuration : (C posé sur la table) ET (B posé sur C) ET (A posé sur B). La résolution doit respecter cet ordre précis.
b) Configuration : (A posé sur B) ET (B posé sur C) ET (C posé sur la table). La résolution doit également suivre cet ordre.
La résolution est-elle identique dans les deux cas ? (À analyser séparément en respectant l'ordre des conjonctions.)
Problèmes de satisfaction de contraintes : illustration avec le problème des reines
Cette section introduit le paradigme de la satisfaction de contraintes à travers un problème de 4 reines. Chaque reine est placée sur une case définie par deux variables : Xi = j, où X représente la ligne i et j la colonne.
3.1 Méthode « générer et tester »
Combien d'affectations différentes faut-il tester pour trouver toutes les solutions possibles ?
3.2 Méthode « retour arrière »
Dans cette approche, on annule les placements quand il devient évident qu'aucune solution n'est possible. Il faut détailler les étapes d'affectation et les retours en arrière nécessaires.
3.3 Méthode « filtrage »
À chaque placement, on réduit le domaine des variables restantes. Si une variable n'a plus de domaine valide avant d'atteindre une solution complète, le processus s'arrête.
FAQ
Qu'est-ce qu'un hypergraphe dans ce contexte ?
Un hypergraphe est une structure mathématique où les sommets représentent les états possibles et les hyperarêtes les actions (ou transitions) entre ces états.
Pourquoi l'ordre des empilements est-il important ?
L'ordre des empilements définit des contraintes spécifiques sur les actions possibles, influençant la séquence de résolution et les états intermédiaires.
Comment la méthode « retour arrière » optimise-t-elle la recherche ?
Elle évite de tester des configurations impossibles en annulant les placements dès qu'un conflit est détecté, réduisant ainsi le nombre d'étapes inutiles.