Prolog条计划器永远不会完成

Question

以下是Ivan Bratko在Prolog一书中关于人工智能的例子：

“人工智能的Prolog编程-第3版”( ISBN -13: 978-0201403756) (艾迪生-韦斯利，ISBN 0-201-14224-4,1986年第一版)

我注意到很多例子并没有完成，而是似乎被卡住了。我已经尝试了几种不同的实现，但没有成功。是否有人愿意对代码进行深入研究，看看他们是否能识别出哪里有错误的逻辑，或者我是否犯了错误？

这是块世界的条形平面机的完整程序，如书中所示：

%   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).

我添加了7个块和4个位置，并测试了它的表示法，其中所有的块都是从位置1的直通式g中按字母顺序堆放的，目标是在位置2上按相同的顺序堆叠它们。

要运行程序调用plan(StartState,GoalState, Sol).

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          --->    d
c                  c
b                  b
a  ~  ~  ~      ~  a  ~  ~
_  _  _  _      _  _  _  _
1  2  3  4      1  2  3  4

参考文献：

• 移动的定义：2.txt
• 目标回归的最终平均计划者：8.txt

如有任何建议，将不胜感激。

Answer 1

最后，代码是正确的，但组合爆炸杀死了它。

数据：

• 在9‘55次调用plan/3之后，3个位置，3个街区成功，5次移动。
• 4个位置，3个街区成功，在98'304调用plan/3后5次移动。
• 在915'703次调用plan/3之后，3个位置，4个街区成功，7次移动。
• 3个位置，5个街区成功，在97'288'255次调用plan/3后9次移动。

尝试更多是没有意义的，尤其是4个地方，7个街区。显然，启发式，对称性的开发等是需要进一步的。所有这些都需要更大的内存。在这里，使用的内存在所有情况下都是很小的:在迭代深化(并存储在堆栈上)搜索树上只有一条路径在任何时候都是活动的。我们不记得访问过的任何一个州，这是一个非常简单的搜索。

在更新代码下面(长337行)

更改(在代码中标记为“FIX”的重要更改)

• 在可能的情况下，已经使用了library(list)谓词，从而消除了一些代码。
• 使用format/2添加调试输出生成。
• 断言(请参阅这里)使用添加的assertion/1检查发生了什么，我认为会发生什么。
• 谓词和变量重命名，以更好地反映它们的预期意义。
• 添加了run/0谓词，它初始化状态和目标，调用plan/3并打印计划。
• can/2混淆了两个不同的方面:实例化一个动作和确定它的先决条件。分为两个谓词instantiate_action/1和preconditions/2。
• select_goal/2看起来像依赖于国家，但实际上并非如此，清理干净。

注意使这成为一个“迭代深化”搜索的诀窍。它非常聪明，但是从另一个角度来看，它太聪明了一半，因为它基于谓词run/3，当被调用为一个无绑定变量时，它的行为与计划是一个绑定变量时不同。第一种情况只发生在隐含搜索树的最顶层节点上。这一点可能会在教科书中得到进一步的解释，而我还没有，并且花了一些时间才意识到这段代码中到底发生了什么。

如果我在((nonvar(Plan), Plan == []) -> fail ; true )搜索分支开始时添加的剪枝表达式plan/3令人恼火，那么迭代深化技巧也应该如此。IMHO，最好使用树深度计数器并通过累加器返回计划。特别是如果有人将负责在生产系统(即“生产中的系统”，而不是“基于前向链接规则的系统”)中维护这样的代码。

% Based on
%
% Exercise 17.5 on page 429 of "Prolog Programming for Artificial Intelligence"
% by Ivan Bratko, 3rd edition
%
% The text says:
%
% "This planner searches through the state space in iterative-deepening style."
%
% See also:
%
% https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search
% https://en.wikipedia.org/wiki/Blocks_world
%
% The "iterative deepening" trick is all in the "Plan" list structure.
% If you remove it, the search becomes depth-first and no longer terminates!


% ----------
% Encapsulator to be called by user from the toplevel
% ----------

run :- 
   % Setting up
   start_state(State),
   final_state(Goals),
   % TODO: Build predicates that verify that State and Goal are actually validly constructed
   % Or choose better representations
   nb_setval(glob_plancalls,0), % global variable for counting calls (non-backtrackable)
   b_setval(glob_depth,0), % global variable for counting depth (backtrable)
   % plan/3 is backtrackable and generates different/successively longer plans on backtrack
   % it may however generate the same plan several times
   plan(State, Goals, Plan), 
   dump_plan(Plan,1).

