GPS Navigation
What is GPS?
The Global Positioning System (GPS) is a satellite-based navigation system made up of a network of 24 satellites placed into orbit by the U.S. Department of Defense. GPS was originally intended for military applications, but in the 1980s, the government made the system available for civilian use. GPS works in all weather conditions, provided there is an unhindered line of visual perception communication with 4 or more GPS satellites. GPS is managed by the US Air Force. A GPS functions independently of the user’s internet connection or telephone signal. However, their presence increases the efficacy of GPS positioning.
The GPS system consists of three segments
The Space Segment : which includes the satellites and the transmitted signals.
The Control Segment : the ground facilities that carries out the task of satellite tracking, orbit computations, telemetry and supervision is required for the management of the space segment.
The User Segment : the whole spectrum of applications equipment and computational techniques that are available to the users.
The GPS satellite system
The 24 satellites that make up the GPS space segment are orbiting the earth about 12,000 miles above us. They are constantly moving, making two complete orbits in less than 24 hours. These satellites are travelling at speeds of roughly 7,000 miles an hour. GPS satellites are powered by solar energy. They have backup batteries onboard to keep them running in the event of a solar eclipse, when there’s no solar power. Small rocket boosters on each satellite keep them flying in the correct path.
Working of GPS navigation
GPS navigation or any other digital map divides it into hundreds of segments, with some only 24 meters long. A GPS visually examines this street as a graph divided into vertices and edges.
Breadth First Search (BFS)
There are differences in the route which I usually take and the one which GPS shows as the shortest, probably due to the algorithms used. I learned from my graph theory data structure classes that (BFS) Breadth First search example is GPS navigation and digital maps. I tried looking for the possible use of Algorithms (Breadth First Search example or A* application) used in GPS navigation on the web, but I couldn’t find a lot of details. So here is how Breadth First Search is used in real life application like GPS.
Let’s first understand working of GPS navigation
Digital maps, unlike humans, see streets as a bunch of nodes. The 33.55-mile road from vasai road to Narsee Monjee Institute of Management Studies. We (humans) consider this road a single entity (You may divide it into few more segments based on metro stations or intersections, but not more than that).
But a GPS navigation or any other digital map divides it into hundreds of segments, with some only 24 meters long. A GPS looks at this street as a graph divided into vertices and edges. There is a lot of data to be covered and calculated while finding the shortest path.
Graph Traversal in Maps
Take a look at this simple “Gridworld” which is used for various graph traversal algorithms. Your digital map considers your world a similar grid, which is made up of intersections connected to each other.
Now for the grid shown, there could be N number of ways to traverse from point A to point P.
Following are two of these N ways in which one can travel from point A to point P.
So how does an algorithm decide which the shortest way to reach a destination is? Graph Traversal Algorithms!
The Breadth First Search algorithm looks at the map as we do; it just can’t perceive it completely. When you have to travel from one destination to another, you draw a line from point A to point B, and then chose the road closest to that line. Algorithms repeat the same method choosing the node nearest to the intersection points, eventually selecting the route with the shortest length.
Let’s take a simple example of GridWorld given above and try solving it using Breadth First Search search. Assume you need to travel from location A to location P.
Note: Every vertex in the image is given a number, which is the total distance from the source and an alphabet which represents the previous node.
Breadth First Search for GridWorld
Step 1 — Visit neighboring nodes to A, i.e, B, E, and F. The vertex to B would become 1-A and since E and F are also at an equal distance as B, hence vertices to both E and F from A, could be denoted as 1-A too. There is the no particular order for node preference but to make it simple, we began with B.
Step 2 — Since all the neighboring nodes of A have now been traced, we will mark “A” as visited.
And take the next visited node as the source node, which in this case is node B. Visit all the adjacent nodes to B, which are C (2B) and G (2B). Node F is considered in the previous step from A, hence it is not visited again. Once all neighboring nodes from one node are visited, mark them as visited and move to the next step.
Step 3 — Visit all neighboring nodes of Node E, which are I (2E) and J (2E), and mark E as visited.
Step 4 — Visit neighboring nodes of Node F, which is K (2F). Since all the adjacent nodes have been visited by either B or E, mark node F as visited.
Step 5 — Repeat the process until all the nodes on the grid are visited at least once.
Step 6 — Once all nodes are visited, you would find that the distance required to reach from A to P is 3 and the shortest route is diagonal.
If you remove all the vertices which are not used to connect the nodes, as in the graph above.
Such graphs are called minimum spanning trees, where each node is connected to at least one vertex.
But in the real world, you can’t always move diagonally. Most of the portions in between the intersection are occupied by houses, shops, malls, and metro stations. So how does BFS work in such circumstances? Let’s understand it with the same GridWorld example, but in this case, the algorithm is not allowed to move or visit a node diagonally.
Step 1 — Consider node A as source and visit all neighboring nodes of A, which are B(1A) and E (1A). Mark A as visited.
Step 2 — Visit all neighboring nodes of B, node C (2B) and node F (2B), and mark B as visited.
Step 3 — Visit neighboring nodes to E, since F is already visited by B. Visit node I (2E) and mark E as visited
Step 4 — Repeat the steps for all nodes until each of them has been visited at least once. Mark nodes you considered visited.
Step 5 — Remove all the unconnected/unwanted vertices, and convert the graph into a minimum spanning tree connecting each node at least once.
– Highlight the nodes connecting source node A to node P, which has distance 6 and is the shortest path between two nodes.
You now understand why GPS navigation didn’t suggest the path A, E, I, M, N, O, P or A,B,C, D, H, L, P though they were equidistant.
Once you’ve understood the way GPS works, you’d wish the world could be a simple Grid! But to a programmer’s disappointment, it isn’t. Hence, for a GPS, distance is not the only factor in choosing a route, rather elapsed time, the speed limit on a route, live traffic update, the number of stop signals all has to be taken into consideration. That’s why you would find your GPS occasionally suggesting winding state highways to travel instead of the usual national highways.
Bellman-Ford Algorithm
Complexity theory, randomized algorithms, graphs, and more.
The Bellman-Ford algorithm is a graph search algorithm that finds the shortest path between a given source vertex and all other vertices in the graph. This algorithm can be used on both weighted and unweighted graphs.
Like Dijkstra’s shortest path algorithm, the Bellman-Ford algorithm is guaranteed to find the shortest path in a graph. Though it is slower than Dijkstra’s algorithm, Bellman-Ford is capable of handling graphs that contain negative edge weights, so it is more versatile. It is worth noting that if there exists a negative cycle in the graph, then there is no shortest path. Going around the negative cycle an infinite number of times would continue to decrease the cost of the path (even though the path length is increasing). Because of this, Bellman-Ford can also detect negative cycles which is a useful feature.
Imagine a scenario where you need to get to a baseball game from your house. Along the way, on each road, one of two things can happen. First, sometimes the road you’re using is a toll road, and you have to pay a certain amount of money. Second, sometimes someone you know lives on that street (like a family member or a friend). Those people can give you money to help you restock your wallet. You need to get across town, and you want to arrive across town with as much money as possible so you can buy hot dogs. Given that you know which roads are toll roads and which roads have people who can give you money, you can use Bellman-Ford to help plan the optimal route.
Graphical representation of routes to a baseball game
Instead of your home, a baseball game, and streets that either take money away from you or give money to you, Bellman-Ford looks at a weighted graph. The graph is a collection of edges that connect different vertices in the graph, just like roads. The edges have a cost to them. Either it is a positive cost (like a toll) or a negative cost (like a friend who will give you money). So, in the above graphic, a red arrow means you have to pay money to use that road, and a green arrow means you get paid money to use that road. In the graph, the source vertex is your home, and the target vertex is the baseball stadium. On your way there, you want to maximize the number and absolute value of the negatively weighted edges you take. Conversely, you want to minimize the number and value of the positively weighted edges you take. Bellman-Ford does just this.
Overview
The Bellman-Ford algorithm operates on an input graph, GG, with |V|∣V∣ vertices and |E|∣E∣ edges. A single source vertex, ss, must be provided as well, as the Bellman-Ford algorithm is a single-source shortest path algorithm. No destination vertex needs to be supplied, however, because Bellman-Ford calculates the shortest distance to all vertices in the graph from the source vertex.
The Bellman-Ford algorithm, like Dijkstra’s algorithm, uses the principle of relaxation to find increasingly accurate path length. Bellman-Ford, though, tackles two main issues with this process:
If there are negative weight cycles, the search for a shortest path will go on forever.
Choosing a bad ordering for relaxations leads to exponential relaxations.
The detection of negative cycles is important, but the main contribution of this algorithm is in its ordering of relaxations. Dijkstra’s algorithm is a greedy algorithm that selects the nearest vertex that has not been processed. Bellman-Ford, on the other hand, relaxes all of the edges.
Bellman-Ford labels the edges for a graph GG as
e_1, e_2, … , e_m,e1,e2,…,em,
and that set of edges is relaxed exactly |V| — 1∣V∣−1 times, where |V|∣V∣ is the number of vertices in the graph.
Algorithm Psuedo-code
The pseudo-code for the Bellman-Ford algorithm is quite short.
This is high level description of Bellman-Ford written with pseudo-code, not an implementation.
for v in V:
v.distance = infinity
v.p = None
source.distance = 0
for i from 1 to |V| — 1:
for (u, v) in E:
relax(u, v)
The first for loop sets the distance to each vertex in the graph to infinity. This is later changed for the source vertex to equal zero. Also in that first for loop, the p value for each vertex is set to nothing. This value is a pointer to a predecessor vertex so that we can create a path later.
The next for loop simply goes through each edge (u, v) in E and relaxes it. This process is done |V| — 1 times.
Relaxation Equation
Relaxation is the most important step in Bellman-Ford. It is what increases the accuracy of the distance to any given vertex. Relaxation works by continuously shortening the calculated distance between vertices comparing that distance with other known distances.
Take the baseball example from earlier. Let’s say I think the distance to the baseball stadium is 20 miles. However, I know that the distance to the corner right before the stadium is 10 miles, and I know that from the corner to the stadium, the distance is 1 mile. Clearly, the distance from me to the stadium is at most 11 miles. So, I can update my belief to reflect that. That is one cycle of relaxation, and it’s done over and over until the shortest paths are found.
This is relaxation equation.
Relax Equation
relax(u, v):
if v.distance > u.distance + weight(u, v):
v.distance = u.distance + weight(u, v)
v.p = u
Detecting Negative Cycles
A very short and simple addition to the Bellman-Ford algorithm can allow it to detect negative cycles, something that is very important because it disallows shortest-path finding altogether. After the Bellman-Ford algorithm shown above has been run, one more short loop is required to check for negative weight cycles.
This pseudo-code is written as a high-level description of the algorithm, not an implementation.
for v in V:
v.distance = infinity
v.p = None
source.distance = 0
for i from 1 to |V| — 1:
for (u, v) in E:
relax(u, v)
for (u, v) in E:
if v.distance > u.distance + weight(u, v):
print “A negative weight cycle exists”
Complexity
Worst case time complexity: Θ(VE)
Average case time complexity: Θ(VE)
Best case time complexity: Θ(E)
Space complexity: Θ(V)
Applications
A version of Bellman-Ford is used in the distance-vector routing protocol. This protocol decides how to route packets of data on a network. The distance equation (to decide weights in the network) is the number of routers a certain path must go through to reach its destination.
For the Internet specifically, there are many protocols that use Bellman-Ford. One example is the routing Information protocol. This is one of the oldest Internet protocols, and it prevents loops by limiting the number of hops a packet can make on its way to the destination. A second example is the interior gateway routing protocol. This proprietary protocol is used to help machines exchange routing data within a system.
