Prolog STRIPS 规划器永远不会完成
Prolog STRIPS planner never completes
以下是 Ivan Bratko 在其书中关于 Prolog 中人工智能的示例：
"Prolog Programming for Artificial Intelligence - 3rd Edition" (ISBN-13: 978-0201403756)（Addison-Wesley 1986 年第一版，ISBN 0-201-14224-4）
我注意到很多示例没有 运行 完成，而是似乎卡住了。我已经尝试了几种不同的实现方式，但没有成功。有没有人愿意看一下代码，看看他们是否能找出逻辑错误的地方，或者我是否犯了错误？
这是 STRIPS style planner 方块世界的完整程序，如书中所示：
% 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 个位置，并使用所有块按字母顺序从 a 到 g 在位置 1 上堆叠的表示进行测试，目标是在位置 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
参考文献：
- 走法定义：http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_2.txt
- End means planner with goal regression: http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_8.txt
如有任何建议，我们将不胜感激。
最后，代码是正确的，但组合爆炸杀死了它。
数据：
- 3 个位置，3 个方块 在调用
plan/3. 9'755 次后成功移动 5 步
- 4 个位置，3 个方块 在调用
plan/3 98'304 次后成功移动 5 次。
- 3 个位置，4 个方块 在调用
plan/3 915'703 次后成功移动 7 步。
- 3 个地方，5 个方块 在调用
plan/3. 97'288'255 次后成功移动 9 步
尝试更多是没有意义的，尤其是 4 个地方，7 个街区 。很明显，需要启发式方法、对称性利用等才能走得更远。所有这些都需要更大的内存。在这里，使用的内存在所有情况下都保持很小：在任何时候，迭代加深（并存储在堆栈中）搜索树中只有一条路径是活动的。我们不记得访问过的任何州或任何东西，这是一个非常简单的搜索。
更新代码下方（长，337 行）
改动（代码中标有'FIX'的重要改动）
library(list) 在可能的情况下使用了谓词，去掉了一些代码。- 添加了使用
format/2 调试输出生成。
- 断言（参见 here）使用
assertion/1 添加以检查发生的事情是否是我认为发生的事情。
- 谓词和变量重命名以更好地反映它们的预期含义。
run/0 添加了谓词，它初始化状态和目标，调用 plan/3 并打印计划。can/2 混淆地结合了两个独立的方面：实例化一个动作和确定它的先决条件。分为两个谓词 instantiate_action/1 和 preconditions/2.select_goal/2 看起来像是依赖于 State，但实际上并非如此。清理干净。
注意将此设为 "iterative deepening" 搜索的技巧。它非常聪明，但转念一想，它太聪明了一半，因为它基于谓词 run/3 在调用未绑定变量 Plan 时与调用绑定变量 Plan 时表现不同。第一种情况仅出现在隐含搜索树的最顶端节点。这可能在我没有的教科书中有进一步的解释，我花了一些时间才意识到这段代码中实际发生了什么。
如果我放在 plan/3 搜索分支开头的修剪表达式 ((nonvar(Plan), Plan == []) -> fail ; true ) 令人恼火，那么迭代加深技巧也应该如此。恕我直言，最好通过累加器使用树深度计数器和 return 计划。特别是如果有人将负责在生产系统中维护此类代码（即 "system in production"，而不是 "forward-chaining rule-based system"）。
% 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)
另见
以下是 Ivan Bratko 在其书中关于 Prolog 中人工智能的示例：
"Prolog Programming for Artificial Intelligence - 3rd Edition" (ISBN-13: 978-0201403756)（Addison-Wesley 1986 年第一版，ISBN 0-201-14224-4）
我注意到很多示例没有 运行 完成，而是似乎卡住了。我已经尝试了几种不同的实现方式，但没有成功。有没有人愿意看一下代码，看看他们是否能找出逻辑错误的地方，或者我是否犯了错误？
这是 STRIPS style planner 方块世界的完整程序，如书中所示：
% 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 个位置，并使用所有块按字母顺序从 a 到 g 在位置 1 上堆叠的表示进行测试，目标是在位置 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
参考文献：
- 走法定义：http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_2.txt
- End means planner with goal regression: http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_8.txt
如有任何建议，我们将不胜感激。
最后，代码是正确的，但组合爆炸杀死了它。
数据：
- 3 个位置，3 个方块 在调用
plan/3. 9'755 次后成功移动 5 步
- 4 个位置，3 个方块 在调用
plan/398'304 次后成功移动 5 次。 - 3 个位置，4 个方块 在调用
plan/3915'703 次后成功移动 7 步。 - 3 个地方，5 个方块 在调用
plan/3. 97'288'255 次后成功移动 9 步
尝试更多是没有意义的，尤其是 4 个地方，7 个街区 。很明显，需要启发式方法、对称性利用等才能走得更远。所有这些都需要更大的内存。在这里，使用的内存在所有情况下都保持很小：在任何时候，迭代加深（并存储在堆栈中）搜索树中只有一条路径是活动的。我们不记得访问过的任何州或任何东西，这是一个非常简单的搜索。
更新代码下方（长，337 行）
改动（代码中标有'FIX'的重要改动）
library(list)在可能的情况下使用了谓词，去掉了一些代码。- 添加了使用
format/2调试输出生成。 - 断言（参见 here）使用
assertion/1添加以检查发生的事情是否是我认为发生的事情。 - 谓词和变量重命名以更好地反映它们的预期含义。
run/0添加了谓词，它初始化状态和目标，调用plan/3并打印计划。can/2混淆地结合了两个独立的方面：实例化一个动作和确定它的先决条件。分为两个谓词instantiate_action/1和preconditions/2.select_goal/2看起来像是依赖于 State，但实际上并非如此。清理干净。
注意将此设为 "iterative deepening" 搜索的技巧。它非常聪明，但转念一想，它太聪明了一半，因为它基于谓词 run/3 在调用未绑定变量 Plan 时与调用绑定变量 Plan 时表现不同。第一种情况仅出现在隐含搜索树的最顶端节点。这可能在我没有的教科书中有进一步的解释，我花了一些时间才意识到这段代码中实际发生了什么。
如果我放在 plan/3 搜索分支开头的修剪表达式 ((nonvar(Plan), Plan == []) -> fail ; true ) 令人恼火，那么迭代加深技巧也应该如此。恕我直言，最好通过累加器使用树深度计数器和 return 计划。特别是如果有人将负责在生产系统中维护此类代码（即 "system in production"，而不是 "forward-chaining rule-based system"）。
% 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)
另见