%======================================================================
% MODULE: planner-ME-GR.p
%
% A simple means-ends planner with goal regression.
% 
% See Figure 16.8, p. 417 of
% "Prolog Programming for Artificial Intelligence", 2d Edition
%                        - by Ivan Bratko
%======================================================================

%----------------------------------------------------------------------
% plan( InitialState, Goals, Plan)
%----------------------------------------------------------------------

plan( State, Goals, []) :-
        satisfied( State, Goals).          % Goals true in State

plan( State, Goals, Plan) :-
        append( PrePlan, [Action], Plan), % Divide plan (breadth-1st)
        select( State, Goals, Goal),    % Select a goal
        achieves( Action, Goal),
        can( Action, Condition),        % Ensure Action contains no variables
        preserves( Action, Goals),      % Protect Goals
        regress( Goals, Action, RegressedGoals), % Regress Goals through Action
        plan( State, RegressedGoals, PrePlan).

satisfied( State, Goals) :-
        subtract( Goals, State, []).      % All Goals in State

select( State, Goals, Goal) :-          % Select Goal from Goals
        member( Goal, Goals).           % A simple selection principle

achieves( Action, Goal) :-
        add( Action, Goals),
        member( Goal, Goals).

preserves( Action, Goals) :-            % Action does not destroy Goals
        del( Action, Relations),
        not(( member( Goal, Relations), member( Goal, Goals) )).

regress( Goals, Action, RegressedGoals) :-       % Regress Goals through Action
        add( Action, NewRelations),
        subtract( Goals, NewRelations, RestGoals),
        can( Action, Condition),
        addnew( Condition, RestGoals, RegressedGoals). % Add precondition,
                                                       %  check impossibility

%----------------------------------------------------------------------
% addnew( NewGoals, OldGoals, AllGoals):
%   AllGoals is the union of NewGoals and OldGoals
%   NewGoals and OldGoals must be compatible
%----------------------------------------------------------------------

addnew( [], L, L).

addnew( [Goal | _], Goals, _) :-
        impossible( Goal, Goals),                % Goal incompatible with Goals
        !,
        fail.                                    % Cannot be added

addnew( [X | L1], L2, L3) :-
        member( X, L2),
        !,
        addnew( L1, L2, L3).                     % Ignore duplicate

addnew( [X | L1], L2, [X | L3]) :-
        addnew( L1, L2, L3).