% ----------
% Writing out a solution found
% ----------

dump_plan([P|R],N) :-
   % TODO: Verify that the plan indeed works!
   format('Plan step ~w: ~w~n',[N,P]),
   NN is N+1,
   dump_plan(R,NN).

dump_plan([],_).

% The representation of the blocks world (see below) is a bit unfortunate as places and blocks
% have to be declared separately and relationships between places and blocks, as well
% as among blocks themselves have to declared explicitely and consistently. 
% Additionally we have to specify which elements have a view of the sky (i.e. are clear/1)
% On the other hand, the final state and end state need not be specified fully, which is
% interesting (not sure what that means exactly regarding solution finding)
% The atoms used in describing places and blocks must be distinct due to program construction!

start_state([on(a,1), on(b,a), on(c,b), clear(c), clear(2), clear(3), clear(4)]).
final_state([on(a,2), on(b,a), on(c,b), clear(c), clear(1), clear(3), clear(4)]).

% ----------
% Representation of the blocks world
% ----------

% We have BLOCKs identified by atoms a,b,c, ...
% Each of those is identified by block/1 attribute.
% A block/1 is clear/1 if there is nothing on top of it.
% A block/1 is on(Block, Object) where Object is a block/1 or place/1.

block(a).
block(b).
block(c).

% We have PLACEs (i.e. columns of blocks) onto which to stack blocks.
% Each of these is identified by place/1 attribute.
% A place/1 can be clear/1 if there is nothing on top of it.
% (In fact these are like special immutable blocks and should be modeled as such)

place(1).
place(2).
place(3).
place(4).

% OBJECTs are place/1 or block/1.

object(X) :- place(X) ; block(X).

% ACTIONs are terms "move( Block, From, To)".
% "Block" must be block/1.
% "From" must be object/1 (i.e. block/1 or place/1).
% "To" must be object/1 (i.e. block/1 or place/1).
% Evidently constraints exist for a move/3 to be possible from or to any given state.

% STATEs are sets (implemented by lists) of "goal" terms.
% A goal term is "on( X, Y)" or "clear(Y)" where Y is object/1 and X is block/1.

% ----------
% plan( +State, +Goals, -Plan)
% Build a "Plan" get from "State" to "Goals".
% "State" and "Goals" are sets (implemented as lists) of goal terms.
% "Plan" is a list of action terms.
% The implementation works "backwards" from the "Goals" goal term list towards the "State" goal term list.
% ----------

% ___ Satisfaction branch ____ 

% This can only succeed if we are at the "end" of a Plan (the Plan must match '[]') and State matches Goal.

plan( State, Goals, []) :-

  % Debugging output
  nb_getval(glob_plancalls,P), 
  b_getval(glob_depth,D), 
  NP is P+1, 
  ND is D+1, 
  nb_setval(glob_plancalls,NP), 
  b_setval(glob_depth,ND),
  statistics(stack,STACK),
  format('plan/3 call ~w at depth ~d (stack ~d)~n',[NP,ND,STACK]),

  % If the Goals statisfy State, print and succeed, otherwise print and fail
  ( satisfied( State, Goals) -> 
     (sort(Goals,Goals_s),
      sort(State,State_s),
      format('   Goals: ~w~n', [Goals_s]),
      format('   State: ~w~n', [State_s]),
      format('   *** SATISFIED ***~n'))
     ;
      format('   --- NOT SATISFIED ---~n'),
      fail).

% ____ Search branch ____
%
% Magic which generates the breath-first iterative deepening search:
%
% In the top node of the call tree (the node directly underneath "run"), "Plan" is unbound.
%
%    At point "XXX" "Plan" is set to a list of as-yet-unbound actions of a given length.
%    At each backtrack that reaches up to "XXX", "Plan" is bound to list longer by 1.
%
% In any other node of the call tree than the top node, "Plan" is bound to a list of fixed length
% becoming shorter by 1 on each recursive call.
%
% The length of that list determines how deep the search through the state space *must* go because 
% satisfaction can only be happen if the "Plan" list is equal to [] and State matches Goal.
%
% So: 
% On first activation of the top, build plans of length 0 (only possible if Goals passes satisfied/2 directly)
% On second activation of the top, build plans of length 1 (and backtrack over all possibilities of length 1)
% ...
% On Nth activation of the top, build plans of length N-1 (and backtrack over all possibilities of length N-1)
%
% A slight improvement is to fail the search branch immediately if Plan is a nonvar and is equal to []
% because append( PrePlan, [Action], Plan) will fail...

