Update 1 – Optimization of Tribe Pathways

At this point in time, I have finished coding the core structure of the algorithm in python. Given a point on a map, the program will output the shortest distance from the start point to every other point on the map and record the path it takes to get there. For the next step in the project, I hope to organize the single script into a class with multiple functions contained within it. I have tested the algorithm enough to be certain that it functions correctly, but there may be some bugs in the programming I have not yet encountered. There is also a fair bit of optimization that could go into the program and there needs to be an easier way to input map data. That being said, with the small sample graphs I have been using, the results are almost instantaneous.

Output of program.

The program outputs the destination vertex, the shortest distance from the start point to the end point, and the steps along the path to reach it.

The algorithm works with a map of connected vertices. The paths between the vertices are non directional and weighted based solely on total distance. The information for this graph is stored in two separate lists: a list of the connected neighbors for every vertex and a list of distances between connected vertices. The program begins with a start point that the user inputs. From there, it will check all connected neighbors and determine the closest distance. At the start, the distance from the start point to every other point is set to infinity. Once the program finds the closest neighbor, it will update the distance to that point if it is less than the current value. The closest neighbor will then become the new start point and the previous start point will be marked as visited. The program will continue this loop checking only unvisited points until all points have been visited.

Graphical representation of map data.

Graphical representation of map data.

After considering multiple different algorithms, I found that Dijkstra’s worked the best for what I was trying to accomplish. With the exception of a small input error that set me back a day, the coding of the algorithm went smoothly. Implementing the code that would give the steps taken in the shortest path took some fiddling but ended up being very helpful in identifying problems with the algorithm. The next step in the project is taking a map of a selected part of campus and turning it into usable data for the algorithm. I hope to visit campus soon to record data on path features. I still need to add a feature which excludes paths based on a set of conditions but have decided this would be easier to add once I am using real data.

Comments

  1. Seems like a great project Ian! I hope you release the program when you finish as I could definitely see myself using it. As someone who bikes around campus, an option to avoid stairs is exciting.

    What are your criteria for what qualifies as a node? For example, every intersection of every path could count as a node, but that would be a large amount of data. Collecting that manually would take a long time, and the algorithm would take longer to run (though it may be an insignificant amount). Yet, that would produce the most accurate results. One way to speed that up could be collecting the distances from already available databases (e.g. Google Maps) and then adding in the terrain considerations manually.

    If you’re in for a lot of work, a potential feature you could add would be to time how long it takes to go from node to node and using that data instead of distance in your algorithm. Then you could accurately account for changes in elevation, terrain, etc. That could be sped up by having a default speed for level ground and only measuring each hill/staircase. For even more exercise, you could repeat those calculations on a bike.

    Good luck with the rest of your project! I look forward to more updates.

  2. Hello! I think your use of coding in real world situations is a great choice for a research project. Optimizing pathways is always a viable goal, as people (mostly students) who would be using these pathways are usually doing so with a specific destination in mind and a specific time in which to reach it. However, when you translate your work from the computer to the real world, there are some complications. Are you able to factor in obstacles (the Crim Dell, for instance) that may be in between two destinations, thus making the shortest path impossible? Or is this a part of the ‘set conditions which would cause you to exclude certain paths’ that you wrote about?

  3. Hey Ian this is a really cool project not to mention that it is very practical!

    I also share the questions of other posters about the consideration behind your node selection, but my main question is related to the algorithm that you are using. Perhaps I am misunderstanding it, but it seems like the way it currently runs there is a possibility that the shortest path is inadvertently missed. For example, if you have three nodes in the shape of a right triangle and choose your start point as one vertex of the hypotenuse and the endpoint as the other. The way I read it, the algorithm would find that the distance to the right angle is shorter, move forward to that point and then move to the end point. This minimizes the distance traveled between each vertex, but not the total distance traveled, since the shortest distance is simply traversing the hypotenuse.

    Unfortunately, if my understanding is correct, then that means for each path calculation you need to follow every “tree” to completion, which dramatically increases computational expense. Also unfortunately, I don’t have any particular solutions to offer you since I ran into a similar problem in my own research this summer. I just thought I might bring it up for consideration. But again, the project idea is really intriguing and useful! Great work!