/* APPENDIX B Section B.1 An Interpreter for Temporal Golog Programs */ /*********************************************************************** A Golog interpreter with preferences, rewards and utilities based on Trans-interpreter by DeGiacomo, Lespérance, Levesque, IJCAI-1997 and the idea of sequential, temporal Golog by Reiter, KR-1998 ***********************************************************************/ :- lib(r). :- lib(fromonto). :- set_flag(print_depth,300). :- pragma(debug). /* :- nodbgcomp. */ :- set_flag(all_dynamic, on). :- dynamic(proc/2). :- set_flag(all_dynamic, on). :- op(800, xfy, [&]). /* Conjunction */ :- op(850, xfy, [v]). /* Disjunction */ :- op(870, xfy, [=>]). /* Implication */ :- op(880,xfy, [<=>]). /* Equivalence */ :- op(950, xfy, [:]). /* Action sequence.*/ :- op(960, xfy, [#]). /* Nondeterministic action choice.*/ /* GOLOG clauses. */ /* trans(Prog,Sit,Prog_r,Sit_r) */ trans(P1 : P2,S,P2r,Sr) :- final(P1,S),trans(P2,S,P2r,Sr). trans(P1 : P2,S, P1r : P2,Sr) :- trans(P1,S,P1r,Sr). trans(?(C),S,nil,S) :- holds(C,S). trans(P1 # P2,S,Pr,Sr) :- trans(P1,S,Pr,Sr) ; trans(P2,S,Pr,Sr). trans(pi(V,P),S,Pr,Sr) :- sub(V,_,P,PP), trans(PP,S,Pr,Sr). trans(star(P),S,PP : star(P),Sr) :- trans(P,S,PP,Sr). trans(if(C,P1,P2),S, Pr,Sr) :- holds(C,S), trans(P1,S,Pr,Sr) ; holds(-C,S), trans(P2,S,Pr,Sr ). trans(while(C,P),S,Pr,Sr) :- holds(-C,S), Pr=nil, Sr=S; holds(C,S), trans(P : while(C,P),S, Pr,Sr). trans(P,S,Pr,Sr) :- proc(P,Pbody), trans(Pbody,S,Pr,Sr). trans(A,S,nil,do(A,S)) :- primitive_action(A), deterministic(A), poss(A,S), start(S,T1), time(A,T2), T1 $<= T2. /* NEW GOLOG CONSTRUCT: pick the best value for a variable. Beware that be(V,E) fails if there is no execution of E1 (E with an instantiated V) leading to a situation S1 such that pref(S1,S,S) (i.e., S1 better than the current situation S). But if an execution of be(V,E) terminates it results in a better situation than the current situation S. */ trans(be(V,E),S,Pr,Sr) :- sub(V,_,E,E1), trans(E1,S, Pr,Sr), bestSit(Pr,Sr, Sbest), not dominated(be(V,E),S,E1,Sbest). bestSit(E,S,Best) :- offline(E,S,Best), not ( offline(E,S,Sf), pref(Sf,Best,S) ), pref(Best,S,S). dominated(be(V,E),S,E1,S1) :- sub(V,_,E,E2), bestSit(E2,S,S2), E2 \= E1, pref(S2,S1,S). /* NEW GOLOG CONSTRUCT: pick a good value for a variable. Beware that an execution of good(V,E) may result in a situation S1 such that pref(S1,S,S) is false (i.e., S1 is not better than the current situation S). But if there is a terminating execution of E1 (E with an instantiated V), then good(V,E) terminates too. */ trans(good(V,E),S, Pr,Sr) :- sub(V,_,E,E1), trans(E1,S, Pr,Sr), offline(Pr,Sr, Sgood ), not ( offline(E1,S,S12), pref(S12,Sgood,S) ), not better(good(V,E),S,E1,Sgood). better(good(V,E),S,E1,S1) :- sub(V,_,E,E2), offline(E2,S,S2), E2 \= E1, not ( offline(E2,S,S21), pref(S21,S2,S) ), pref(S2,S1,S). /* final(Prog,Sit) */ final(nil,S). final(fail,S). final(P1 : P2,S) :- final(P1,S),final(P2,S). final(P1 # P2,S) :- final(P1,S) ; final(P2,S). final(pi(V,P),S) :- final(P,S). final(star(P),S). final(P_Args,S) :- proc(P_Args,Pbody), final(Pbody,S). /* transCL(Pr,S,Pr_r,S_r) is the transitive closure of trans(Pr,S,Pr_r,S_r) */ transCL(P,S,P,S). transCL(P,S,Pr,Sr) :- trans(P,S,PP,SS), transCL(PP,SS,Pr,Sr). /* offline(Pr,S,Sr): Sr is the situation resulting after doing Pr in S */ offline(Prog,S0,Sf) :- final(Prog,S0), Sf=S0; trans(Prog,S0,Prog1,S1), offline(Prog1,S1,Sf). bestTrans(Delta,S,Delta2,S2) :- trans(Delta,S,Delta2,S2), offline(Delta2,S2,Best), not ( offline(Delta,S,Sf), pref(Sf,Best,S) ), % pref(Best,S,S), util(Ut, Best), U $=< Ut, rmax(U), current_stream(reports, X, Stream), printf(Stream, "\n >> Current program = %w\n >> Next Program = %w\n >> BestPlan = %w \n >> Utility = %w \n", [Delta,Delta2,Best,U]). /* Preferences and rewards */ /* pref(S1,S2,S): the situation S1 is better than S2 wrt S. On the situation tree, S is a predecessor of both S1 and S2 */ /* A simple implementation of preferance relation by means of utilities */ pref(S1, S2, S) :- util(Val1,S1), V1 $=< Val1, util(Val2,S2), V2 $=< Val2, rmax(V1), rmax(V2), !, /* no backtracking */ V1 > V2. % util(V,S) is a fluent: V is a total utility in situation S. % See an example of utility function in the file "coffee" /* Time specific clauses. */ start(do(A,S),T) :- time(A,T). /* start( s0, 0 ). Say this in the file coffee */ /* "now" is a synonym for "start". */ now(S,T) :- start(S,T). /* schedMin(S1, Sg) determines a schedule such that times of occurrences are minimized. */ schedMin(S1,S1). schedMin(S1,do(A,S2)) :- S1==S2, time(A,T), (nonground(T) -> rmin(T); true). schedMin(S1,do(A,S2)) :- S1\==S2, schedMin(S1,S2), time(A,T), (nonground(T) -> rmin(T); true). /* sub(Name,New,Term1,Term2): Term2 is Term1 with Name replaced by New. */ sub(X1,X2,T1,T2) :- var(T1), T2 = T1. sub(X1,X2,T1,T2) :- not var(T1), T1 = X1, T2 = X2. sub(X1,X2,T1,T2) :- not T1 = X1, T1 =..[F|L1], sub_list(X1,X2,L1,L2), T2 =..[F|L2]. sub_list(X1,X2,[],[]). sub_list(X1,X2,[T1|L1],[T2|L2]) :- sub(X1,X2,T1,T2), sub_list(X1,X2,L1,L2). /* The holds predicate implements the revised Lloyd-Topor transformations on test conditions. */ holds(P & Q,S) :- holds(P,S), holds(Q,S). holds(P v Q,S) :- holds(P,S); holds(Q,S). holds(P => Q,S) :- holds(-P v Q,S). holds(P <=> Q,S) :- holds((P => Q) & (Q => P),S). holds(-(-P),S) :- holds(P,S). holds(-(P & Q),S) :- holds(-P v -Q,S). holds(-(P v Q),S) :- holds(-P & -Q,S). holds(-(P => Q),S) :- holds(-(-P v Q),S). holds(-(P <=> Q),S) :- holds(-((P => Q) & (Q => P)),S). holds(-all(V,P),S) :- holds(some(V,-P),S). holds(-some(V,P),S) :- not holds(some(V,P),S). /* Negation */ holds(-P,S) :- isAtom(P), not holds(P,S). /* by failure */ holds(all(V,P),S) :- holds(-some(V,-P),S). holds(some(V,P),S) :- sub(V,_,P,P1), holds(P1,S). /* The following clause treats the holds predicate for non fluents, including Prolog system predicates. For this to work properly, the GOLOG programmer must provide, for all fluents, a clause giving the result of restoring situation arguments to situation-suppressed terms, for example: restoreSitArg(ontable(X),S,ontable(X,S)). */ holds(A,S) :- restoreSitArg(A,S,F), F ; not restoreSitArg(A,S,F), isAtom(A), A. isAtom(A) :- not (A = -W ; A = (W1 & W2) ; A = (W1 => W2) ; A = (W1 <=> W2) ; A = (W1 v W2) ; A = some(X,W) ; A = all(X,W)). restoreSitArg(poss(A),S,poss(A,S)). restoreSitArg(start(T),S,start(S,T)). restoreSitArg(now(T),S,now(S,T)). restoreSitArg(currentSit(Sc), S, currentSit(Sc,S)). restoreSitArg(util(V), S, util(V,S)). restoreSitArg(pref(S1,S2), S, pref(S1,S2,S)). currentSit(S1,S2) :- S1=S2.