plan( State, Goals, Plan)  :-

  % The line below can be commented out w/o ill effects, it is just there to fail early
  ((nonvar(Plan), Plan == []) -> fail ; true ),

  % Debugging output
  nb_getval(glob_plancalls,P), 
  b_getval(glob_depth,D), 
  NP is P+1, 
  ND is D+1, 
  nb_setval(glob_plancalls,NP), 
  b_setval(glob_depth,ND),
  statistics(stack,STACK),
  format('plan/3 call ~w at depth ~d (stack ~d)~n',[NP,ND,STACK]),
  format('       goals ~w~n',[Goals]),

  % Even more debugging output
  ( var(Plan) -> format('  Top node of plan/3 call~n') ; true ), 
  ( nonvar(Plan) -> (length(Plan,LP), format('  Low node of plan/3 call, plan length to complete: ~w~n',[LP])) ; true ),

  % prevent runaway behaviour
  % assertion(NP < 1000000),

  % XXX
  % append/3 is backtrackable.
  % For the top node, it will generate longer completely uninstantiated PrePlans on backtracking:
  % PrePlan = [], Plan = [Action] ;
  % PrePlan = [_G981], Plan = [_G981, Action] ;
  % PrePlan = [_G981, _G987], Plan = [_G981, _G987, Action] ;
  % PrePlan = [_G981, _G987, _G993], Plan = [_G981, _G987, _G993, Action] ;
  % For lower nodes, Plan is instantiated to a list of length N already, and PrePlan will therefore necessarily
  % be the prefix list of length N-1
  % XXX

  append( PrePlan, [Action], Plan),

  % Backtrackably select some concrete Goal from Goals
  select_goal( Goals, Goal), % FIX: In the original this seems to depend on State, but it really doesn't
    assert_goal(Goal),
    format( '    Depth ~d, selected Goal: ~w~n',[ND,Goal]),
  % Check whether Action achieves the Goal. 
  % As Action is free, what we actually do is instantiate Action backtrackably with something that achieves Goal
  achieves( Action, Goal),
    format( '    Depth ~d, selected Action: ~w~n', [ND,Action]),
  % Fully instantiate Action backtrackably
  % FIX: Passed "conditions", the precondition for a move, which is unused at this point: broken up into two calls
  instantiate_action( Action),
    format( '    Depth ~d, action instantiated to: ~w~n', [ND,Action]),
    assertion(ground(Action)),
  % Check that the Action does not clobber any of the Goals
  preserves( Action, Goals),
  % We now have a ground Action that "achieves" some goals in Goals while "preserving" all of them
  % Work backwards from Goals to a "prior goals". regress/3 may fail to build a consistent GoalsPrior!
  regress( Goals, Action, GoalsPrior),
  plan( State, GoalsPrior, PrePlan).

% ----------
% Check
% ----------

assert_goal(X) :-
   assertion(ground(X)),
   assertion((X = on(A,B), block(A), object(B) ; X = clear(C), object(C))).

% ----------
% A State (a list) is satisfied by Goals (a list) if all the terms in Goals can also be found in State
% ----------

satisfied( State, Goals)  :-
  subtract( Goals, State, []). % Set difference yields empty list: [] = Goals - State

% ----------
% Backtrackably select a single Goal term from a set of Goals
% ----------

select_goal( Goals, Goal)  :-
  member( Goal, Goals).

% ----------
% When does an Action (move/2) achieve a Goal (clear/1, on/2)?
% This is called with instantiated Goal and free Action, so this actually instantiates Action
% with something (partially specified) that achieves Goal.
% ----------

achieves( Action, Goal) :-
  assertion(var(Action)),
  assertion(ground(Goal)),
  would_add( Action, GoalsAdded),
  member( Goal, GoalsAdded).

% ----------
% Given a ground Action and ground Goals, will Action from a State leading to Goals preserve Goals?
% ----------

