Course:CPSC312-2018-Dijkstra's-Algorithm

From UBC Wiki

Dijkstra's Algorithm

Authors:

Adrian Tang, Ford Atwater, Matthew Cam

What is the problem?

Our group is investigating the problem of logical decision making with Prolog.

One distinct way to represent decisions is by a graph – multiple types of relational data can be instantiated this way from data propagation to navigation to cost-effective purchasing.

To explore this, we are making an implementation of Dijkstra's algorithm using Prolog.

Route-Finding Optimization for Uber-like Service

We are creating locations in our grid upon a 'hail driver' function. It asserts a location and calls a destination, then finds a driver close-by using an aggregator. It's a slight enhancement on a Dijkstra's algorithm by asserting a position first and including that in the graph. For practicality's sake (so that our algorithm would work) we are saying that there are certain paths that can be chosen, existing outside of what we know about Vancouver. The program will then print out a list of the paths between real Vancouver locations that result in the destination.

Something extra?

The drivers selected are not based on shortest distance alone. Drivers with "no job" will receive priority, followed by drivers that are "able to pick up a second person." "Busy" drivers with a drop-off point a certain distance from the customer will receive third priority, and other drivers will receive the last. Also, we are able to tell if customers are really in Vancouver based on their latitude and longitude.

What did we learn from doing this?

We learned about applying our graph theory knowledge – directed vs bidirectional graph knowledge came into play, as we wanted to simulate "one way streets" along with regular ones. Also, we obviously used Dijkstra's Algorithm as the navigational mainframe for our entire project.

Data entry was critical as well: making our objective 'fit' with our algorithm was tricky: we went from coordinate-based data to more barebones 'roads' (edges). The coordinates still came into play, but not as we intended. First, a conversion function built by our team allowed us to turn coordinates into real distances between locations in Vancouver. Second, we used a coordinate system to assert a pickup location anywhere in a legal bound (a general square of the Vancouver area) and this allowed us to build dynamic nodes and edges for a driver to find where a customer is located.

Some of functions that we used that were new to us were 'setof', 'assertz', and 'retract'.

References

https://github.com/slavavikharev/Dijkstra-algorithm/blob/master/dijkstra.pro

Link to code

https://github.com/ajtang/CPSC312-PrologProject