Performance issues on prolog

Question

I'm currently implementing an prolog program to calculate the shortest path between two points. The framework exists already in a Java project. As a requirement the path must be implemented in prolog. Therefore I use gnu.prolog (http://www.gnu.org/software/gnuprologjava/)

Out of java I call searchPath(1,5,Path) which will return Path=[5,4,3,2,1]

Here is my prolog code:

:- dynamic(path/3).

findPath( [Goal | Rest], Goal, Temp, Temp, [Goal | Rest]).

findPath( [A | Rest], Goal, Cost, Temp, Path) :-
    path(A,B,C),
    \+member(B, [A | Rest]),
    NewCosts is (Temp + C),
    findPath([B, A | Rest], Goal, Cost, NewCosts, Path).

searchPath(Start,Goal,Path_to_goal) :-
    findPath([Start], Goal, Cost1, 0, Path),
    findPath([Start], Goal, Cost2, 0, Path2),
    Cost1=<Cost2,
    Path_to_goal = Path.

I have two issues with that:

1. The searchPath method should return the shortest path. However it does NOT. This results in the fact that my ghost "decides" to switch direction at some point resulting in the ghost jittering from left to right.

2. My prolog code takes up to 6 seconds to return a result. I don't have to tell you that this is far too much time. However sometimes prolog only needs 19ms. I wasn't able to figure out on which circumstances this depends on. For example a path list containing 99 elements takes 19ms to calculate but the 6 seconds were spent on a list containing only 38 elements.

Can you suggest any improvements?

Thanks for your help in advance!

Answer 1

You could use Dijkstra' algorithm. I implemented it answering to this question. My code uses attributed variables, I think should work in GnuProlog (I'll test now). Anyway, there you'll find the link to a working pure Prolog implementation.

edit well, I think you could correct your code, because there is a problem:

Path2 in searchPath/3 it's a singleton: then you clearly are going to always end with the first Path, and because the second findPath/3 will find always (if database doesn't change) the very same Cost and Path as the first, Cost1=<Cost2, will be always true. You could try if

searchPath(Start,Goal,Path_to_goal) :-
    findall(Cost-Path, findPath([Start], Goal, Cost, 0, Path), Paths),
    sort(Paths, [_-Path_to_goal|_]).

is sufficiently fast for your assignment. Otherwise you'll need to implement an incremental search, not easy to do because Prolog 'returns' alternatives paths on backtracking, then forcing to use some kind of side effect to select the minimum value.

more edit findall/3 will result in code too much slow. I've coded something more efficient using non backtrackable assignment (I used SWI-Prolog nb_setarg/3, you should use setarg/3 in GProlog).

findPath(_Limit, [Goal | Rest], Goal, Temp, Temp, [Goal | Rest]) :- !.

findPath(Limit, [A | Rest], Goal, Cost, Temp, Path) :-
    path(A,B,C),
    \+member(B, Rest),
    NewCosts is (Temp + C),
    NewCosts < Limit,
    findPath(Limit, [B, A | Rest], Goal, Cost, NewCosts, Path).

% ?- searchPath(aberdeen, glasgow, Path, Length).
%
searchPath(Start, Goal, Path_to_goal, L) :-
    S = path_len([], 1000000),
    repeat,
    arg(2, S, Limit),
    (   findPath(Limit, [Start], Goal, Cost, 0, Path)
    ->  (   Cost < Limit
        ->  nb_setarg(1, S, Path),
        nb_setarg(2, S, Cost),
        fail
        )
    ;   true
    ),
    arg(1, S, Rev),
    reverse(Rev, Path_to_goal),
    arg(2, S, L).