Pathfinding in SWIProlog (Generate and Test Method)
Ok, so I am trying to build a pathfinding SWIProlog program that takes the grid to traverses' properties from facts in the knowledge base:
y_max(Ymax).
x_max(Xmax).
pick_up(Y,X).
So for example, the code below represents a grid below it here:
y_max(6).
x_max(6).
pick_up(4,4).
pick_up(3,2).
% 6      F
% 
% 5       
% 
% 4    P  
% 
% 3  P    
% 
% 2       
% 
% 1 L     
% 1 2 3 4 5 6
% (Note that coordinates will be in the form [Y,X].
Where F is to be the start of the path, being [6,6], L is to be the end of the path, [1,1], and the path should be so that as many pick_up "objects" are picked up along the path as possible. so in this case an "ideal" solution would be:
% 6     XF
% 
% 5    XX 
% 
% 4  XXP  
% 
% 3 XP    
% 
% 2 X     
% 
% 1 L     
% 1 2 3 4 5 6
where the path P would be: P = [[6,6],[6,5],[5,5],[5,4],[4,4],[4,3],[4,2],[3,2],[3,1],[2,1],[1,1]]
my main relation will be:
solve(P,A) :
which will return, based on the knowledge base giving the graph, an ideal (shortest) path P, and A, with A being the number of pickup objects picked up by the path (which should be the maximum number of pickup objects that can be picked up.
I am trying to do this using a generate and test type approach. Because the length of the path cannot be known based on the knowledge base (as far as I'm aware), I'm assuming I will have to recursively generate and test coordinates? I'm trying to do this exercise without using any libraries to really get a grasp on this style of Prolog programming, where I generate and test the path.
Here is what I have so far, but I just can't seem to get it right. Instead it just gives me ERROR: Out of Global stack each time.
% FACTS
y_max(6).
x_max(6).
pick_up(5,5).
pick_up(4,4).
pick_up(2,2).
solve(A,P) :
y_max(Y), x_max(X), aggregate_all(count,pick_up(O,E),C),
A = C, append(P,[Y,X],Np), build_path(Y,X,Y,X,P),
% I'm assuming at this point the list is generated, now to test...
member([Y,X],P), is_last([1,1],P), member([O,E],P).
% cases to end recursion  not sure if I'm doing this part correctly...
build_path(Y,X,1,2,P) : append(P,[1,1],Q), P = Q.
build_path(Y,X,2,1,P) : append(P,[1,1],Q), P = Q.
% recursive case
build_path(Y,X,PrevY,PrevX,P) :
integer(NextY), integer(NextX),
NextY =< Y, NextY >= 1,
NextX =< X, NextY >= 1,
( (NextY =:= PrevY1, NextX =:= PrevX)
; (NextY =:= PrevY+1, NextX =:= PrevX)
; (NextY =:= PrevY, NextX =:= PrevX+1)
; (NextY =:= PrevY, NextX =:= PrevX1)
),
append(P,[NextY,NextX],Np),
build_path(Y,X,NextY,NextX,Np).
is_last([Y,X],[H[]]) : H = [Y,X].
is_last([Y,X],[HT]) : is_last([Y,X],T).
So, what am I doing wrong? I can't seem to find a similar example online that would give me the right idea. I'm assuming I'm just overcomplicating things or am not expressing certain information to Prolog properly. I apologize if my solution is full of errors. I'm just trying to get a grasp on Prolog currently.
2 answers

I didn't read your program deeply, but at least those points seems incorrect:
NextY =:= PrevY1
part should be changed toNextY is PrevY  1
.=:=
is just for comparing and isn't for setting values.Your code seems to be in infinite loop at
build_path
, because you don't check genarated next coodinates are not in the coodinates list.
3.
integer(NextY), integer(NextX),
always fail because they are new variables and not set any values yet, of cause they are not integer.and you don't check generated coodinates are not going outside of the board.
you are trying
depth first search
algorithm.After you make this program work , unfortunately genarated first answer will be far from the shortest path.when you want to get shortest path, I recommendbreadth first search algorithm

Here is a version of
build_path/N
that seems to work.build_path(MaxY,MaxX,Y0,X0,P0,P,Is0,Is) : ( Y0 = 1, X0 = 1 > P = P0, Is = Is0 ; ( Y is Y0  1, X is X0 ; Y is Y0 + 1, X is X0 ; Y is Y0, X is X0 + 1 ; Y is Y0, X is X0  1 ), Y =< MaxY, Y >= 1, X =< MaxX, X >= 1, \+ member(YX,P0), append(P0,[YX],P1), ( pick_up(Y,X) > Is1 = [YXIs0] ; Is1 = Is0 ), build_path(MaxY,MaxX,Y,X,P1,P,Is1,Is) ).
You need to make sure it stops when it hits the end square, so you need to use ifthenelse, or a cut.
I added a list of picked up items, so now you just need to find the optimal combination of path and list.