====== State-space ======
{{tag>planning}}
===== Description =====
A state-space definition for means-ends planning based on goal regression.

**Source**:  PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
===== Download =====
Program source code: {{state-space.pl}}
===== Listing =====
<code prolog>
% Figure 17.9  A state-space definition for means-ends planning based on goal
% regression. Relations satisfied, achieves, preserves, regress, addnew and
% delete_all are as defined in Figure 17.8.


% State space representation of means-ends planning with goal regression
:- op( 300, xfy, ->).

s( Goals -> NextAction, NewGoals -> Action, 1)  :-   % All costs are 1
  member( Goal, Goals),
  achieves( Action, Goal),
  can( Action, Condition),
  preserves( Action, Goals),
  regress( Goals, Action, NewGoals).

goal( Goals -> Action) :-
  start( State),                    % User-defined initial situation
  satisfied( State, Goals).         % Goals true in initial situation

h( Goals -> Action, H)  :-                   % Heuristic estimate
  start( State),
  delete_all( Goals, State, Unsatisfied),    % Unsatisfied goals
  length( Unsatisfied, H).                   % Number of unsatisfied goals

</code>
===== Comments =====