Case Study: Planning Courses of Action - Thinking as Computation - page 195

Figure 9.13. A staged planner in Prolog

splan.pl

% This staged planner needs the predicates below to be defined:
% - legal_move(BeforeState,Move,AfterState)
% - initial_state(State)
% - stages(ListofStages)
% - goal_stage(Stage,State)
% plan(L): L is a list of moves through a list of goal stages.
plan(L) :- initial_state(I), stages([G|GL]), plan_all(G,I,L,GL).
% plan_all(G,S,L,GL): L passes from G through each stage in GL.
plan_all(_,_,[],[]).
plan_all(G1,S1,L,[G2|GL]) :-
append(L1,L2,L), reach(G1,S1,L1,G2,S2), plan_all(G2,S2,L2,GL).
% reach(G1,S1,L,G2,S2): L moves from S1 in stage G1 to S2 in G2.
reach(_,S,[],G2,S) :- goal_stage(G2,S). % S attains stage G2.
reach(G1,S1,[M|L],G2,S3) :- % Move from S1 to S2.
legal_move(S1,M,S2), goal_stage(G1,S2), reach(G1,S2,L,G2,S3).

stages that the planner must pass through, and goal_stage( g , s ) , which holds when
the stage named g applies to state s . The 15-puzzle might include these clauses:
stages([init,r1,r1c1,r12c12,goal]).
goal_stage(init,_).
goal_stage(r1,[1,2,3,4|_]).
goal_stage(r1c1,[1,2,3,4,5,_,_,_,9,_,_,_,13,_,_,_]).
goal_stage(r12c12,[1,2,3,4,5,6,7,8,9,10,_,_,13,14,_,_]).
goal_stage(goal,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]).

The way the planner works is to (use append to) break the sequence of moves into
parts that will proceed from stage to stage until all the stages have been attained and
the problem is solved. Whenever it considers a legal move (within the reach predi-
cate), it checks that the current stage applies to the state that results from doing the
move. This automatically guarantees that the moves within a stage will not compro-
mise a subgoal that was previously achieved. (This was handled manually using the
acceptable predicate.)

9.3.2 Best-first search

∗

Once it has been determined that the best one can do is to search for a path from
some start state to an end state, there are other ways of searching that can be much
more effective than those used so far. One obvious thing to do is to avoid loops that