Prolog - Calculate fastest travel between 2 locations given different travel modes

Help!
1

I’m trying to figure out how to calculate the fastest journey between two places, given different travel modes. My factbase starts with a predicate route(Src, Dest, Distance, TravelMode) and input is via the predicate journey(Src, Dest, TravelMode) which should output the fastest travel mode to use. (Basically whichever has the shortest time.)

However, it says that TravelMode is a string and if it contains f, it means the path can be traveled on foot, c for car, t for train and p for plane. This has me confused since I don’t really understand how to search the String TravelMode and only run the corresponding time functions for the travel modes included.

Below is my code and right now, it’s only able to calculate the time between places (time_f, etc), although I believe my time predicate is wrong since I think it’s supposed to be just one general function.

I also did try coding the journey predicate however, it only seems to output true / false and no values which probably means my route / speed predicate is wrong.

Am I on the right path? I’ve been stuck on this and I’d really appreciate any help to steer me in the correct direction / help explain what i’ve gotten wrong in here.

/* Sample set of facts */
route(dublin, cork, 200, 'fct').
route(cork, dublin, 200, 'fct').
route(cork, corkAirport, 20, 'fc').
route(corkAirport, cork, 25, 'fc').
route(dublin, dublinAirport, 10, 'fc').
route(dublinAirport, dublin, 20, 'fc').
route(dublinAirport, corkAirport, 225, 'p').
route(corkAirport, dublinAirport, 225, 'p').

/* Speed of mode of transport used */
speed(foot, 5).
speed(car, 80).
speed(train, 100).
speed(plane, 500).

/* Time between 2 cities, given specified transportation mode */
time_f(City1, City2, Time) :-
    route(City1, City2, Distance, _),
    speed(foot, Speed),
    Time is (Distance / Speed), 
    write('Time travelling between '), write(City1), write(' and '), write(City2), write(' via foot is: '), write(Time), nl.

time_c(City1, City2, Time) :-
    route(City1, City2, Distance, _),
    speed(car, Speed),
    Time is (Distance / Speed), 
    write('Time travelling between '), write(City1), write(' and '), write(City2), write(' via car is: '), write(Time), nl.

time_t(City1, City2, Time) :-
    route(City1, City2, Distance, _),
    speed(train, Speed),
    Time is (Distance / Speed), 
    write('Time travelling between '), write(City1), write(' and '), write(City2), write(' via train is: '), write(Time), nl.

time_p(City1, City2, Time) :-
    route(City1, City2, Distance, _),
    speed(plane, Speed),
    Time is (Distance / Speed), 
    write('Time travelling between '), write(City1), write(' and '), write(City2), write(' via plane is: '), write(Time), nl.


/* Solve for fastest journey */
journey(City1, City2, TravelModes) :-
    route(City1, City2, Distance, TravelModes),
    speed('TravelModes', Speed),
    Time is (Distance / Speed), 
    write('Time travelling between '), write(City1), write(' and '), write(City2), write(' via '), write(TravelModes), 
    write(' is: '), write(Time), nl.

Screenshot 1
Screenshot 1750×637 86.5 KB

2

Welcome.

If you double post a question, please note it in the post. :smiley:

Re: StackOverflow - Prolog - Calculate fastest travel between 2 locations given different travel modes

3

This seems familiar. I quick search finds: Recursive travel

1 Like
4

Oh my apologies regarding that!

5

I’ve been able to implement the rest of the other features as suggested by other users, however I still can’t seem to output the lowest time value. I don’t think its because I didn’t call the function since when I run all(Solutions). the output is just the same as that of find_min(MinimizedSolutions).

/* Sample set of facts */
route(dublin, cork, 200, fct).
route(cork, dublin, 200, fct).
route(cork, corkAirport, 20, fc).
route(corkAirport, cork, 25, fc).
route(dublin, dublinAirport, 10, fc).
route(dublinAirport, dublin, 20, fc).
route(dublinAirport, corkAirport, 225, p).
route(corkAirport, dublinAirport, 225, p).

/* Speed of mode of transport used */
speed(f, 5).
speed(c, 80).
speed(t, 100).
speed(p, 500). 

