Preventing Sexual Harassment by Finding the Safest Route using Nearby Search, Directions API and Grid Coverage Techniques
Creating an algorithm to find the fastest way to reach a safe place in case of an emergency.
This piece closely follows Angelo Antonio Manzatto’s article on predicting sexual harassment by generating a heatmap of safe and unsafe spots.
If you haven’t seen this one or like to have a refresher on what the first part of the AI challenge is about, I’d advise you to check it out! The gist of it is that we’re able to predict locations that are of higher risk of sexual harassment using convolutional neural networks (specifically, the ST-ResNet framework).
With much of the leg work completed with the heatmap, we still face part two of the challenge, which was to address the following:
The combined data can be used to create an algorithm to find the fastest way to reach a safe place in case of an emergency.
While the heatmap generated is very useful and assistive in informational settings, we’re still tasked with the problem of how we can use and act upon such data to make the overall user experience more agentive — that is, how do we determine the best route to take on behalf of the user.
To begin tackling the problem, we can break it down into smaller, more manageable bite-sized pieces of tasks:
- Find ‘safespots’ relative to a user’s coordinates
- Find directions to so-called ‘safespots’
- Compute the risk associated with getting to each ‘safespot’
Finding ‘safespots’ relative to a user’s coordinates and directions to those places:
Teams at Omdena concurrently work on multiple tasks — given that this task depends on the output of the heatmap, let’s take a look at what we could be facing by simulating some hotspots, so we can get this task going and plug-n-play when the actual heatmap is ready:
Again, this heatmap layer generated using gmaps Python package is completely simulated, but it does give insight into what potentially we could work with. Next, we need to find nearby ‘safespots’ and walking directions to those places. Thankfully, we can leverage Google’s Maps API for this — that is, the combination of both Nearby Search and Directions API :
To quickly detail what was done here:
- Used
Nearby Search APIto find the nearest hospitals within 800 meters Nearby Searchresponse is a list of coordinates for these locations and we then useDirections APIto find walking directions to these places
I won’t go into the specifics of making requests to these services, and if you do want to take a look and try it out on your own, check out here for theNearby Search API and here for the Directions API .
At this time, my fellow team members informed me they have pushed a working version of the heatmap model and that I was able to incorporate a first version of the heatmap; so away with the simulated heatmap and here is what it actually looks!
A few quick points about this figure:
- Given latitude, longitude boundaries and a 28 by 28 array of risk scores, we interpolate the specific coordinates of each spot or ‘grid point’ to create this lattice-looking overlay (coordinate calculations done using haversine)
- Risk scores are discrete, ranging from 0 to 4, with 0 being the safest of spots and 4 being the most dangerous
- Area of each ‘grid point’ works out to be ~1.74 km² (which is fairly large, meaning the resolution isn’t the finest)
Let’s now superimpose the directions layer on top of this and see what we’re working with:
As you can see, various hospital locations are located within 800 meters; however, it is quite intuitive to any user looking at this to avoid the top-side locations, since the risk scores are higher (illustrated by warmer colors). Looking at this, one can simply make a decision on where to go by:
- Prioritizing the overall route safety-ness
- Choosing the closer location
Computing the risk associated with taking each route and finding the safest:
However, in times of where the user is in stress and needs to make a decision immediately, such cognitive abilities come as a luxury (this is akin to determining which route to take with only traffic data provided). The application should complete these tasks for the user, and thus we’ve come to the crux of the problem:
How can we determine the safety-ness of routes?
Again, working our way from simple to more complex solutions, we can:
- Determine overall route safety-ness solely by the risk score associated with the destination
- Calculate the average of risk scores based upon grid coverage of the straight-line path from origin to destination
- Calculate the average of risk scores based upon grid coverage of each step of the route to get to the destination
Completing the first solution isn’t too complicated — in short, you have coordinates for each grid point and finding the grid point that is closest your destination to obtain its risk score involves finding the one with shortest Euclidean distance (here we use a linearized method and assume there’s no curvature between points for simplicity).
Taking on the second and third solutions requires leveraging external resources — we can reframe this problem as one that involves determining the line-of-sight. For example, how can a one determine if their vision is blocked by obstacles; in this context of finding the best route, how do we know if a route touches a grid point? Equipped with the knowledge that there’s pretty much an algorithm for everything, we turn to Bresenham’s line drawing method.
Bresenham’s line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points.
Computer graphics work in units of pixels, so we can see how this algorithm originated from the need to shade in pixels graphical operations.
The general idea behind this algorithm is: given a starting endpoint of a line segment, the next grid point it traverses to get to the other endpoint is determined by evaluating where the line segment crosses relative to the midpoint (above or below) of the two possible grid points choices
As an attempt to walk through this method, we’ll study the following diagram:
- Here, we assume the points refer to each grid point (which are the centre point for each grid box)
- Assume we have a line segment spanning from left to right in upward slope fashion (smaller
(x, y)to larger(x, y)coordinates). Let's also say that the initial grid pointPis shaded and has already been determined to be traversed through - Consider point
Pas the previous grid point, we then need to determine the current grid point to be shaded. To do so, we also consider the grid pointsEandNE(for east and northeast of the current grid point, respectively) Mis the midpoint betweenEandNE- Based on where the line segment intersects between the line between
EandNEand the point of intersection relativeM(above or belowM), we can make a decision on the current grid point that the line traverses through, which isNEin this case, as the line intersects aboveM - The grid points
EandNE(and consequently,M) are then updated in reference to the current grid point and the same methods above are applied again and again until we reach the opposing endpoint of the line segment
When we complete the process, we arrive at something like this:
Fortunately, we need not code this out from scratch as skimage already has an implementation of this — here’s a small snippet of what the code looks like:
from skimage.draw import line
import matplotlib.pyplot as plt# create array of zeros
example_arr = np.zeros((10, 10))# set endpoints for line segment
x0, y0 = 1, 1
x1, y1 = 7, 9# draw the line
rr, cc = line(y0, x0, y1, x1)
example_arr[rr, cc] = 1# plot it out
plt.figure(figsize=(8, 8))
plt.imshow(example_arr, interpolation='nearest', cmap='viridis')
plt.plot([x0, x1], [y0, y1], linewidth=2, color='r')
As you can see, the approximations of the grid point shading are imperfect, as there are definitely grid points that the line has crossed that are not shaded in.
Of course, there’s another algorithm to improve on this where all of the points that are crossed are shaded in; I won’t go in detail here but the term used is to find the supercover of the line segment:
Zooming back out to our problem at hand here, we apply these grid coverage methods to compute the average of risk scores of steps for each route to determine the best. We prioritize the safety of the route first, before accounting for the distance (i.e. the safest route is suggested first if two routes are tied in safety-ness, we then suggest the closer destination).
To top it off, we apply this method to our heatmap to illustrate how one route could look like:
Funny enough, we actually couldn’t make use of the line drawing algorithms in this particular scenario given the rough resolution of the heatmap data. If you recall, each grid point covers approximately 1.74 km² in area; it is highly unlikely that each step of the route would span longer than this and thus we don’t see a line segment cutting across multiple grid points.
Nonetheless, this method and approach still hold — with the accumulation of more data and a finer resolution heatmap, we’ll be able to enjoy the effectiveness of these algorithm implementations. Lastly, I do want to remind readers that the methods implemented here serve as a starting point, where the beneficiary non-profit organization Safecity can draw further ideas and inspiration from.
To productionize such implementations, more development and testing would need to be done to ensure that the user experience is satisfactory.
Concluding Remarks
With that said, I’d like to conclude by saying it was a wonderful experience working and collaborating with individuals all over the world. I truly feel humbled by the fact that there are countless passionate individuals looking to making a social impact through technology.
To be frank, our weekly meetings are at a time not exactly ideal to where I reside (early Sunday mornings), however, the realization that my team members are so eager to share their progress and contribute to the cause serves as instant caffeine for me.
Thank you, collaborators, Omdena organizers and of course Safecity for instilling confidence in us and inspiring us to do good with tech!
Want to become an Omdena Collaborator and join one of our tough AI for Good challenges, apply here.
