/*  WARPLAN.PL  */


/*
SPECIFICATION
-------------

This is David Warren's Warplan program, which I use in PLANNING_BUG.PL.
It exports the predicate
    plan( GoalState+, T+, StartState+, Plan- ):
where
    GoalState is a conjunction of goals, expressed in the form
        Goal1&Goal2&...;
    T is an already generated partial plan. I think this is only
    relevant when 'plan' calls itself; you should pass the atom
    'true' for T;
    StartState represents a conjunction of goals, already achieved by T,
    which must not be undone. StartState should be an atom. Your start
    state should be written as clauses for given/2, where the first
    argument of each clause-head is the same atom, and the second
    argument is one goal. See below for more details;
    Plan is the plan.

For an example of the input to Warplan, see the end of this file.
The call used there would be
    ?- plan( on(a,b)&on(b,c), true, start, Plan )
where we have the clauses
    given( start, on(a,floor) ).
    given( start, on(b,floor) ).
    given( start, on(c,a) ).
    given( start, clear(b) ).
    given( start, clear(c) ).
There are other examples in "Prolog by Example". I will add the other
details of this book if I remember; it's the Springer 1988 bumper book
of Prolog programs, possibly by Coelho, Cotta and Pereira.

You also need to supply specifications of each action. Give these by
the predicates below, whose description I take from "Prolog by
Example":
    add(X,U):   fact X is added by action U; i.e. X is true in any
                state resulting from U (and U is a possible action
                in some state in which X is not true). This
                corresponds to a STRIPS add-list.
    del(X,U):   fact X is deleted by action U; i.e. it is not the
                case that X is preserved by U. (X is preserved by
                U if and only if X is not added by U and X is true
                in a state resulting from U whenever X is true in the
                preceding state). This corresponds to a STRIPS
                delete-list.
    can(U,C):   the conjunction of facts C is the precondition of
                action U; i.e. U is possible in any state in which
                C is true. This corresponds to a STRIPS precondition.
    always(X):  fact X is true in any state.
    imposs(x):  the conjunction of facts X is impossible in any
                state.
    given(T,X): fact X is true in the initial state T (but it is not
                the case that X is true in all state). This is how
                you specify the start state.

The plan uses the operator : to compose actions. For example, the
plan produced by PopBeast in reply to 'grab the food' is this
    start : go([0, 0], [-1, 2]) : grab(food(1), [-1, 2])

Note: Warplan can easily get into infinite loops, and its success can
depend on the ordering of the goals and the clauses of the predicates
above.

The principles of Warplan are also described in "Two Case Studies" by
Kluzniak and Szapowicz, in "Readings in Planning" ed ?,? and Tate,
Morgan-Kauffman 19??.
*/


/*
IMPLEMENTATION
--------------

The code below is exactly as supplied by David Warren. I would welcome
a stronger planner if anyone has one. (This is not criticism of Warren -
remember that Warplan dates from 1974 or so.)

One possibility would be the A* and abstraction-based planner in "AI in
Practice" by Allan Ramsay and Rosalind Barrett, Ellis-Horwood 1987. I
think this is essentially the same as the planner used in the Pop-11
MSBLOCKS program. However, I need it in Prolog, and haven't yet had time
to attempt a translation. Also, because this planner is
abstraction-based, you have to attach priority values to each
precondition, and it would be hard to make PopBeast generate these for
itself. (Intuitively, I quite like the idea of planning via plan
homomorphisms, which I think is what abstraction-based planning is: it
ought to be mathematically elegant.)
*/


:- op(150,xfy,&).
:- op(200,yfx,:).


plans(C,_) :-
    unless(consistent(C,true)),
    !,
    nl, write('impossible'), nl.

plans(C,T) :-
%    cputime(M0),
    plan(C,true,T,T1),
%    cputime(M1),
    nl, output(T1), nl.
%    Time is (M1-M0)/1000, write(Time), write(' secs.'), nl.


cputime(T) :-
    statistics(runtime,[T,_]).


output(T:U) :-
    !,
    output1(T), write(U), write('.'), nl.

output(T) :-
    write(T), write('.'), nl.


output1(T:U) :-
    !,
    output1(T), write(U), write(';'), nl.

output1(T) :-
    write(T), write(';'), nl.


plan(X&C,P,T,T2) :-
    !,
    solve(X,P,T,P1,T1),
    plan(C,P1,T1,T2).

