Pathfinding in SWI-Prolog (Generate and Test Method)

Ok, so I am trying to build a path-finding SWI-Prolog 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 | | | | |X|F|
%   -------------
% 5 | | | |X|X| |
%   -------------
% 4 | |X|X|P| | |
%   -------------
% 3 |X|P| | | | |
%   -------------
% 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 =:= PrevY-1, NextX =:= PrevX)
   ;  (NextY =:= PrevY+1, NextX =:= PrevX)
   ;  (NextY =:= PrevY, NextX =:= PrevX+1)
   ;  (NextY =:= PrevY, NextX =:= PrevX-1)
   ),
   append(P,[NextY,NextX],Np),
   build_path(Y,X,NextY,NextX,Np).

is_last([Y,X],[H|[]]) :- H = [Y,X].
is_last([Y,X],[H|T]) :- 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 over-complicating 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

  • answered 2018-04-14 16:16 Taku Koyahata

    I didn't read your program deeply, but at least those points seems incorrect:

    1. NextY =:= PrevY-1 part should be changed to NextY is PrevY - 1. =:= is just for comparing and isn't for setting values.

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

    1. and you don't check generated coodinates are not going outside of the board.

    2. 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 recommend breadth first search algorithm

  • answered 2018-04-14 16:56 Tomas By

    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(Y-X,P0),
        append(P0,[Y-X],P1),
        ( pick_up(Y,X) -> Is1 = [Y-X|Is0] ; 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 if-then-else, 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.