Il s'agit de réaliser un générateur de plans linéaires (plans complètement ordonnés).
Dans une première partie, on ne s'intéressera qu'à des problèmes simples, sans interaction de sous-buts.
On pourra cependant modifier l'ordre des sous-buts dans le problème initial.
Le problème de la mise à jour de la description de l'univers est réglé de la façon suivante :
Le langage utilisé doit être PROLOG (SWI Prolog).
La planification a été développée et testée pour résoudre le problème de l'empilement de cubes, qui consiste à partir d'un ensemble de cubes dans une situation de départ (sur le sol, ou sur un autre cube), à trouver un liste de déplacements à effectuer (on ne peut bouger qu'un seul cube à la fois, s'il n'y a pas de cube posé sur lui) afin d'obtenir une configuration finale souhaitée.
Nous avons commencé par la mise en place des opérateurs les plus simples, comme equal, et dif.
Nous avons continué par est_vrai qui présentait l'avantage d'être testé indépendamment des fonctions pas encore implémentées.
Cet opérateur vérifie si un fait (on ou clear) est vrai à un moment donné ou non.
Il opère une recherche dans le plan, ou dans les états initiaux si le plan est vide.
Puis nous avons mis en place res1 qui est la fonction qui génère le plan.
Cette fonction regarde si un fait a été rendu vrai par l'état initial ou par une action,
et si aucune action contraire n'a rendu ce fait faux depuis.
res2 vérifie si la liste de faits n'est pas impossible au sens des imposs spécifiés.
permettre est chargée de vérifier si c'est possible,
et d'ajouter dans le plan les actions nécessaires pour rendre vrai.
resoudre enfin, est le point d'entrée du programme.
/* set_prolog_flag(unknown,fail). */ /* A faire à la main */ /* ----- partie fournie en sujet ------- */ ad(on(U,W),move(U,_,W)). ad(clear(V),move(_,V,_)). del(on(U,V),move(U,V,_)). del(clear(W),move(_,_,W)). can(move(U,V,floor),model(on(U,V)),prc([not_equal(V,floor)]), npb(clear(U))). can(move(U,V,W),model(on(U,V)),prc([not_equal(V,W),not_equal(U,W)]),npb([clear(U),clear(W)])). always(clear(floor)). /** etat impossible */ imposs([on(floor,_)]). imposs([on(_,Y),clear(Y)]). imposs([on(X,Y),on(X,Z)]):-dif(Y,Z). imposs([on(X,X)]). imposs([on(X,Y),on(Y,X)]). /** etat initial */ given(start,on(a,floor)). given(start,on(b,floor)). given(start,on(c,a)). given(start,clear(b)). given(start,clear(c)). /* ------ Début développement personnel ------- */ equal(X,X). not_equal(X,Y):- X \== Y. dif(X,Y):-not_equal(X,Y). /** Retourne vrai si chaque element de la liste1, appartient a la liste2, faux sinon */ member2([],_). member2([A|B],X):-member(A,X),member2(B,X). /** Teste si un fait est vrai, d'après les always, les ad et del */ /* vrai quel que soit le plan */ est_vrai([],_). /* on cherche en priorite les etats toujours vrais */ est_vrai([FAIT],_):-always(FAIT). /* vrai si la derniere action cree un ad */ est_vrai([FAIT],[A|_]):-ad(FAIT,A),!. /* vrai si la derniere action cree un del */ est_vrai([FAIT],[A|_]):-del(FAIT,A),!,fail. /* appel reccursif a est_vrai */ est_vrai([FAIT],[_|B]):-est_vrai([FAIT],B). /* vrai si on est dans l'etat initial */ est_vrai([FAIT],[]):-given(start,FAIT). /** Retourne vrai si chaque element de la liste1 qui est vrai dans imposs, appartient a la liste2 */ inclu(X,Y):-member2(X,Y),imposs(X),!. /** Vrai si l'ensemble de la liste est vrai ou si la liste est vide */ verif_equal([]). /* cas_recursif */ verif_equal([A|B]):-A,verif_equal(B). /** creation du mouvement si il est possible et rajout dans le plan de ce mouvement */ permettre(X,AP,[Z|NP]):-ad(X,Z),can(Z,model(B),prc(C),npb(D)),verif_equal(C),est_vrai([B],AP),res1(D,AP,NP). permettre(X,AP,[Z|NP]):-ad(X,Z),can(Z,npb(D)),res1(D,AP,NP). /** planification */ /* cas d'arret */ res1([],P,P):-!. /* si le but est deja cree pas besoin de rajouter une action dans le nouveau plan */ res1([X],AP,AP):-est_vrai([X],AP),!. /* lorsqu'on a un seul sous-but */ res1([X],AP,NP):-permettre(X,AP,NP). /* cas ou on a au moins deux buts (recursif) */ res1([X|[Y|L]],AP,NP):-res1([X],AP,NP1),res1([Y|L],NP1,NP). /** cas impossible prioritaire */ res2(X,_,_):-imposs(Y),inclu(Y,X),!,writeln(impossible). /** fonction appelante de la planification (fonction principale) */ resoudre(X,Y):-not(res2(X,Y,Y)),res1(X,[],Y).
Voici une trace de l'exécution sur le problème des cubes.
[pc3:/projet2] pl -f plan.prolog % /users/g1/irr/irr03/prive/prolog/projet2/plan.prolog compiled 0.00 sec, 8,376 bytesWelcome to SWI-Prolog (Version 5.0.7) Copyright (c) 1990-2002 University of Amsterdam. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- set_prolog_flag(unknown,fail). Yes ?- resoudre([on(a,b)],P). P = [move(a, floor, b), move(c, a, floor)] ; No ?- halt.
Le début de se projet c'est avéré assez difficile, par manque d'expérience de projets prolog.
En se regroupant à plusieurs dans le même cas, nous sommes arrivés à produire un résultat qui semble assez satisfaisant.
Nous n'avons pas traité le problème de la régression, mais la planification directe marche bien.
Nous avons opéré de légères modifications afin que notre programme puisse résoudre aussi un autre problème de calculette
qui nous a été proposé.