With the track “urban innovation” and the stirring talk by Guy L. Steele Jr. on the ubiquity of computing, we were inspired to produce a public-oriented safety innovation that capitalizes on urban data. “Pathena” is the combinations of “Path” and “Athena,” the Greek goddess of wisdom, civilization, justice, and more. Our application seeks to optimize the safety of pedestrians navigating cities struggling with crime and misconduct. In terms of software design philosophy, we looked to make a platform that was both easily accessible and easily extensible via crowdsourced data.
What it does
Pathena differs from other navigation applications in that it doesn’t optimize solely on the basis of travel time/distance. Rather, Pathena takes into account the crime-rates of highly localized regions and factors this into the navigation route (specifically by modifying the algorithm used in the graph traversal of the map). In this way, Pathena balances an efficient route while prioritizing user safety.
How we built it
Challenges we ran into
In addition, our original method of creating a set of varying paths between point A and point B involved comprehensively permuting every single possible traversal that was less than a factor of 2 longer than the shortest possible path (by Dijkstra’s). The runtime for this selection however, was unreasonably high: understandably, a graph that represents a dense urban setting is highly connected, which results in astronomical numbers of possible traversals.
Though we resolved this by instead performing iterative Dijkstra’s algorithms while deleting key nodes in the route (forcing each iteration to find a new shortest path), we were then plagued by constantly deep-copying the graph for each iteration (as we did not want to mutate the original graph). The solution to this runtime-hog was to create a single copy, then re-add the deleted node after the traversal algorithm was applied.
We realized that scoring a path’s danger wasn’t as simple as finding the lowest sum of danger scores or the lowest mean -- it would be possible that the vast majority of the route was in safe areas but a tiny portion passed through highly dangerous zones. To account for this, we decided that minimizing standard deviation of danger scores would be important too, thus eliminating routes with sudden spikes of danger. Our final choice was to create a subset of the bottom 25% least dangerous routes by mean danger, then selecting the final route as the one with the lowest danger standard deviation across nodes from this subset.
Accomplishments that we're proud of
Using an API we were unfamiliar with to generate graphs that could then be used with a Dijkstra algorithm to determine the shortest and safest path from point A to point B.
Solving some of the computational/algorithmic/statistical problems we encountered in the above challenges
Using publicly available data to create a tool with clear and obvious impacts on citizen wellbeing.
Creating an easily extensible platform for finding safe routes in metropolitan areas.
Making a fairly polished end product in 24 hours.
What we learned
We learned how to deploy an app on the Google Cloud Platform and have it be publicly accessible.
Good planning and delegation leads to effective work management
We brainstormed on paper as a group, then split up work according to individual strengths and knowledge. The result was incredibly synergistic, and the product lies far beyond the sum of our individual strengths
Don’t get too attached to an algorithm -- as your project encounters various roadblocks and walls, you may have to abandon or modify your brainchild
Keep the energy up -- our group was grooving for the full 24-hours nonstop, and that energy absolutely contributed to our spirit and productivity
Care about what you’re working on: we chose a project that struck close to home, regardless of sponsored prizes, and we tried to compete appropriately in the category we were assigned to, despite it being outside of our general area of expertise.
Care about what you’re working on: we chose a project that struck close to home, regardless of sponsored prizes, and we tried to compete appropriately in the category we were assigned to, despite it being outside of our general area of expertise. Despite this, none of us have any regrets, we are very proud of this work!
If you need help, ask for it! Often a team member would run into a blockade, only for another team member to release it. Different approaches will help dismantle a tough problem!
Be generous with time when communicating complex ideas -- this will save you time later when your functions and algorithms play nicely with each other as planned!
What's next for Pathena
Pathena was created with long term goals in mind, and we have planned out some future goals. In addition to navigation, Pathena will have be able to collect crime/safety statistics in a region based on data crowdsourced from users and create more robust and widespread heatmaps. The goal is to preemptively warn users of their surrounding areas to give better safety insights. User-submitted social media data will be aggregated in addition to crime statistics to supplement the representation of the safety of neighborhoods where crime data published by local jurisdictions may be insufficient to accurately analyze the safety.