Localizing with Google Maps
Recently, while seeking refuge from Hurricane Ida’s path, I was hit with a bout of anxiety. This pang emerged while using Waze on my smartphone. Here I was navigating the outskirts of Atlanta, relying on a technology I have trusted for at least a decade and somehow the app filled me with dread, a dread outside the fallout of Ida. This feeling came from trying to understand how Waze worked.
This curiosity provided an intersection between my ongoing education into algorithms and my explorations of big data and its inherent concerns. Thinking about what it would take to make an app detailing the shortest distance between any two point at any time that must update in real time with a razor-thin margin for error, where consumer trust could erode in an instant in the case of a inefficient or incorrect route. This small handy utility, revealed itself to be a tiny behemoth and within that behemoth lies all the usual suspects in tech: machine learning, user-sourced data, privacy concerns, and the tradeoffs consumer make for convenience.
GNSS
Global Navigation Satellite Systems (GNSSs) are the engines that allow for geospatial positioning that enables the baseline for navigation technology. GNSS are a collection of satellites that contain an atomic clock and send radio waves of time signals with high precision to electronic receivers, that detail positional data between the satellite and the receiver such as longitude, latitude and altitude using trilateration.
The USA’s Global Positioning System (GPS) is the most commonly used GNSS around the world explaining it being a colloquial synonym to GNSS. GPS was initially developed for military use as an update to radio positioning technology such as TRANSIT and LORAN in the 1970s. It was eventually approved for joint civilian and military use in 1994 and currently has 32 satellites in orbit. Other GNSS are the Russian (former Soviet) GLONASS launched in 1982 with 24 satellites currently orbiting, China’s BeiDou which launched in 2000 and has 16 satellites, and the EU’s Galileo which launched in 2011 and currently has 22 satellites in usable condition.
Localization is a term used to describe locating a phone/user in space. For applications such as Waze and Google Maps to be optimized for user experience and application accuracy many positioning strategies are used on top of GNSS to localize the phone. A limitation of GNSS is that it can take time for a radio signal to reach a receiver and in certain areas such as dense urban areas the signal will not be strong enough to pass through building. Technologies such as Augmented GNSS which uses a receiver and a server to send cached signals that may be lost on the way to a mobile receiver. Other methods of creating precise location data are utilizing the user’s cell network, hybrid positioning systems, WIFI, or nearby hotspots for position.
GNSS locates a user’s phone in space, the point of navigation is finding a path between at least two points. While the exact algorithms used to generate routes on Google Maps and Waze are not readily available thanks to the complexity of concerns involved in real-time navigation, looking at common shortest path algorithms still gives some insight to how routes are calculated. When it comes to shortest path algorithms Dijkstra’s algorithm and its variations are the baseline standard.
Dijkstra’s algorithm
Dijkstra’s algorithm is a shortest path algorithm developed by Dutch engineer Edsger W. Dijkstra in 1956. The algorithm takes a graph node and calculates this graph node’s distance from every other node on the graph via number values set on the edges of the graph. Taking the starting node or vertex, the algorithm visits the unvisited neighbor nodes and takes into account the edge values. Additionally the algorithm implements a priority queue that orders the paths to these neighboring vertices prioritizing the path with the edge that has the lesser edge value.
Once every neighbor of the current vertex is visited, the current vertex is retired and the neighbor next on the priority queue becomes the current vertex and the algorithm runs again skipping any vertex that is already visited and retired. The value of the edges, starting at the original parent vertex are retained according to path and compounded until the destination is reached to compare which path is the shortest.
At each junction of the Dijkstra’s algorithm the most locally optimal choice is made for traversal making the algorithm a greedy algorithm. This fact makes Dijkstra’s algorithm not always the most efficient because it has no concept of the direction you may be going or what weights to disregard in order to get to a path quicker. If the edge value is lower, that is the direction the algorithm will lead. For this reason, augmentations of Dijkstra’s algorithm are utilized to to increase the efficacy to that shortest path.
One common iteration on Dijkstra’s algorithm is the A* (A star) algorithm which introduces an additional heuristic to Dijkstra’s algorithm which is some sort of way to measure the distance between the starting vertex and the destination, such as using the Pythagorean theorem to calculate the distance, and applying that knowledge to assist in the making choices in how to proceed through the graph. To optimize A* the heuristic used to calculate distance must be precise because underestimation and overestimation of the can invalidate the choice-making process afforded by A*. With A* the priority queue is calculated by how far a path is from the original parent node and far there is still to go to reach the destination node. Thus overall distance to the destination is considered and moving farther away instantly disregards unfruitful paths.
While neither of these algorithms are exactly how Google Maps or Waze calculates distances, theses concepts of priority queues and heuristics to measure weights are the baseline for calculating distance and demystifies the work that goes into calculating shortest distances between paths.
localization and google
After localization, finding the shortest path between a user’s starting point and their destination is the second step. This step still dates this endeavor by two decades to when I printed out MapQuest directions to navigate my mother to my sisters away games. In the epoch of the mobile internet and GPS receivers in every cell phone, consumers have relied on and expected persistent and dynamic navigation that incorporates user experience in their navigation applications and finally this is where Google barges in.
Google’s mission is simple and it is readily available, “Our company mission is to organize the world’s information and make it universally accessible and useful.” This dedication to the pursuit of information is evident in the Google Maps project. In order for maps to work as it does it takes in alot of information. As Harold Stark writes in, “Since You Asked Here’s How Google Maps Really Works,
For its basic geological map, Google depends on its Base Map Partner Program, which collects information from a range of credible organizations, such as the US Geological Survey, Forest Service, city and state councils and so forth, using them to construct everything from massive freeways to remote lanes and stitching them together into the comprehensive digital image that we call Google Maps.
This is for its base, additionally, Google generates and implements data gathered by other ventures such as Google Street View and Google Earth to gather information to supplement this base information. On top of this, walking, metro, and biking routes are also calculated using sourced information. Throughout, I have used Google and Waze in conjunction and that is because Waze is yet another acquisition that supplements Google’s data even further by its integration of user-submitted information such as where stalled cars are located and last known speed traps.
This cocktail of data and variables, pooled together with all the location data that google maps users readily contribute, go into calculating up-to-date ETAs. This is made possible through the use of Graph Neural Networks (GNNs) which we can think of in relation to the edges and heuristics of the Dijkstra and A* algorithm’s. In collaboration with yet another subsidiary, DeepMind, Google uses Machine Learning graph models to anticipate changes to traffic to factor in these weight before accidents or traffic jams occur.
Spelling out how Google Maps works underlines Google as a true behemoth of information. The breadth of this topic has not even left space for the potential insidious nature of how much user location data is used to power this technology. Within that is the tradeoff that allows for the incredible applications of Waze and Google Maps and too numerous to name Google technologies and solutions that power more of our experiences than we realize. It is still a humbling tradeoff that shifts my anxiety from Google Maps and Waze to Google, this incredible titan of information.