通过伊万·布拉特科（Ivan Bratko）在其书中关于Prolog的人工智能示例进行学习：
“Prolog Programming for Artificial Intelligence – 第三版”（ISBN-13: 978-0201403756）（第一版1986年由Addison-Wesley出版，ISBN 0-201-14224-4）
我注意到很多示例无法运行到完成，而是似乎卡住了。我尝试了几个不同的实现，严格按照书中的方法进行，但没有成功。是否有人愿意查看代码，看看是否能发现逻辑错误或是我犯的错误？
这是书中所示的用于方块世界的STRIPS风格规划器的完整程序：
% 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 Stateplan( 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 Stateselect( State, Goals, Goal) :- % Select Goal from Goals member( Goal, Goals). % A simple selection principleachieves( 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 compatibleaddnew( [], L, L).addnew( [Goal | _], Goals, _) :- impossible( Goal, Goals), % Goal incompatible with Goals !, fail. % Cannot be addedaddnew( [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 L2delete_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 placeimpossible( 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 fe ed ---> dc cb ba ~ ~ ~ ~ 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
- 带有目标回归的终端手段规划器：http://media.pearsoncmg.com/intl/ema/ema_uk_he_bratko_prolog_3/prolog/ch17/fig17_8.txt
任何建议都将不胜感激。
回答：
最终，代码是正确的，但组合爆炸使其无法完成。
数据：
- 3个位置，3个方块在调用
plan/39’755次后成功，移动5次。 - 4个位置，3个方块在调用
plan/398’304次后成功，移动5次。 - 3个位置，4个方块在调用
plan/3915’703次后成功，移动7次。 - 3个位置，5个方块在调用
plan/397’288’255次后成功，移动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在计划为未绑定变量时与计划为绑定变量时的行为不同。第一种情况仅在隐含搜索树的顶部节点发生。这可能在教科书中进一步解释，我没有这本书，花了一些时间才意识到这段代码中实际发生了什么。
如果我在plan/3的搜索分支开始处放置的修剪表达式((nonvar(Plan), Plan == []) -> fail ; true )令人恼火，那么迭代加深的技巧也应该如此。依我之见，最好使用树深度计数器，并通过累加器返回计划。特别是如果有人将被指派在生产系统中维护这样的代码（即，“生产中的系统”，而不是“前向链式规则系统”）。
% 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 placeconsistent( 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)另见
