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