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).