Prolog 中的区块世界问题不断在相同的两个状态之间振荡

Question

我正在尝试在序言中实现一个块世界程序。区块世界是人工智能中的一个众所周知的问题，其本身相当简单。这是我当前的代码：

% Define the blocks in your world
blocks([a, b, c, d, e, f]).

% A block X is a member of the list of blocks
block(X) :-
    blocks(BLOCKS),  % Extract the list BLOCKS
    member(X, BLOCKS).

% Given predicates
move(X, Y, Z, S1, S2):-
    member([clear, X], S1),
    member([on, X, Y], S1),
    block(Y),
    member([clear, Z], S1),
    notequal(X, Z),
    substitute([on, X, Y], [on, X, Z], S1, INT),
    substitute([clear, Z], [clear, Y], INT, S2).

notequal(X, X):-!, fail.
notequal(_, _).

substitute(X, Y, [X|T], [Y|T]).
substitute(X, Y, [H|T], [H|T1]):-
    substitute(X, Y, T, T1).

% Additional predicates to be implemented
% (i) move from a block onto the table
move_onto_table(X, Y, S1, S2):-
    member([clear, X], S1),
    member([on, X, Y], S1),
    substitute([on, X, Y], [on, X, 'table'], S1, INT),
    substitute([clear, Y], [clear, X], INT, S2).

% (ii) move from the table onto a block
move_onto_block(X, Y, S1, S2):-
    member([clear, X], S1),
    member([on, X, 'table'], S1),
    substitute([on, X, 'table'], [on, X, Y], S1, INT),
    substitute([clear, X], [clear, Y], INT, S2).

% Define start and goal states
start([[on, d, 'table'], [on, c, d], [on, a, c], [on, b, 'table'], [clear, a], [clear, b]]).
goal([[on, d, 'table'], [on, c, 'table'], [on, a, b], [on, b, 'table'], [clear, a], [clear, c], [clear, d]]).

% Define notYetVisited
notYetVisited(State, PathSoFar):-
    permutation(State, PermuteState),
    \+ member(PermuteState, PathSoFar).

% Define path and connect predicates
path(S1, S2):-
    move(X, Y, Z, S1, S2).
path(S1, S2):-
    move_onto_table(X, Y, S1, S2).
path(S1, S2):-
    move_onto_block(X, Y, S1, S2).

connect(S1, S2) :- path(S1, S2).
connect(S1, S2) :- path(S2, S1).

% Define DFS predicate with added debugging statements and iterative deepening
dfs(X, [X], _):-
    goal(X),
    write('Goal reached: '), write(X), nl.
% else expand X by Y and find path from Y
dfs(X, [X|Ypath], VISITED):-
    connect(X, Y),
    notYetVisited(Y, VISITED),
    write('Current state: '), write(X), nl,
    write('Moving to: '), write(Y), nl,
    dfs(Y, Ypath, [Y|VISITED]).

我使用的查询是：

start(Start), dfs(Start, Path, []).

现在出现的输出只是一个循环。尽管对重复状态进行了检查，但 dfs 似乎只是在相同的两个状态之间振荡：

Current state: [[on, d, table], [on, c, d], [on, a, c], [on, b, table], [clear, a], [clear, b]]
Moving to: [[on, d, table], [on, c, d], [on, a, b], [on, b, table], [clear, a], [clear, c]]
Current state: [[on, d, table], [on, c, d], [on, a, b], [on, b, table], [clear, a], [clear, c]]
Moving to: [[on, d, table], [on, c, d], [on, a, c], [on, b, table], [clear, a], [clear, b]]
Current state: [[on, d, table], [on, c, d], [on, a, c], [on, b, table], [clear, a], [clear, b]]
Moving to: [[on, d, table], [on, c, d], [on, a, b], [on, b, table], [clear, a], [clear, c]]
Current state: [[on, d, table], [on, c, d], [on, a, b], [on, b, table], [clear, a], [clear, c]]
Moving to: [[on, d, table], [on, c, d], [on, a, c], [on, b, table], [clear, a], [clear, b]]
Current state: [[on, d, table], [on, c, d], [on, a, c], [on, b, table], [clear, a], [clear, b]]
Moving to: [[on, d, table], [on, c, d], [on, a, b], [on, b, table], [clear, a], [clear, c]]
Current state: [[on, d, table], [on, c, d], [on, a, b], [on, b, table], [clear, a], [clear, c]]
Moving to: [[on, d, table], [on, c, d], [on, a, c], [on, b, table], [clear, a], [clear, b]]