preserves( Action, Goals)  :-
  assertion(ground(Action)),
  assertion(ground(Goals)),
  would_del( Action, GoalsDeleted),
  intersection( Goals, GoalsDeleted, []). % "would delete none of the Goals"

% ----------
% Given existing Goals and an (instantiated) Action, compute the previous Goals
% that, when Action is applied, yield Goals. This may actually fail if no
% consistent GoalsPrior can be built!
% ** It is actually not at all self-evident that this is right and that we get a valid
%    "GoalsPrior" via this method! ** (prove it!)
% FIX: "Condition" replaced by "Preconditions" which is what this is about.
% ----------

regress( Goals, Action, GoalsPrior) :-
  assertion(ground(Action)),
  assertion(ground(Goals)),
  would_add( Action, GoalsAdded),
  subtract( Goals, GoalsAdded, GoalsPriorPass), % from the "lists" library
  preconditions( Action, Preconditions),
  % All the Preconds must be fulfilled in Goals2, so try adding them
  % Adding them may not succeed if inconsistencies appear in the resulting set of goals, in which case we fail
  add_preconditions( Preconditions, GoalsPriorPass, GoalsPrior).

% ----------
% Adding preconditions to existing set of goals and checking for inconsistencies as we go
% Previously named addnew/3
% New we use union/3 from the "lists" library and the modified "consistent"
% ----------

add_preconditions( Preconditions, GoalsPriorIn, GoalsPriorOut) :-
  add_preconditions_recur( Preconditions, GoalsPriorIn, GoalsPriorIn, GoalsPriorOut).

add_preconditions_recur( [], _, GoalsPrior, GoalsPrior).

add_preconditions_recur( [G|R], Goals, GoalsPriorAcc, GoalsPriorOut) :-
  consistent( G, Goals),
  union( [G], GoalsPriorAcc, GoalsPriorAccNext),
  add_preconditions_recur( R, Goals, GoalsPriorAccNext, GoalsPriorOut).

% ----------
% Check whether a given Goal is consistent with the set of Goals to which it will be added
% Previously named "impossible/2".
% Now named "consistent/2" and we use negation as failure
% ----------

consistent( on(X,Y), Goals ) :-
  \+ on(X,Y) = on(A,A),            % this cannot ever happen, actually
  \+ member( clear(Y), Goals ),    % if X is on Y then Y cannot be clear
  \+ ( 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

consistent( clear(X), Goals ) :-
  \+ member( on(_,X), Goals).      % if something is on X, X cannot be clear

% ----------
% Backtrackably instantiate a partially instantiated Action
% Previously named "can/2" and it also instantiated the "Condition", creating confusion
% ----------

instantiate_action(Action) :-
  assertion(Action = move( Block, From, To)),
  Action = move( Block, From, To),
  block(Block), % will unify "Block" with a concrete block
  object(To),   % will unify "To" with a concrete object (block or place)
  To \== Block, % equivalent to \+ == (but = would do here); this demands that blocks and places have disjoint sets of atoms
  object(From), % will unify "From" with a concrete object (block or place)
  From \== To,
  Block \== From.

% ----------
% Find preconditions (a list of Goals) of a fully instantiated Action
% ----------

preconditions(Action, Preconditions) :-
  assertion(ground(Action)),
  Action = move( Block, From, To),
  Preconditions = [clear(Block), clear(To), on(Block, From)].

% ----------
% would_del( Move, DelGoals )
% would_add( Move, AddGoals )
% If we run Move (assuming it is possible), what goals do we have to add/remove from an existing Goals
% ----------

would_del( move( Block, From, To), [on(Block,From), clear(To)] ).
would_add( move( Block, From, To), [on(Block,To), clear(From)] ).

运行上面的输出将产生大量的输出，并最终：

plan/3 call 57063 at depth 6 (stack 98304)
   Goals: [clear(2),clear(3),clear(4),clear(c),on(a,1),on(b,a),on(c,b)]
   State: [clear(2),clear(3),clear(4),clear(c),on(a,1),on(b,a),on(c,b)]
   *** SATISFIED ***
Plan step 1: move(c,b,3)
Plan step 2: move(b,a,4)
Plan step 3: move(a,1,2)
Plan step 4: move(b,4,a)
Plan step 5: move(c,3,b)

另请参阅

• 带材自动计划机
• 迭代深化深度优先搜索
• 区块世界