Image Album

Inspiration

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

We used OpenStreetMap (OSM) to generate a graph of our selected area, selecting our initial nodes (regions of interest as classified by OSM) as the intersection of footpaths (edges). We then assigned edges/paths danger scores with police reports from the Berkeley Police Department. We filtered for crimes that were risks to personal safety and security that occurred in the last 6 months to generate the most focused heuristic we could. Next, we used Dijkstra’s algorithm (weighted by distance) to find the shortest possible traversal from point A to point B. We then iteratively deleted nodes and ran Dijkstra’s again, to create a set of alternative pathways (nodes were replaced before the next deletion). Once a sample of relatively short pathways were created between the start and end vertices of the graph, they were arranged by their weights in danger score rather than distance. The bottom 25% for mean danger score across nodes was selected as a subset, and from this subset, the route with the lowest standard deviation was chosen. The reasoning behind this was to avoid routes with low mean danger scores that potentially travelled (albeit infrequently) through extremely dangerous zones. This information was then combined with a Javascript frontend that employed the Google Maps API, to create an interactive web app.

Challenges we ran into

Angular was our first choice of front-end framework for Pathena, and we reached a significant progress until we ran into a challenge. Due to unidentifiable causes, our Angular build was not able to communicate with our Google Cloud server. After various attempts to fix, we decided that it would be the most efficient to port the Angular project to a Javascript based web application. Our decision turned out to be correct, and we were able to create a port quickly and stably.

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.

Built With

Share this project:
×

Updates