/* Checks if mode is in string */
availableMode(Mode, TravelModes) :- sub_atom(TravelModes,_,1,_,Mode).

/* Keep definition of journey but include a time variable that can be utilized */
journey(City1, City2, TravelModes) :- journey(City1, City2, TravelModes, _Time).

/* journey using time variable */
journey(City1, City2, TravelModes, Time) :- 
	route(City1, City2, Distance, TravelModes),
	availableMode(Mode, TravelModes),
	speed(Mode, Speed),
	Time is (Distance / Speed).
	%write('Time between '), write(City1), write(' and '), write(City2), write(' via '), write(Mode), write(' is: '),
	%write(Time), nl.


/* Collecting all solutions */
all(Solutions) :- findall([City1, City2, TravelModes, Time], journey(City1, City2, TravelModes, Time), Solutions).

/* Recursion to find minimum travel time */
/* Using the \+ (not provable operator) which discards the unnecessary solution */
/* Allowing us to retain the solutions with lowest time */
/* After recursively going thru the list, the accumulator list is set to the final solution list (aka the lowest time) */
minimize([],Sol,Sol).
minimize([S|Ss],SolAcc,FinSol) :- S = [Cy1, Cy2, _, _],
                                  \+ member([Cy1, Cy2, _, _], SolAcc),
                                  minimize(Ss,[S|SolAcc],FinSol).
minimize([S|Ss],SolAcc,FinSol) :- S = [Cy1, Cy2, _MyMd, MyTi],
                                  member([Cy1, Cy2, _OtherMd, OtherTi], SolAcc),
                                  OtherTi < MyTi,
                                  minimize(Ss,SolAcc,FinSol).
minimize([S|Ss],SolAcc,FinSol) :- S = [Cy1, Cy2, _MyMd, MyTi],
                                  member([Cy1, Cy2, _OtherMd, OtherTi], SolAcc),
                                  OtherTi >= MyTi,
                                  delete(SolAcc, [Cy1, Cy2,_,_], SolAcc2),
                                  minimize(Ss,[S|SolAcc2],FinSol).

/* Finding minimum solution */
find_min(MinimizedSolutions) :- all(Solutions),minimize(Solutions,[],MinimizedSolutions).
6

You can do the following:

Put the elements in a flat term, not a list. Instead of:

findall([City1, City2, TravelModes, Time], ...)

Write:

findall(path(City1, City2, TravelModes, Time), ..., Solutions)

Now it is even easier to sort on Time and just take the first:

sort(4, @=<, Solutions, [Fastest|_])

You could have sorted with lists but then you need to give a list to the first argument of sort/4.

I hope I am not misunderstanding your problem.

7

Hi! Thank you for this, so that means the minimize(, Sol, Sol) and onwards predicates are not needed anymore right?

I was reading the swi documentation for sort and I tried to follow it:

/* Collecting all solutions */
all(Solutions) :- findall(path(City1, City2, TravelModes, Time), journey(City1, City2, TravelModes, Time), Solutions).

/* Sort solutions by lowest time */
sort(Solutions, [Fastest|]) :-
sort(4, @=<, Solutions, [Fastest|]).

However, I seem to get an error of "No permission to modify static procedure ‘sort/2’

8

Yes, everything else is unnecessary.

You get the error because there is already a built in sort/2.

I don’t see why you need to wrap the call to sort/4 to be honest. But just rename your sort/2 to something else and it should work.

It seems to me, from looking at your code, that you are not finding journeys longer than a single “route”. Is that on purpose?

9

Ah I see, I’m quite confused sir Boris. That being if I were to not call sort/4, how would I be able to input journey(City1, City2, TravelModes) and have an output that were to state the path with the shortest time.

/* Collecting all solutions */
all(Solutions) :- findall(path(City1, City2, TravelModes, Time), journey(City1, City2, TravelModes, Time), Solutions).

/* Sort solutions by lowest time */
  sort(4, @=<, all(Solutions), MinimizedSolutions).

Also, yeah I’ve limited it only to single routes.