Blocks-World Problem in Prolog keeps oscillating between the same two states

Question

I am trying to implement a blocks world program in prolog. Blocks world is a well-known problem in AI, and in and of itself, is rather simple. This is my current code:

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

The query I'm using is thus: start(Start), dfs(Start, Path, []).

Now, the output that appears is simply a loop. Despite implementing a check for repeated states, dfs simply seems to oscillate between the same two states as such:

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]]

I have tried multiple solutions. Obviously, the expectation is for it to go through as many states as needed to reach the goal state (which is hard-coded in the script). Here's what I've done so far:

1. Changing the way notYetVisited works, trying to do a simple equality rather than using permutation. However, this results in the stack limit being exceeded.
2. Adding debugging statements at various points. These are included in the provided code.
3. Using a DFID (Depth-First Iterative Deepening) approach for the dfs procedure instead. This did not work, as again, stack limit was exceeded almost instantaneously.
4. Changing dfs to update the state when backtracking.
5. Altering the move procedures (move_onto_table and move_onto_block) to make sure the 'clear' condition is satisfied.

Answer 1

The main problems with your code are:

• The predicate notYetVisited/2 establishes that a state has not yet been visited if there exists some permutation of it that has not yet been visited. For example, the following query should fail (since the lists [a,b] and [b,a] represent the same state).

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

• The actions move_onto_table and move_onto_block are not defined correctly. For example:

  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!
  

Your code can be improved in several aspects:

• Use terms to represent fluents and lists of terms to represent states. Thus, the start state can be represented by [clear(a), clear(b), on(a,c), on(b,t), on(c,d), on(d,t)], where t stands for table.

• Use ordered sets, so you don't have to handle permutations.

Thus, a possible solution (using swi-prolog) is:

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

Example:

?- 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.