Course:CPSC312-2017-Route-Optimizer

Shortest Path

Authors: Claire, Ford, Madeleine https://github.com/madeleinefrancis/PrologMap

What is the problem?

Find the shortest path, in terms of time, between popular locations in Vancouver using Dijkstra's algorithm. User can choose whether they would like to walk, bike, drive, or take transit.

What is the something extra?

Implement rich natural language querying for the user.

What did we learn from doing this?

It was very simple to represent a graph in Prolog given the fact that the language defines relations. A graph is essentially a map of relations between objects, and in our case, nodes which are related by weighted edges. The relations we were trying to represent were very simple, so Prolog was just fine for the task in that sense. We did not need to worry as much about the confines of data structures, as can be the case in other languages. We were able to create a representation however we wanted.

At first we attempted to create queues in working memory to keep track of lists of visited nodes, as well as the the shortest paths with accumulated length values as we recursed through all the nodes. This was done using assert/1, and assertz/1 to add to bottom of queue, and retract/1 to remove. Although this was an interesting approach to the problem, it became overcomplicated. The assert stacks were leading to inconsistencies with running the program since they essentially work like global variables, which makes programming quite hairy. What makes logical programming attractive is partly that not keeping state means everything is safely reusable. We found that there were simpler solutions.

Since Prolog finds all possible solutions to a clause, it was convenient to use to find the shortest path. We simply ran the program and found the smallest path within the set. Because we are using rules and facts to define the solution, our program ends up being much less verbose than if we were using an object-oriented approach.

Because the program is stateless, this means that the user cannot really interact with the program and change any data. This is actually fine in our case because our graph is representing what is true about geographical locations. Someone who is simply looking for the shortest route somewhere is probably not needing to change the map in any way.

We also created a simple natural language interface to the route finder. This allows the user to query it for the shortest path of nodes between points A and B and the total time it takes to complete the journey. The user can ask questions like "how do I bike from here to there?." We then used Prolog to parse the query and then call the algorithm that returned a sentence describing the shortest path and the trip time. Prolog was useful for this functionality because it can easily parse the grammar of the query and then return facts about the relation between places.