Iterative deepening search - Help!

[Guest_imported]

I'm using IDS to find a path from a start point to a goal in a maze. The problem is that when no path exists, my algorithm keeps looping. How can I correct this?

Also the variable containing the resulting path (Move) always has a tail of the form of 'GD<number>' which shouldn't be there but keeps getting appended. The head of the list contains the correct path in the form of 'left', 'up'...etc directives.

Thanks

iterative_DF(X, Y, Move, Depth) :- depth_first(X, Y, Move, Depth), !.
iterative_DF(X, Y, Move, Depth) :- NewDep is Depth + 1, iterative_DF(X, Y, Move, NewDep).


depth_first(CX, CY, _, _) :- goal(CX, CY).
depth_first(CX, CY, [Move|T], Depth) :- Depth > 0, NextDep is Depth - 1, move(CX, CY, Move, NX, NY), depth_first(NX, NY, T, NextDep).

 

[pimi]

Hello.
I think that there are the following two methods.

1. restricting the depth of search
2. check the way along which it already passed


*** program ***

% 1 2 3
% +---+---+---+
% 1 | S |
% +---+ + +
% 2 | |
% + +---+---+
% 3 | / G |
% +---+---+---+

goal(3, 3).
move(1, 1, right, 2, 1).
move(2, 1, left, 1, 1).
move(2, 1, right, 3, 1).
move(2, 1, down, 2, 2).
move(3, 1, left, 2, 1).
move(3, 1, down, 3, 2).
move(1, 2, right, 2, 2).
move(1, 2, down, 1, 3).
move(2, 2, left, 1, 2).
move(2, 2, top, 2, 1).
move(2, 2, right, 3, 2).
move(3, 2, top, 3, 1).
move(3, 2, left, 2, 2).
move(1, 3, top, 1, 2).
move(1, 3, right, 2, 3).
move(2, 3, left, 1, 3).
move(2, 3, right, 3, 3).
move(3, 3, left, 2, 3).

%%% method of restricting the depth of search

iterative_DF2(X, Y, Move, DepthMax) :-
depth_first2(X, Y, Move, DepthMax).
depth_first2(CX, CY, [], _) :-
goal(CX, CY).
depth_first2(CX, CY, [Move|T], DepthMax) :-
DepthMax > 0,
move(CX, CY, Move, NX, NY),
depth_first2(NX, NY, T, DepthMax - 1).

%%% method of checking the way along which it already passed

iterative_DF3(X, Y, Move) :-
depth_first3(X, Y, Move, []).
depth_first3(CX, CY, [], _) :-
goal(CX, CY).
depth_first3(CX, CY, [Move|T], Passed) :-
move(CX, CY, Move, NX, NY),
not(member([NX, NY], Passed)),
depth_first3(NX, NY, T, [[NX, NY]|Passed]).

%%% typical member function

member(X, [X|L]).
member(X, [_|L]) :- member(X, L).


*** sample ***

?- iterative_DF2(1, 1, Move, 6).
Move = [right,down,left,down,right,right] ;
no

?- iterative_DF2(1, 1, Move, 7).
Move = [right,down,left,down,right,right] ;
no

?- iterative_DF2(1, 1, Move, 8).
Move = [right,left,right,down,left,down,right,right] ;
Move = [right,right,left,down,left,down,right,right] ;
Move = [right,right,down,left,left,down,right,right] ;
Move = [right,down,left,right,left,down,right,right] ;
Move = [right,down,left,down,top,down,right,right] ;
Move = [right,down,left,down,right,left,right,right] ;
Move = [right,down,left,down,right,right] ;
Move = [right,down,left,down,right,right,left,right] ;
Move = [right,down,top,down,left,down,right,right] ;
Move = [right,down,right,left,left,down,right,right] ;
no

?- iterative_DF3(1, 1, Move).
Move = [right,right,down,left,left,down,right,right] ;
Move = [right,down,left,down,right,right] ;
no

?- retract(move(1, 3, right, 2, 3)). % close; no path exists
yes

?- iterative_DF2(1, 1, Move, 6).
no

?- iterative_DF2(1, 1, Move, 7).
no

?- iterative_DF2(1, 1, Move, 10).
no

?- iterative_DF3(1, 1, Move).
no