RCS file: RCS/gps.lisp,v Working file: gps.lisp head: 1.8 branch: locks: strict narby: 1.8 access list: symbolic names: keyword substitution: kv total revisions: 8; selected revisions: 8 description: ---------------------------- revision 1.8 locked by: narby; date: 2000/11/24 21:51:55; author: narby; state: Exp; lines: +166 -75 VERSION COMPLETE ORIGINALE de Norvig ---------------------------- revision 1.7 date: 2000/11/24 21:51:00; author: narby; state: Exp; lines: +61 -25 On gere des etats courants locaux. En effet, dans le cadre d'un but multiple, gerer l'etat courant par une variable globale comme *state* n'etait pas tres malin (c'est le probleme que Norvig appelle le "leaping before you look"): d`es qu'une action etait possible, i.e. toutes ses preconditions etaient satisfaites, elle etait effectuee, et cela sans penser aux consequences pour la suite. On avait donc un "backtracking" partiel qui s'appliquait a chacun des buts separemment (Norvig parle de "planning" qui se melange a l'execution et il a raison). Effets: - on se debarasse de "*state*" et donc "achieve-all", "achieve" et "apply-op" ont l'etat courant "state" en argument. D'autre part, "achieve-all" et "apply-op" renvoient des etats courants. - l'appel principal dans "gps" est transform'e en: (remove-if-not #'action-p (achieve-all (cons '(start) state) goals nil))) - la construction d'un nouvel etat courant est effectu'e dans "apply-op" et est stock'ee dans "state2" qui correspond a l'etat lorsque toutes les preconditions sont satisfaites. - le stockage du nouvel etat courant est fait dans "achieve-all" qui est appliqu'e apres chaque resolution de sous-but. Le test principal: (and (every #'(lambda (g) (achieve g goal-stack)) goals) (subsetp goals *state*))) est remplac'e par: (if (and (every #'(lambda (g) (setf current-state (achieve current-state g goal-stack))) goals) (subsetp goals current-state :test #'equal)) current-state))) (NB: la forme lambda est correcte puisque : (setf x nil) renvoie NIL) ---------------------------- revision 1.6 date: 2000/11/24 21:50:01; author: narby; state: Exp; lines: +18 -52 On construit une memoire des buts qui sont en train d'etre resolus, et la recherche dans une voie est abandonnee si on retombe sur le meme but a resoudre (les boucles ne sont alors plus possibles). Effets: - il faut gerer une pile des buts "goal-stack", et donc "achieve-all", "achieve" et "apply-op" ont cette pile en argument. - C'est dans l'appel principal de "apply-op" que l'on augmente la pile des buts: (when (achieve-all (op-preconds op)) est remplac'e par: (when (achieve-all (op-preconds op) (cons goal goal-stack)) - (NB: ces predicats deviennent n-aires et donc doivent souvent s'utiliser avec des "lambdas" pour les rendre unaires). ---------------------------- revision 1.5 date: 2000/11/24 21:49:14; author: narby; state: Exp; lines: +79 -11 On garde la trace des actions faites en les stockant dans l'etat courant "*state*" et la reponse de gps n'est plus un simple 'solved mais la liste des actions effectuee (et donc sortie beaucoup plus reutilisable). Effets: - toute action "a" possede dans son "add-list" la condition particuliere "(EXECUTING a)". - on se donne des fonctions de constructions d'operateurs et de predicats qui verifient cette forme (egalement, une fonction de conversion pour utiliser les domaines deja ecrits). ex: (convert-op (make-op :action 'telephone-shop :preconds '(know-phone-number) :add-list '(in-communication-with-shop))) #S(OP :ACTION TELEPHONE-SHOP :PRECONDS (KNOW-PHONE-NUMBER) :ADD-LIST ((EXECUTING TELEPHONE-SHOP) IN-COMMUNICATION-WITH-SHOP) :DEL-LIST NIL) - on enleve le "print" dans apply-op. - on filtre la sortie en enlevant tous les elements qui ne sont pas sous la forme "(executing a)". Cela necessite que: on ajoute une etiquette de depart "(start)" qui permet de distinguer un NIL issu d'un echec ou d'un etat qui ne demande aucune application d'operateur (par le point precedent, on filtre tous les elements de l'etat courant; si le but en fait partie, aucune action n'a a etre prise, et donc le filtre enleve tout. On a donc un filtre "action-p" qui s'applique sur "*start*". on ne peut plus utiliser "set-difference" et "union" dans le code de "apply-op", car ceux-ci ne preservent pas l'ordre. L'etat est sense cependant etre apres le filtrage representatif de l'ordre d'execution: on fait donc un append de la "add-list" et de la liste *state* de l'etat courant sur laquelle on a appliqu'e un remove-if de la "del-list": (setf *state* (set-difference *state* (op-del-list op))) (setf *state* (union *state* (op-add-list op))) est remplac'e par: (setf *state* (append (remove-if #'(lambda (x) (member-equal x (op-del-list op))) *state*) (op-add-list op))) ---------------------------- revision 1.4 date: 2000/11/24 21:44:54; author: narby; state: Exp; lines: +41 -36 L'ensemble des op'erations est li'e exterieurement a gps. Effet: - la signature de gps: "(defun GPS (*state* goals &optional (*ops* *ops*))" - Une fonction "use" qui fixe l'ensemble des op'erateurs et dont voici un appel "(use *school-ops*)" ---------------------------- revision 1.3 date: 2000/11/24 21:44:22; author: narby; state: Exp; lines: +41 -30 Une condition devient une liste (en fait, qqch. qui ressemble a un predicat PROLOG; cela permet plus de expressivit'e.) Effet: faire les appels "member" en "member #'equal" (en fait, on construit la fonction "member-equal" associ'ee) ---------------------------- revision 1.2 date: 2000/11/24 21:41:39; author: narby; state: Exp; lines: +7 -14 Verification qu'a la fin tous les buts sont valides (et donc qu'il n'y a pas d'effets genants d^us a la sequentialit'e de la resolution des buts). Effet: - au lieu de l'appel "(every #'achieve goals)" qui implique la sequentialit'e, on utilisera: "(and (every #'achieve goals) (subsetp goals *state*)) 'solved)" - on met cet appel dans une fonction "achieve-all" et on l'appelle dans les fonctions "gps" et "apply-op". ---------------------------- revision 1.1 date: 2000/11/24 21:40:31; author: narby; state: Exp; Initial revision =============================================================================