This is a block world problem which is going to move the blocks where we want them to be.
The predicate located_on tells us the locations of blocks according to the fluents. The goal_state is where we want the blocks to be.
The third parameter of located_on is situations(fluents), which indicates the action history.
The fluent starts at empty list which means no action has been done yet. After each action, we add the action into the third parameter fluent.
For example, if we move a to b, then move b to c, then move c to d, the fluent would be [move(c,d),move(b,c),move(a,b)]. We can know where each blocks are according to fluents(their action history).
%Successor states
located_on(A,B,[move(A,B)|_]).
located_on(B,L,[_|S]) :- located_on(B,L,S).
%Goal state
goal_state(S):- located_on(a,b,S),located_on(d,area2,S).
The problem is that, when I have only one goal, say goal_state(S):- located_on(a,b,S), I can get all possible fluents S:
?- goal_state(X).
X = [] ;
X = [move(a, b)|_G4037] ;
X = [_G4036] ;
X = [_G4036, move(a, b)|_G4040] ;
X = [_G4036, _G4039] ;
X = [_G4036, _G4039, move(a, b)|_G4043] ;
X = [_G4036, _G4039, _G4042] ;
X = [_G4036, _G4039, _G4042, move(a, b)|_G4046] ;
X = [_G4036, _G4039, _G4042, _G4045] ;
X = [_G4036, _G4039, _G4042, _G4045, move(a, b)|_G4049]
But when I have more than one goals, say goal_state(S):- located_on(a,b,S),located_on(d,area2,S)., the fluents I get get stuck in one of its goals:
?- goal_state(X).
X = [] ;
X = [move(a, b)] ;
X = [move(a, b), move(d, area2)|_G344] ;
X = [move(a, b), _G343] ;
X = [move(a, b), _G343, move(d, area2)|_G347] ;
X = [move(a, b), _G343, _G346] ;
X = [move(a, b), _G343, _G346, move(d, area2)|_G350] ;
X = [move(a, b), _G343, _G346, _G349] ;
X = [move(a, b), _G343, _G346, _G349, move(d, area2)|_G353] ;
X = [move(a, b), _G343, _G346, _G349, _G352] ;
X = [move(a, b), _G343, _G346, _G349, _G352, move(d, area2)|_G356] ;
X = [move(a, b), _G343, _G346, _G349, _G352, _G355] ;
X = [move(a, b), _G343, _G346, _G349, _G352, _G355, move(d, area2)|_G359]
The first element here are aways move(a,b) since the program get infinite loop in satisfying move(d, area2).
Is there any way that can help me get rid of the infinite loop?
The whole program is like this:
%Initial states
initial_state([]).
located_on(a,b,[]).
located_on(b,c,[]).
located_on(c,area1,[]).
located_on(d,area2,[]).
%Successor states
located_on(A,B,[move(A,B)|_]).
located_on(B,L,[_|S]) :- located_on(B,L,S).
%Goal state
goal_state(S):- located_on(a,b,S),located_on(d,area2,S),located_on(b,d,S),located_on(c,area1,S).
%Poss
poss(move(A,B),S) :- member(A,[a,b,c,d]),member(B,[a,b,c,d,area1,area2,area3]),
\+A=B,clear(A,S),clear(B,S).
clear(A,S) :- member(A,[a,b,c,d,area1,area2,area3]), \+located_on(_,A,S).
%Solve problem
legal_move(S,A,[A|S]):-poss(A,S).
plan(L) :- initial_state(I), goal_state(G), reachable(I,L,G).
reachable(S,[],S).
reachable(S1,[M|L],S3) :- legal_move(S1,M,S2), reachable(S2,L,S3).
I solve the problem by replacing plan(L) :- initial_state(I), goal_state(G), reachable(I,L,G). with plan(L) :- initial_state(I), reachable(I,L,G), goal_state(G).
That means instead of generating all possible goal_states, we first try every reachable positions and then check if they are goal states. In this way we get unified G when dealing with goal_state.
Here is the answer from prolog:
24 ?- plan([A,B,C]).
A = move(a, area3),
B = move(b, d),
C = move(a, b) ;
false.
In this formulation, you can't get rid of the infinite recursion alltogther because moving a block between to a new state and back creates a cycle in the graph, which corresponds to an infinite list.
What you can do is to perform an iterative deepening search by unifiying the solution with an arbitrary list first:
:- length(S,_), goal_state(S).
first, S is unified with a list of length 0, on which goal_state is tried. After all lists of length an were tried, length unifies with a list of length 1, etc.
Edit: thanks to mat for identifying the correct search strategy!