(It will be at least better than Apple Maps) Nathan Faber (He/Him) and Zoë McGinnis (She/Her) Saprina Pereira (She/Her)
This project seeks to look at optimal path planning given a weighted graph. We will be doing this within the scope of Olin and walking around Olin. This will be an implementation and theory based project. We plan to get real world measurements of Olin to keep the project grounded. In essence we are hoping to make a “Google Maps” for Olin’s campus. We will start with some research into how routing algorithms like Google maps/GPS work to understand how this problem is approached and simplified. We will then switch to making our own implementation based on our findings. We will also do some analysis on how this performs in response to a brute force method and how it would scale (time and space complexity). We will culminate this project in an interactive slideshow and/or video in which we compare and contrast the different methods of path finding, as well as how the problem changes when additional variables are added (i.e. stairs).
Proposal: April 11 Week 1 (12th-18th): Create a Github, research data collection for elevation/distance keep notes/write into theory for report Week 2 (19th-25th): Implement Graph in python and solve brute force method (backtracking?) Start/decide on more complex algorithm, specify project scope and the rest (directed graph, multiple weights etc) Week 3 (26th-2nd): Completing algorithm(s), collecting more data as needed Week 4 (3rd-9th): Video/report making, visuals and polishing! Gifs in Github pages May 10: Project due
Undirected Graph with just distance (weight) between nodes Path calculation between 2 points in better than brute force time Visual representation of our graph! (Using networkx) Final deliverable fits in on a portfolio! (Github pages?)
Directed graph (take gravity into account when considering ease of travel) Route calculation (a chain of points) Multiple algorithms compared (aka more lookup tables etc) Visual representation onto Olin google maps image 3D? Take into account elevation
https://en.wikipedia.org/wiki/A*_search_algorithm https://realitybytes.blog/2017/07/11/graph-based-path-planning-dijkstras-algorithm/ https://realitybytes.blog/2018/08/17/graph-based-path-planning-a/ http://correll.cs.colorado.edu/?p=965