1% A SIMPLE REGRESSION PLANNER FOR ACTIONS IN STRIPS NOTATION 2 3% solve(G,NS,P) is true if P is a plan to solve goal G that uses 4% less than NS steps. G is a list of atomic subgoals. 5 6solve(G,_,init) <- 7 solved(G). 8 9solve(G,NAs,do(A,Pl)) <- 10 NAs > 0 & 11 useful(G,A) & 12 wp(G,A,G1) & 13 NA1 is NAs-1 & 14 solve(G1,NA1,Pl). 15 16% solved(G) is true if goal list G is true initially 17solved([]). 18solved([G|R]) <- 19 holds(G,init) & 20 solved(R). 21 22% useful(G,A) is true if action A is useful to solve a goal in goal list G 23%useful([S|R],A) <- 24% holds(S,init) & 25% useful(R,A). 26useful([S|R],A) <- 27% ~ holds(S,init) & 28 useful(R,A). 29useful([S|_],A) <- 30 achieves(A,S). 31 32% wp(G,A,G0) is true if G0 is the weakest precondition that needs to hold 33% immediately before action A to ensure that G is true immediately after A 34wp([],A,G1) <- 35 preconditions(A,G) & 36 filter_derived(G,[],G1). 37wp([S|R],A,G1) <- 38 wp(R,A,G0) & 39 regress(S,A,G0,G1). 40 41% regress(Cond,Act,SG0,SG1) is true if regressing Cond through Act 42% starting with subgoals SG0 produces subgoals SG1 43regress(S,A,G,G) <- 44 achieves(A,S). 45regress(S,A,G,G1) <- 46 primitive(S) & 47 ~ achieves(A,S) & 48 ~ deletes(A,S) & 49 insert(S,G,G1). 50 51filter_derived([],L,L). 52filter_derived([G|R],L,[G|L1]) <- 53 primitive(G) & 54 filter_derived(R,L,L1). 55filter_derived([A \= B | R],L,L1) <- 56 A \= B & 57 filter_derived(R,L,L1). 58filter_derived([G|R],L0,L2) <- 59 clause(G, B) & 60 filter_derived(R,L0,L1) & 61 filter_derived(B,L1,L2). 62 63regress_all([],_,G,G). 64regress_all([S|R],A,G0,G2) <- 65 regress(S,A,G0,G1) & 66 regress_all(R,A,G1,G2). 67 68% ============================================================================= 69 70% member(X,L) is true if X is a member of list L 71member(X,[X|_]). 72member(X,[_|L]) <- 73 member(X,L). 74 75% subset(L1,L2) is true if L1 is a subset of list L2 76subset([],_). 77subset([A|B],L) <- 78 member(A,L) & 79 subset(B,L). 80 81% insert(E,L0,L1) inserts E into list L0 producing list L1. 82% If E is already a member it is not added. 83insert(A,[],[A]). 84insert(A,[A|L],[A|L]). 85insert(A,[B|L],[B|R]) <- 86 A \= B & 87 insert(A,L,R). 88 89% ============================================================================= 90 91% TRY THE FOLLOWING QUERIES with delrob_strips.pl: 92% ask solve([carrying(rob,k1)],5,P). 93% ask solve([sitting_at(k1,lab2)],8,P). 94% ask solve([carrying(rob,parcel),sitting_at(rob,lab2)],10,P). 95% ask solve([sitting_at(rob,lab2),carrying(rob,parcel)],10,P).