我尝试了多种解决方案。显然，期望它经历尽可能多的状态以达到目标状态（这是在脚本中硬编码的）。这是我到目前为止所做的：

1. 改变 notYetVisited 的工作方式，尝试进行简单的相等而不是使用排列。但是，这会导致超出堆栈限制。
2. 在各个点添加调试语句。这些都包含在提供的代码中。
3. 使用 DFID（深度优先迭代加深）方法来代替 dfs 过程。这不起作用，因为再次几乎立即超出了堆栈限制。
4. 更改 dfs 以在回溯时更新状态。
5. 更改移动过程（move_onto_table 和 move_onto_block）以确保满足“清除”条件。

Answer 1

您的代码的主要问题是：

• 谓词

  notYetVisited/2

  确定如果存在尚未访问的状态 some 排列，则该状态尚未被访问。例如，以下查询应该 fail （因为列表

  [a,b]

  和

  [b,a]

  代表相同的状态）。

  ?- notYetVisited([a,b], [[b,a]]).
  true .
  

• 操作

  move_onto_table

  和

  move_onto_block

  未正确定义。例如：

  move_onto_table(X, Y, S1, S2):-
      member([clear, X], S1),
      member([on, X, Y], S1),
      block(Y),                                          % <== this condition must be added!
      substitute([on, X, Y], [on, X, 'table'], S1, INT),
      substitute([clear, Y], [clear, X], INT, S2).       % <== fluent clear(X) should be maintained, not substitued!
  

您的代码可以在几个方面进行改进：

• 使用 terms 表示 Fluents 并使用 termslists 表示 states。因此，开始状态可以用

  [clear(a), clear(b), on(a,c), on(b,t), on(c,d), on(d,t)]

  表示，其中

  t

  代表 table。

• 使用有序集，这样你就不必处理排列。

因此，一个可能的解决方案（使用 swi-prolog）是：

% Iterative deepening search

ids(Limit, Plan) :-
    start(Start0),
    goal(Goal0),
    list_to_ord_set(Start0, Start),
    list_to_ord_set(Goal0, Goal),
    between(0, Limit, Len),
    length(Plan, Len),
    dfs(Start, Goal, [Start], Plan).

dfs(State, State, _Visited, Plan):-
    !,
    Plan = [].

dfs(State, Goal, Visited, [Action|Actions]):-
    action(Action, State, Next),
    not(member(Next, Visited)),
    dfs(Next, Goal, [Next|Visited], Actions).

% Blocks world

% Start
% 
%      a
%      c
%  b   d
% ------- t
%
% Goal
%
%  a
%  b c d
% ------- t


block(X) :-
    member(X, [a, b, c, d]).


start([on(d, t),
       on(c, d),
       on(a, c),
       on(b, t),
       clear(a),
       clear(b)]).

goal([on(d, t),
      on(c, t),
      on(a, b),
      on(b, t),
      clear(a),
      clear(c),
      clear(d)]).

action(move(X,Y,Z), S1, S3):-
    member(clear(X), S1),
    member(on(X,Y), S1),
    block(Y),
    member(clear(Z), S1),
    X \= Z,
    ord_subtract(S1, [clear(Z), on(X,Y)], S2),
    ord_union([clear(Y), on(X,Z)], S2, S3).

action(move_onto_table(X,Y), S1, S3):-
    member(clear(X), S1),
    member(on(X,Y), S1),
    block(Y),
    ord_subtract(S1, [on(X,Y)], S2),
    ord_union([clear(Y), on(X,t)], S2, S3).

action(move_onto_block(X,Y), S1, S3):-
    member(clear(X), S1),
    member(clear(Y), S1),
    member(on(X,t), S1),
    X \= Y,
    ord_subtract(S1, [clear(Y), on(X,t)], S2),
    ord_union([on(X,Y)], S2, S3).

示例：

?- ids(3, Plan).
Plan = [move(a, c, b), move_onto_table(c, d)] ;
Plan = [move(a, c, b), move(c, d, a), move_onto_table(c, a)] ;
Plan = [move_onto_table(a, c), move_onto_table(c, d), move_onto_block(a, b)] ;
Plan = [move_onto_table(a, c), move_onto_block(a, b), move_onto_table(c, d)] ;
false.