prologlogic-programmingnegateanswer-set-programming

Prolog - ASP 'not' to Prolog negate

I have an example problem in Answer Set Programming (ASP). When I try to make the equivalent code in Prolog, I keep getting stuck with the not blocked.

This is the ASP code:

road(berlin,potsdam).
road(potsdam,werder).
road(werder,brandenburg).
road(X,Y) :- road(Y,X).

blocked(werder,brandenburg).

route(X,Y) :- road(X,Y), not blocked(X,Y).
route(X,Y) :- route(X,Z), route(Z,Y).

drive(X) :- route(berlin,X).

#show drive/1

The answer is: drive(potsdam), drive(werder), drive(berlin).

In Prolog, I initially thought it would be as simple as changing the not to \+. When I query drive(X)., it recursively generates the X = potsdam answer. I know that Prolog and ASP work differently but I just can't figure it out.

Solution

  • The problem is road(X,Y) :- road(Y,X). This will recurse forever if there is no match among the facts:

    is road(X,Y)?
is road(Y,X)?
is road(X,Y)?
is road(Y,X)? 
.....

    You can replace the predicate:

    road(X,Y) :- road(Y,X).

    with

    road(X,X).

    and add:

    reachable(X,Y):-
     road(X,Y)
  ;  road(Y,X).

    and modify:

    route(X,Y) :- road(X,Y), \+ blocked(X,Y).

    to:

    route(X,Y) :- reachable(X,Y), \+ blocked(X,Y).