Charting Safe Passages Through the Urban Jungle with Big Data
When you visit a big American city for the first time, you probably wonder where it’s safe to go, and what areas it would be best to avoid. Wouldn’t it be great to have an app that advised you? Researchers recently demonstrated the viability of using big public data and innovative algorithms to recommend the safest, shortest passages through the city.
Three researchers from the University of Pittsburgh and Boston University recently published a paper titled “Safe Navigation in Urban Environments” that lays out a logical, data-oriented approach to tackling the challenge of navigating big cities in the safest and quickest manner. They used publicly available crime data from Chicago and Philadelphia–two megacities with reputations for street crime–and a collection of algorithms to help guide the way.
The SafePaths problem looks to find a balance between two primary variables: Crime risk and walking distance. While it’s possible to completely avoid areas of high criminal activity by charting a wide berth around them when going from point A to point B, that’s not a realistic solution. It’s a gray area, and people generally are willing to accept a slightly higher risk in exchange for a shorter route. City-dwellers balance these two variables all the time, and now researchers are expressing this complex equation in the language of data science.
The researchers started by importing OpenStreetMap data for Chicago and Philly and then loading them into a graph database where streets are defined as edges and intersections are defined as nodes. The Chicago SafePaths graph had 91,695 edges and 57,998 nodes, while the Philly graph had 82,676 edges and 55,234 nodes.
Then came the crime data. The researchers–Esther Galbrun and Evimaria Terzi from Boston University and Konstantinos Pelechrinis from the University of Pittsburgh–plotted the geographic coordinates of crime incidents to compute a spatial density for criminal activity. Then they took a function of crime incidents and the population density of a given area–as determined using “mobility traces” via call detail records and GPS traces–to come up with a crime density figure that reflects the probability of a person observing a crime for any given location.
One of the big challenges the researchers had to overcome was the “bicriteria optimization” aspect of the problem. Apparently, it’s not feasible to combine the length-of-path calculations with the crime-risk calculations into one algorithm. (Further complicating matters is the fact that the crime component was further split into two subparts, including the total probability of a crime happening on the route and the maximum risk of a crime occurring on any part of the route.) Instead, the researchers did the computations separately, and then combined the two result sets to come up with a “small set of paths that provide tradeoffs between the two objectives,” they state in their paper.
When put into action, the SafePaths algorithms return a group of paths that are the quickest and safest ways to get from point A to point B. Consider a hypothetical resident of Philadelpha who wants to walk from the Philadelphia Museum of Art (point S) to her home on Wharton Street (point T).
“Her shortest way to home is given by Path 1,” the researchers write. “However, according to the crime model…the itinerary indicated as Path 5 constitutes her safest option, which is also about 1.5 times longer than Path 1. Instead, our art lover may prefer one of the intermediate routes (Paths 2–4), that offer various tradeoffs between distance and risk.
It doesn’t appear that the researchers have any immediate plans to commercialize their work at this point. While the experiments demonstrate the efficacy of the algorithms and their practical applicability, they plan on fine-tuning their risk models by finding more data sources. They would also like to incorporate the time dimension into the calculations as well.