plan(X,P,T,T1) :-
    solve(X,P,T,_,T1).


solve(X,P,T,P,T) :-
    always(X).

solve(X,P,T,P1,T) :-
    holds(X,T),
    and(X,P,P1).

solve(X,P,T,X&P,T1) :-
    add(X,U),
    achieve(X,U,P,T,T1).


achieve(_,U,P,T,T1:U ) :-
   preserves(U,P),
   can(U,C),
   consistent(C,P),
   plan(C,P,T,T1),
   preserves(U,P).

achieve(X,U,P,T:V,T1:V) :-
   preserved(X,V),
   retrace(P,V,P1),
   achieve(X,U,P1,T,T1),
   preserved(X,V).


holds(X,_:V) :-
    add(X,V).

holds(X,T:V) :-
    !,
   preserved(X,V),
   holds(X,T),
   preserved(X,V).

holds(X,T) :-
    given(T,X).


preserved(X,V) :-
    mkground(X&V,0,_),
    del(X,V),
    !, fail.

preserved(_,_).


preserves(U,X&C) :-
    preserved(X,U),
    preserves(U,C).

preserves(_,true).


retrace(P,V,P2) :-
   can(V,C),
   retrace1(P,V,C,P1),
   conjoin(C,P1,P2).


retrace1(X&P,V,C,P1) :-
    add(Y,V),
    equiv(X,Y),
    !,
    retrace1(P,V,C,P1).

retrace1(X&P,V,C,P1) :-
    elem(Y,C),
    equiv(X,Y),
    !,
    retrace1(P,V,C,P1).

retrace1(X&P,V,C,X&P1) :-
    retrace1(P,V,C,P1).

retrace1(true,_,_,true).


consistent(C,P) :-
   mkground(C&P,0,_),
   imposs(S),
   unless(unless(intersect(C,S))),
   implied(S,C&P),
   !, fail.

consistent(_,_).



and(X,P,P) :-
    elem(Y,P),
    equiv(X,Y),
    !.

and(X,P,X&P).


conjoin(X&C,P,X&P1) :-
    !,
    conjoin(C,P,P1).

conjoin(X,P,X&P).


elem(X,Y&_) :-
    elem(X,Y).

elem(X,_&C) :-
    !,
    elem(X,C).

elem(X,X).


intersect(S1,S2) :- elem(X,S1), elem(X,S2).


implied(S1&S2,C) :-
    !,
    implied(S1,C),
    implied(S2,C).

implied(X,C) :-
    elem(X,C).

implied(X,_) :-
    always(X).    % CHANGE


notequal(X,Y) :-
   unless(X=Y),
   unless(X=qqq(_)),
   unless(Y=qqq(_)).


equiv(X,Y) :-
    unless(nonequiv(X,Y)).


nonequiv(X,Y) :-
    mkground(X&Y,0,_),
    X=Y,
    !, fail.

nonequiv(_,_).


mkground(qqq(N1),N1,N2) :-
    !,
    N2 is N1+1.

mkground(qqq(_),N1,N1) :- !.

mkground(X,N1,N2) :-
    X =.. [_|L],
    mkgroundlist(L,N1,N2).


mkgroundlist([X|L],N1,N3) :-
    mkground(X,N1,N2),
    mkgroundlist(L,N2,N3).

mkgroundlist([],N1,N1).


unless(X) :-
    X, !, fail.

unless(_).


/*
Sample input to Warplan
-----------------------


% Blocks World

test :- plans( on(a,b) & on(b,c), start).

imposs( on(X,Y) & clear(Y) ).
imposs( on(X,Y) & on(X,Z) & notequal(Y,Z) ).
imposs( on(X,X) ).

add( on(U,W),       move(U,V,W) ).
add( clear(V),      move(U,V,W) ).

del( on(U,Z),       move(U,V,W) ).
del( clear(W),      move(U,V,W) ).

can( move(U,V,floor),   on(U,V) & notequal(V,floor) & clear(U) ).
can( move(U,V,W),   clear(W) & on(U,V) & notequal(U,W) & clear(U) ).

always( notequal(X,Y) ) :- notequal(X,Y).

given( start, on(a,floor) ).
given( start, on(b,floor) ).
given( start, on(c,a) ).
given( start, clear(b) ).
given( start, clear(c) ).
*/
