1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2% FILE : Interpreters/transfinal-search.pl 3% 4% IndiGolog TRANS & FINAL Implementation for 5% various search operators (IndiGolog) 6% 7% AUTHOR : Sebastian Sardina 8% EMAIL : ssardina@cs.toronto.edu 9% WWW : www.cs.toronto.edu/~ssardina www.cs.toronto.edu/cogrobo 10% TYPE : system independent code 11% TESTED : SWI Prolog 5.0.10 http://www.swi-prolog.org 12% 13% For more information on Golog and some of its variants, see: 14% http://www.cs.toronto.edu/~cogrobo/ 15% 16%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 17% 18% This file provides: 19% 20% -- trans(P,H,P2,H2) : configuration (P,H) can perform a single step 21% to configuration (P2,H2) 22% -- final(P,H) : configuration (P,H) is terminating 23% 24% The following special features are also provided: 25% 26% 27% 28% The following is required for this file: 29% 30% -- wscp(Name,G,Max,IA,SimNo,H,E): WSCP implementation 31% Name : name of the planning problem 32% G : goal to be achieved 33% IA : initial list of possible actions 34% SimNo: identification of the exogenous action simulator to be used 35% H : Initial situation-history 36% E : SOLUTION: CONDITIONAL PLAN 37% 38% FROM SYSTEM CODE DEPENDING ON WHERE IT IS USED 39% -- report_message(T, M) : report message M of type T 40% 41% FROM TEMPORAL PROJECTOR: 42% -- isTrue(+C, +H) 43% Conditio C is true at history H 44% -- calc_arg(+A, -A2, +H) 45% calculate the arguments of action A at history H 46% -- domain(-V, +D) 47% -- rdomain(-V, +D) 48% object V is an element of domain D (random) 49% -- getdomain(+D, -L) 50% L is the list of elements in domain D 51% -- sensed(+A, ?V, ?H) 52% action A got sensing result V w.r.t. history H 53% 54%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 55 56 57 58 59%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 60%% (D) INDIGOLOG SEARCH CONSTRUCTS 61%% 62%% (D.1) search(E,M) : linear search on E, with message M 63%% (D.1) search(E) : linear search on E 64%% (D.1) searchg(P,E,M) : linear search on E, with message M, replanning condition P 65%% (D.1) search(P,E) : linear search on E, replanning condition P 66%% (D.1) searcho(P,Options) : linear search on E, with list of Options 67%% 68%% (D.2) searchc(E,M) : conditional search on E, with message M 69%% (D.2) searchc(E) : conditional search on E 70%% 71%% (D.3) achieve(G,Max,IA) : CONDITIONAL PLANNER WSCP (Hector Levesque) 72%% 73%% (D.4) fullSearch : INTERRUPTABLE SEARCH (BETA VERSION) 74%% still not attached to any Golog construct 75%% (D.5) searchr(E,LGoals,FluentAssum,M): RATIONAL SEARCH (BETA VERSION) 76%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 77 78%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 79%% (D.1) TRADITIONAL SEARCH (From [De Giacomo & Levesque 99]) 80%% 81%% Linear plans, ignore sensing 82%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 83 84 85%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 86% search(E): search on E, using caching and replanning only when 87% situation is not the expected one 88%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 89final(search(E,_),H) :- final(search(E),H). 90final(search(E),H) :- final(E,H). 91 92trans(search(E,M),H,E1,H1):- 93 report_message(program, ['Thinking linear plan on: ', M]), 94 (trans(search(E),H,E1,H1) -> 95 report_message(program, 'Finished thinking: Plan found!') 96 ; 97 report_message(program, 'Finished thinking: No plan found!'), 98 fail 99 ). 100 101% if findpath/3 wants to abort everhting it has to throw exception search 102% you can obtain the vanilla search version by having Prolog code to 103% ignore both catch/3 and throw/1. 104trans(search(E),H,followpath(E1,L),H1) :- 105% store_node(search, E, H), % For debugging 106 catch( (trans(E,H,E1,H1), findpath(E1, H1, L)) , search, fail). 107trans(search(E,M),H,E1,H1):- 108 report_message(program, ['Thinking linear plan on: ', M]), 109 (trans(search(E),H,E1,H1) -> 110 report_message(program, 'Finished thinking: Plan found!') 111 ; 112 report_message(program, 'Finished thinking: No plan found!'), 113 fail 114 ). 115 116% findpath(E,H,L): find a solution L for E at H; 117% L is the list [E1,H1,E2,H2,...,EN,HN] encoding 118% each step evolution (Ei,Hi) where final(EN,HN) 119% 120% If last action was commit, then try to find a plan with what remains 121% if no plan is possible then throw exception "search" to abort the 122% whole search 123findpath(E,[commit|H],L) :- !, (findpath(E,H,L) -> true ; throw(search)). 124findpath(E,H,[E,H]) :- final(E,H). 125findpath(E,H,[E,H|L]) :- 126% store_node(search, E, H), % For debugging only 127 trans(E,H,E1,H1), 128 findpath(E1,H1,L). 129 130 131% followpath(E,L): execute program E wrt expected sequence of 132% configurations L=[E,HEx,E1,H1,...] 133% if the current history does not match the next expected one 134% in L (i.e., H\=HEx), then redo the search for E from H 135final(followpath(E,[E,H]),H) :- !. 136final(followpath(E,_),H) :- final(E,H). /* off path; check again */ 137trans(followpath(E,[E,H,E1,H1|L]),H,followpath(E1,[E1,H1|L]),H1) :- !. 138trans(followpath(E,_),H,E1,H1) :- trans(search(E),H,E1,H1). /* redo search */ 139 140 141%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 142%% searchext(P,Opt) : search for E with options Opt 143%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 144 145trans(searchn(E,LOptions),H,mnt(E,H,followpath(E1,L),LOptions),H1) :- 146 trans(E,H,E1,H1), 147 findpathn(E1, H1, L, LOptions). 148final(search(E,opt(_LOptions)),H) :- final(E,H). 149 150findpathn(E,H,[E,H],_LOpt) :- final(E,H). 151findpathn(E,H,[E,H|L],LOpt) :- 152 trans(E,H,E1,H1), 153 (H1=[A|H], member(assumptions(LAssumptions), LOpt), add_assumptions(A,LAssumptions,ExogAss,_TestAss) -> 154 E2 = [ExogAss|E1] 155 ; 156 E2 = E1 157 ), 158 findpathn(E2,H1,L,LOpt). 159 160% LAssumption is a list of assumptions of the form [A, Exog]: If A just happend 161% then assume Exog will ocurr right away. 162% 163% If action A has just been executed in H, then assume exog action Exog 164% occurrs. _Test is supposed to encode a test to wait for the exog. action (not used at this point) 165add_assumptions(A, LAssumptions, Exog, _Test) :- 166 copy_term(LAssumptions,LAssumptionsCopy), % get a copy of the assumptions to avoid binding their orig vars 167 member([A, Exog], LAssumptionsCopy).
172final(mnt(_,_,followpath(E,[E,H]),_),H) :- !. 173final(mnt(_,_,followpath(E,_),_),H) :- final(E,H). /* off path; check again */ 174 175 176trans(mnt(EO,HO,followpath(E,[E,_,E1,H1|L]),LOpt),H1,mnt(EO,HO,followpath(E1,[E1,H1|L]),LOpt),H1) :- 177 E = [ExogAction|_], % An exogenous action was assumed, wait until added to current history H1 178 exog_action(ExogAction), !. 179trans(mnt(EO,HO,followpath(E,[E,H,E1,H1|L]),LOpt),H,mnt(EO,HO,followpath(E1,[E1,H1|L]),LOpt),H1) :- 180 \+ (E = [ExogAction|_], exog_action(ExogAction)), !. % Progress blindly if not an assumed exog action 181trans(mnt(EO,HO,EFollow,LOpt),H,ERecovered,HRecovered) :- 182 EFollow=followpath(Ex,[Ex,Hx|_]), % History is not what expected, recover 183 H\=Hx, % Replan only if the current situation is not the one expected 184 recover(EO,HO,LOpt,EFollow,H,ERecovered,HRecovered).
189recover(_EO,_HO,_LOpt,EFollow,H,followpath(Ex,ListRecovered),H) :- 190 EFollow=followpath(Ex,[Ex,Hx|L]), 191 append(H,HDropped,Hx), !, % The expected history has been chopped (progressed) 192 writeln('======> Surgery recovering plan.........'), 193 dropPrefixHistory([Ex,Hx|L],HDropped,ListRecovered). 194 195dropPrefixHistory([],_,[]). 196dropPrefixHistory([E,H|L],HDropped,followpath(E,[E,HNew|L2])) :- 197 append(HNew,HDropped,H), 198 dropPrefixHistory(L,HDropped,L2). 199 200 201recover(EO,HO,LOpt,_,H,EN,HN) :- 202 writeln('======> Full recovering......'), % Full re-planning is required 203 transstar(conc(EO,star(pi(a,[?(exog_action(a)),a]))),HO,conc(E1,_),H), % respect actions already done 204 trans(searchn(E1,LOpt),H,EN,HN). 205 206 207 208 209 210 211%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 212%% searchg(P,E) : search for E with replanning when P holds only 213%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 214final(searchg(_,E,_),H):- final(search(E),H). 215final(searchg(_,E),H) :- final(E,H). 216 217trans(searchg(P,E),H,followpathg(P,E1,L),H1) :- 218 catch( (trans(E,H,E1,H1), findpath(E1,H1,L)), search,fail). 219trans(searchg(P,E,M),H,E1,H1):- 220 report_message(program, ['Thinking linear plan on: ', M]), 221 (trans(searchg(P,E),H,E1,H1) -> 222 report_message(program, 'Finished thinking: Plan found!') 223 ; 224 report_message(program, 'Finished thinking: No plan found!'), 225 fail 226 ). 227 228% followpath(P,E,L): execute program E wrt expected sequence of 229% configurations L=[E,H,E1,H1,...] 230% if the current history does not match the next expected one 231% in L and re-planning condition P holds, then redo the search for E at H 232final(followpathg(_,E,[E,H]),H) :- !. 233final(followpathg(P,E,[E,_]),H) :- \+ isTrue(P,H), !. /* _\=H */ 234final(followpathg(_,E,_),H) :- final(E,H). /* off path; check again */ 235 236trans(followpathg(P,E,[E,H,E1,H1|L]),H,followpathg(P,E1,[E1,H1|L]),H1) :- !. 237trans(followpathg(P,E,_),H,EN,HN) :- 238 isTrue(P,H), !, /* HExp\= H and replanning cond P holds */ 239 writeln('we need to replan!'), 240 trans(searchg(P,E),H,EN,HN). 241trans(followpathg(P,E,[E,HExp,E1,H1|L]),H,followpathg(P,E1,[E1,HN|LN]),HN) :- 242 writeln('NO need to replan!'), 243 append(HNExp,HExp,H), /* HExp\= H and replanning cond P does not holds */ 244 repair_expected([E1,H1|L],HNExp,[E1,HN|LN]). /* H=HNExp+HExp */ 245 246% repair_expected(L,H,LN): L is a list of expected configurations 247% LN is the new list of expected configurations 248% where H is added at the front of each history in L 249repair_expected([],_,[]). 250repair_expected([E1,H1|L],HNExp,[E1,H11|LN]) :- 251 append(HNExp,H1,H11), 252 repair_expected(L,HNExp,LN). 253 254 255 256 257 258 259%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 260%% (D.2) CONDITIONAL SEARCH: Conditional plans with sensing 261%% 262%% From [Sardina LPAR-01] and based on sGolog [Lakemeyer 99] 263%% 264%% After a step, the program looks for special "marks" generated by the 265%% program when searched: 266%% 267%% branch(P): CPP should branch w.r.t. rel fluent P 268%% commit : no backtracking on the already found partial CPP 269%% sim(A) : A is a simulated exogenous action, don't add it to the CPP 270%% test(P) : a test ?(P) should be left in the CPP (from ??(P)) 271%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 272final(searchc(E,_),H):- final(searchc(E),H). 273final(searchc(E),H) :- final(E,H). 274 275trans(searchc(E,M),H,E1,H1):- 276 report_message(program, ['Thinking Conditional plan on: ', M]), 277 (trans(searchc(E),H,E1,H1) -> 278 report_message(program, 'Finished thinking: CPP found!') 279 ; 280 report_message(program, 'Finished thinking: No CPP found!'), 281 fail 282 ). 283 284% if calcCPP/3 wants to abort everything it has to throw exception searchc 285trans(searchc(E),S,CPP,S):- 286 catch(calcCPP(E,S,CPP), searchc, fail). 287 288trans(branch(P),S,[],[branch(P)|S]). /* branching step always succeeds */ 289 290calcCPP(E,S,[]) :- final(E,S). 291calcCPP([E1|E2],S,C) :- E2\=[], !, calcCPP(E1,S,C1), /* program is a sequence */ 292 extendCPP(E2,S,C1,C). 293 294%calcCPP(branch(P),S,[]) :- isTrue(know(P),S), !. /* no branching */ 295%calcCPP(branch(P),S,[if(P,[],[])]) :- isTrue(kwhether(P),S), !. /* branching */ 296calcCPP(branch(P),_,[if(P,[],[])]) :- !. /* branching, do not check */ 297 298calcCPP(E,S,C) :- trans(E,S,E1,S1), /* program is not a sequence */ 299 (S1=[branch(P)|S] -> calcCPP([branch(P)|E1],S,C) ; /* branch now wrt P*/ 300% S1=[commit|S] -> (calcCPP(E1,S,C) -> /* commit here */ 301% true 302% ; 303% throw(searchc)) ; /* abort if no plan found for E1 */ 304 S1=S -> calcCPP(E1,S1,C) ; /* normal test */ 305 S1=[test(P)|S] -> (calcCPP(E1,S,C1), C=[?(P)|C1]) ; /* perdurable test */ 306 S1=[A|S] -> (calcCPP(E1,S1,C1), C=[A|C1]) ). /* normal action */ 307 308/* extendCPP(E,S,C,C1) recursively descends the CAT C (first two clauses). */ 309/* Once a leaf of the CAT is reached (third clauses), "calcCPP" is called */ 310/* which then extends this branch accordingly to E */ 311extendCPP(E,S,[sim(A)|C],[sim(A)|C2]) :- exog_action(A), !, 312 extendCPP(E,[sim(A)|S],C,C2). 313extendCPP(E,S,[if(P,C1,C2)],[if(P,C3,C4)]) :- !, 314 assume(P,true,S,S1), extendCPP(E,S1,C1,C3), 315 assume(P,false,S,S2), extendCPP(E,S2,C2,C4). 316extendCPP(E,S,[commit|C],C2) :- !, (extendCPP(E,S,C,C2) ; throw(searchc)). 317extendCPP(E,S,[A|C],[A|C2]) :- prim_action(A), !, extendCPP(E,[A|S],C,C2). 318extendCPP(E,S,[],C) :- calcCPP(E,S,C). /* We are on a leaf of the CPP */ 319 320 321%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 322%% (D.3) CONDITIONAL PLANNER WSCP: conditional planner (Hector Levesque) 323%% 324%% Requires loading the library for WSCP 325%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 326:- ensure_loaded(wscplan). % Load the WSCP Planner 327 328% Transitions for the case(A,CondPlan) construct 329trans(case(A,[if(V,Plan)|_]),H,Plan,H):- sensed(A,V,H), !. 330trans(case(A,[if(_,_)|BL]),H,case(A,BL),H). 331 332% Transition for the planning construct achieve 333% G : the goal to achieve 334% Max : the maximum depth for the search 335% --- LOptions is the list of options: 336% - id(NameId) : planning name id 337% - simid(Id) : Id of the exog. simulator to be used (none = no simulator) 338% - mess(Mess) : description of the planning work to be done (to be printed) 339% - actions(LAct) : legal actions that may be used 340 341trans(achieve(G,Max,LOptions),H,E,H) :- 342 extract_option(LOptions,id,NameId,G), 343 extract_option(LOptions,mess,Mess,none), 344 (Mess\=none -> 345 report_message(program, ['Planning for: ', Mess]) 346 ; 347 true 348 ), 349 wscp(NameId,G,Max,H,E) -> % Do the actual planning! 350 Mess\=none, 351 report_message(program, ['Finished planning for ',Mess,' : Plan found!']) 352 ; 353 Mess\=none, 354 report_message(program, ['Finished planning for ',Mess,' : No plan found!']), 355 fail. 356 357 358 359%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 360%% (D.4) INTERRUPTABLE SEARCH (BETA VERSION) 361%% 362%% Developed first by Hector Levesque (2003) 363%% Fixed and improved by Sebastian Sardina (2003-2004) 364%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 365%% This is code to incrementally go through a search tree 366%% 367%% Tree is a list [node_k children_k-1 node_k-1 ... children_1 node_1] 368%% where a node is a pair (E,H), E is a program and H is a history 369%% and where children_k is a list of remaining children of node_k 370%% and where node_1 is the root of the tree */ 371%% 372%% Two predicates defined: 373%% - doneSearch(Tree) succeeds iff the search has found a full path 374%% - xtndSearch(Tree,Tree1) succeeds iff the search from Tree can 375%% progress one step to Tree1: either extend a leaf of Tree using 376%% Trans or pop the tree (as necessary) if the leaf goes nowhere 377%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 378fullSearch(T, T) :- doneSearch(T). 379fullSearch(T, T1) :- xtndSearch(T, T2), !, fullSearch(T2, T1). 380 381doneSearch([(E,H)|_]) :- final(E,H). 382 383% Progress the tree T one step (poping is not considered a step) 384xtndSearch(T,[First,Rest|T]) :- 385 T=[(E,H)|_], 386% store_node(xtnd, E, H), % For debugging 387 findall((E1,H1),trans(E,H,E1,H1),[First|Rest]). 388% setof((E1,H1),trans(E,H,E1,H1),[First|Rest]). 389xtndSearch([_,[],_,[]|T], T1) :- !, xtndSearch([backup,[]|T], T1). 390xtndSearch([_,[],_,[First|Rest]|T],T1) :- !, xtndSearch([First, Rest|T], T1). 391xtndSearch([_,[First|Rest]|T],T1) :- !, xtndSearch([First, Rest|T], T1). 392 393% Progress the tree T counting each pop as a step 394xtndSearch2(T,[First,Rest|T]) :- 395 T=[(E,H)|_], setof((E1,H1),trans(E,H,E1,H1),[First|Rest]). 396xtndSearch2([_,[],_,[]|T], [_,[]|T]):- !. 397xtndSearch2([_,[],_,[First|Rest]|T],[First, Rest|T]) :- !. 398xtndSearch2([_,[First|Rest]|T],[First, Rest|T]). 399 400xtnd(T, T, 0) :- !. 401xtnd(T, T1, N):- xtndSearch2(T, TT),!, N2 is N-1, xtnd(TT, T1, N2). 402 403/* With these two predicates, we can get a full search without */ 404/* any interruptions if desired by calling xtndSearch repeatedly */ 405findpath(E,H,Path,H2) :- 406% store_node(xtnd, E, H), % For debugging 407 fullSearch([(E,H)], T), !, 408 buildPath(T, PathR), 409 PathR=[(_,H2)|_], 410 reverse(PathR, Path). 411 412buildPath([C],[C]). 413buildPath([C,_|R], [C|RP]) :- buildPath(R, RP). 414 415 416%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 417%% (D.5) RATIONAL SEARCH (BETA VERSION) 418%% 419%% From [Sardina & Shapiro AAMAS-2003] 420%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 421%% Computes the "best" CPP for a program wrt a set of goals 422%% 423%% The rational search construct needs 424%% 425%% - E: a nondeterministic ConGolog program 426%% - SetGoals: set of pairs goals-rewards: [[G1,R1],...,[Gn,Rn]] 427%% - FluentAssum: set of possible assumptions [...,[fi,[v1,..,v2],...] 428%% this set identifies the set of possible worlds for 429%% which all solutions will be tested/evaluated 430%% - M: a message for the user when the search starts (optional) 431%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 432 433% Version with a message 434trans(searchr(E,SetGoals,FluentAssum,M),S,CPP,S):- 435 report_message(program, ['Thinking a rational plan on: ', M]), 436 (trans(searchr(E,SetGoals,FluentAssum),S,CPP,S) -> 437 report_message(program, 'Finished thinking: rational CPP found!') 438 ; 439 report_message(program, 'Finished thinking: No rat. CPP found!'), 440 fail 441 ). 442 443:- dynamic bestPlan/2. 444 445% trans/5 for rational search 446trans(searchr(E,SetGoals,FluentAssum),S,CPP,S):- 447 compute_possible_assumptions(FluentAssum, S, SetAssum), 448 retractall(bestPlan(_,_)), 449 catch(calcRationalCPP(E,S,SetGoals,SetAssum), searchr, bestPlan(CPP)), 450 (\+ var(CPP) ; bestPlan(CPP)). 451 452% Compute all CPPs, evaluate them, and store them in the database 453% CPP is computed in situation S in which there may be unknowns. 454% E itself has to be designed to deal with this unknowns (E JIT in S) 455calcRationalCPP(E,S,SetGoals,SetAssum) :- 456 calcCPP(E,S,CPP), 457 calc_vector_utility(CPP, S, SetAssum, SetGoals, LVectorU), 458 assert(bestPlan(CPP,LVectorU)), 459 fail. 460calcRationalCPP(_,_,_,_). 461 462bestPlan(CPP) :- 463 bestPlan(CPP,EvalCPP), 464 \+ (bestPlan(CPP2, EvalCPP2), 465 CPP2 \= CPP, 466 member([N,[Min1,_]], EvalCPP), 467 member([N,[_,Max2]], EvalCPP2), 468 Min1<Max2 469 ). 470 471%trans(searchr(mainControl(0), [[safeOpen=true,10],[neg(exploded),5]],[[combNum0,[true,false]]]),[],E,S). 472 473%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 474% CODE FOR EVALUATING PLANS WRT A SET OF GOALS 475%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 476 477% calc_vector_utility(+CPP, +H, +SetAssumptions, +SetGoal, -LVectorU) 478% Computes the vector of utilities of a CPP at H wrt the SetGoals 479% LVectorU = [ [MI1,MA1],[MI2,MA2],....,[MIN,MAN] ] 480% where MIk = minimum utility of CPP with assumptions k 481% where MAk = maximum utility of CPP with assumptions k 482% SetAssumptions is a list of pairs [Id, History] 483calc_vector_utility(CPP, H, SetAssumptions, SetGoals, LVectorU) :- 484 findall([Id,U],(member([Id,H2],SetAssumptions), 485 append(H2,H,H3), 486 evaluate_CPP(CPP,H3,SetGoals,U)), LU), 487 maplist(get_min_max,LU,LVectorU). 488 489% Obtains the pair minimum-maximum of a list L of numbers 490get_min_max([Id,L],[Id,[Min,Max]]) :- min(L, Min), max(L, Max). 491 492% compute_possible_assumptions(+FluentAssum, +H, -SetAssumptions) 493% FluentAssum is a list of pairs [Fluent, [v1,v2,...,vn]] where 494% v1,..,vn are the possible assumptions for Fluent 495% H is the current history 496% SetAssumptions are all the possible assumptions that are consistent at H 497compute_possible_assumptions(FluentAssum, H, SetAssumptions) :- 498 findall(HA, multiple_assumptions(FluentAssum, H, HA), LHA), 499 identify_list(LHA, 1, SetAssumptions). 500 501% identify_list(L,N,IL) 502% If L = [e1,e2,e3,...,en], then IL=[ [N,e1], [N+1,e2], ..., [N+n,en] ] 503identify_list([], _, []). 504identify_list([A|RA], N, [[N,A]|IRA]) :- 505 N2 is N+1, 506 identify_list(RA, N2, IRA). 507 508% multiple_assumptions(+LAssum, +H, H2) : 509% H2 is a consistent combination of assumptions at H from LAssum 510multiple_assumptions([], _, []). 511multiple_assumptions([[F,PV]|R], H, HA) :- % F has no value on H 512 holds(neg(know(F)), H), !, 513 multiple_assumptions(R, H, HR), 514 member(X, PV), 515 assume(F,X,HR,HA). 516multiple_assumptions([[_,_]|R], H, HA) :- % F has a value in H, do not assume 517 multiple_assumptions(R, H, HA). 518 519 520% Evaluate a CPP in a particular history H wrt goals-value SG 521% LUtilities is a list of utilities that the CPP may collect 522evaluate_CPP(CPP, H, SG, LUtilities) :- 523 findall(U, (extract_trace(CPP, H, H2), 524 append(H2, H, H3), 525 evaluate_trace(H3, SG, U)), LUtilities). 526 527 528% Evaluate history H wrt the set of pairs Goal-Value 529evaluate_trace(_, [], 0) :- !. 530evaluate_trace(H, [[Goal,Value]|RG], Utility) :- 531 evaluate_trace(H,RG,UtilityRG), 532 (isTrue(Goal,H) -> 533 Utility is UtilityRG + Value 534 ; 535 Utility is UtilityRG 536 ). 537 538 539% extract_trace(E,H,H2) : H2 is the execution trace of E starting in H 540% (E is known to be executable at H) 541extract_trace([],_,[]). 542extract_trace([if(P,E1,E2)],H,H2) :- 543 isTrue(P=Y,H), !, 544 A = _SingletonInBranches, 545 (Y=true -> extract_trace(E1,[A|H], H2) ; extract_trace(E2,[A|H], H2)). 546extract_trace([if(P,E1,_)],H,HR) :- 547 assume(P,true,H,H2), 548 extract_trace(E1,H2, H3), 549 assume(P,true,[],H4), 550 append(H3,H4,HR). 551extract_trace([if(P,_,E2)],H,HR) :- !, 552 assume(P,false,H,H2), 553 extract_trace(E2,H2, H3), 554 assume(P,false,[],H4), 555 append(H3,H4,HR). 556extract_trace([A|E],H,H2) :- % It is an action followed by a CPP 557 A\=[], 558 extract_trace(E,[A|H], HE), 559 append(HE,[A],H2). 560 561 562 563 564 565%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 566% EOF: Interpreters/transfinal-search.pl 567%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%