Prolog

TD n°7

Planification dynamique en Prolog

Le but du TD est d'explorer les aspects "dynamiques" de Prolog via l'application classique de la planification d'actions dans le "monde des blocs".

Déclarer des faits dynamiques

Le "monde des blocs" est constitué d'objets élémentaires (boîtes, cubes, boules, pyramides...) disposés dans un espace plan. On va réaliser des actions dans ce monde (déplacer un objet d'un endroit à un autre). Par exemple, on va passer de la situation 1 à la situation 2 :


situation 1	situation2

Cela signifie que des faits vrais à un certain moment (le fait que le bloc a soit sur le bloc b), deviennent faux à d'autres. Pour déclarer de tels faits, on déclare certains prédicats comme "dynamiques".

:- dynamic(sur/2).

sur(a,b).    
sur(b,c).    
sur(c,table).

On ne peut déplacer qu'un objet qui est "libre", c'est-à-dire en haut d'une pile, et on ne peut le mettre que sur la table (qui est supposée toujours "libre") ou en haut d'une autre pile. En réalisant ce déplacement, on retire de l'ensemble des faits l'ancien positionnement du bloc déplacé, et on ajoute son nouveau positionnement. On peut donc définir l'action de déplacement avec les prédicats suivants :

libre(table).
libre(a).

met_sur(X,Y) :-
     X \== table,
     X \== Y,
     libre(X),
     libre(Y),
     sur(X,Z),
     retract(sur(X,Z)),
     asserta(sur(X,Y)),
     asserta(deplace(X,Y)).

Dans ce code, le métaprédicat "retract(...)" retire de la base de faits ce qui ne doit plus être considéré comme vrai, tandis que "asserta(...)", lui, ajoute un nouveau fait devenu vrai. L'action de déplacement elle-même est stockée dans le terme "deplace(X,Y)". Une fois ce code chargé, on peut réaliser les opérations suivantes, où le métaprédicat listing(Predicat) donne toutes les instances vraies de Predicat :

| ?- listing(libre).

libre(table).
libre(a).

yes
| ?- listing(sur).  

sur(a,b).
sur(b,c).
sur(c,table).

yes
| ?- met_sur(a,table).

yes
| ?- listing(sur).    

sur(a,table).
sur(b,c).
sur(c,table).

yes
| ?- listing(deplace).

deplace(a,table).

yes
| ?- listing(libre).  

libre(table).
libre(a).

Quel est le problème ? Modifier le code en conséquence... Vous pouvez utiliser la négation de certains prédicats, à conditions que ses arguments soient instanciés au moment où on fait appel à cette négation.

Planification récursive

Faire de la planification consiste à créer des plans, c'est-à-dire des suites d'actions, permettant de passer d'un état à un autre. Ici, notre plan sera constitué de l'ensemble des actions de déplacement effectuées, on le visualisera donc par l'instruction listing(deplace). Chaque action dans un plan doit être définie en 3 étapes :

les préconditions : ensemble des faits qui doivent être vrais pour que l'action puisse être réalisée
la suppression des faits devenus faux après l'action
l'ajout des nouveaux faits vrais, y compris de l'action réalisée

Dans l'exemple précédent, vous pouvez vérifier que si les préconditions ne sont pas remplies, l'action n'est pas effectuée :


| ?- met_sur(c,a).

no

Evidemment, pour que les préconditions soient vérifiées, il suffit de réaliser des actions qui les rendent vraies, ce qui peut amener à définir des actions récursives. Ecrire une version récursive de met_sur en définissant un prédicat liberer qui rend vraie la précondition libre en réalisant une action si besoin. Cette version récursive devrait permettre de mettre le bloc b sur le bloc a en passant par plusieurs étapes intermédiaires, comme dans le dessin suivant (où r_put_on(X,Y) est la version récursive d'un prédicat non récursif put_on(X,Y)): graphe de changement de situation

Plan pour atteindre un état

Un but est plus facilement décrit par une liste de faits qui doivent tous être vrais en même temps. Par exemple, on veut passer de l'état de départ (pile "a sur b sur c sur table") à un état décrit par "c sur b sur a sur table". Le but est donc décrit par la liste : [sur(c,b),sur(b,a),sur(a,table)]. Ecrire le programme qui produit un plan rendant vraie une telle liste.

Attention, il ne suffit pas de parcourir la liste et de lancer une planification sur chacun de ses éléments les uns après les autres, car le plan rendant vrai un élément peut rendre faux un élément précédent. Pour chaque élément de la liste, il faut donc vérifier que tous les éléments précédents sont encore vrais.

Extensions

On peut améliorer notre monde des blocs en ajoutant des formes nouvelles :

des pyramides, qui peuvent se poser sur la table mais sur lesquelles on ne peut rien poser
des boules qui peuvent être mises dans des boîtes, quand elles sont vides (si les cubes sont en fait des boîtes) mais sur lesquelles on ne peut rien poser
des blocs allongés plus grands que les cubes, qu'on peut empiler les uns sur les autres et sur lesquels on peut mettre des cubes ou des boîtes, mais qu'il vaut mieux ne pas poser eux-mêmes sur des cubes ou des boîtes.

Dernière modification : 9/9/2011