title: Prolog STRIPS planner never completes
body: <p>Following examples by Ivan Bratko on Artificial Intelligence in Prolog through his book:</p>
  
  <p><em>"Prolog Programming for Artificial Intelligence - 3rd Edition"</em> (ISBN-13: 978-0201403756) (1st edition 1986 by Addison-Wesley, ISBN 0-201-14224-4)</p>
  
  <p>I've noticed that a lot of the examples do not run to completion but instead seem to get stuck. I have tried several different implementations following it to the letter, but with no luck. Would anyone be willing to take a gander at the code to see if they can spot where there is faulty logic or if I made a mistake?</p>
  
  <p>This is the complete program of a <a href="https://en.wikipedia.org/wiki/STRIPS" rel="nofollow noreferrer">STRIPS style planner</a> for a blocks world as illustrated in the book: </p>
  
  <pre><code>%   This planner searches in iterative-deepening style.
  %   A means-ends planner with goal regression
  
  %   plan( State, Goals, Plan)
  plan( State, Goals, [])  :-
    satisfied( State, Goals).                   % Goals true in State
  
  plan( State, Goals, Plan)  :-
    append( PrePlan, [Action], Plan),           % Divide plan achieving breadth-first effect
    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)  :-
    delete_all( Goals, State, []).              % All Goals in State
  
  select( State, Goals, Goal)  :-               % Select Goal from Goals
    member( Goal, Goals).                       % A simple selection principle
  
  achieves( Action, Goal)  :-
    adds( Action, Goals),
    member( Goal, Goals).
  
  preserves( Action, Goals)  :-                 % Action does not destroy Goals
    deletes( Action, Relations),
    not((member( Goal, Relations),
         member( Goal, Goals))).
  
  regress( Goals, Action, RegressedGoals)  :-       % Regress Goals through Action
    adds( Action, NewRelations),
    delete_all( Goals, NewRelations, RestGoals),
    can( Action, Condition),
    addnew( Condition, RestGoals, RegressedGoals).  % Add precond., check imposs.
  
  % addnew( NewGoals, OldGoals, AllGoals):
  %   OldGoals 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),  !,               % Ignore duplicate
    addnew( L1, L2, L3).
  
  addnew( [X | L1], L2, [X | L3])  :-
    addnew( L1, L2, L3).
  
  % delete_all( L1, L2, Diff): Diff is set-difference of lists L1 and L2
  
  delete_all( [], _, []).
  
  delete_all( [X | L1], L2, Diff)  :-
    member( X, L2), !,
    delete_all( L1, L2, Diff).
  
  delete_all( [X | L1], L2, [X | Diff])  :-
    delete_all( L1, L2, Diff).
  
  can( move( Block, From, To), [clear(Block), clear(To), on(Block,From)]) :-
    block(Block),
    object(To),
    To \== Block,
    object( From),
    From \== To,
    Block \== From.
  
  adds( move(X,From,To),[on(X,To),clear(From)]).
  
  deletes( move(X,From,To),[on(X,From), clear(To)]).
  
  object(X) :-
      place(X)
      ;
      block(X).
  
  impossible( on(X,X), _).
  
  impossible( on( X,Y), Goals) :-
      member( clear(Y), Goals)
      ;
      member( on(X,Y1), Goals), Y1 \== Y % Block cannot be in two places
      ;
      member( on( X1, Y), Goals), X1 \== X. % Two blocks cannot be in same place
  
  impossible( clear( X), Goals) :-
      member( on(_,X), Goals).
  
  block(a).
  block(b).
  block(c).
  block(d).
  block(e).
  block(f).
  block(g).
  
  place(1).
  place(2).
  place(3).
  place(4).
  </code></pre>
  
  <p>I added 7 blocks and 4 locations and tested it with a representation where all the blocks are alphabetically stacked from a through g on position 1, and the goal is to stack them in the same order on position 2.</p>
  
  <p>To run the program call <code>plan(StartState,GoalState, Sol).</code></p>
  
  <pre><code>plan([on(a,1), on(b,a), on(c,b), on(d,c), on(e,d), on(f,e), on(g,f), 
        clear(g), clear(2), clear(3)],
       [clear(1), on(a,2), on(b,a), on(c,b), on(d,c), on(e,d), on(f,e),
        on(g,f), clear(g), clear(3)],
        P).
  
  
  
  ~                  ~
  g                  g 
  f                  f
  e                  e
  d          ---&gt;    d
  c                  c
  b                  b
  a  ~  ~  ~      ~  a  ~  ~
  _  _  _  _      _  _  _  _
  1  2  3  4      1  2  3  4
  </code></pre>
  
  <p>References: </p>
  
  <ul>
  <li>Definition of move: <a href="http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_2.txt" rel="nofollow noreferrer">http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_2.txt</a></li>
  <li>End means planner with goal regression: <a href="http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_8.txt" rel="nofollow noreferrer">http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_8.txt</a></li>
  </ul>
  
  <p>Any advice would be greatly appreciated.</p>