We observe it everywhere in our daily lives: finding the shortest path between two locations. Whenever you traverse from one location to another or while playing a game where we are desperate to reach/find the goal mission timely.
Efficient path-finding algorithms are at the heart of data structures and algorithms in Computer Science. Their applications are widespread, ranging from traffic information systems to internet routing. Algorithms for finding the shortest path between two points are universally applicable.
It is herein where these algorithms assume considerable importance. Through this project, we intend to introduce two very well known path-finding algorithms, namely, Dijsktra’s Agorithm and A*Search . Following an introduction to both the algorithms, we will compare them by exploring each one with a game.
Before we delve into the algorithms, let us visualize path-finding. The following simple game shows how path-finding can be visualized. The game below has a sand-terrain. Click on any point on the graph. This is your starting point. Click on some other point. This is your ending point. Now see what happens, as we explore the possible paths from the start to the end, we expand points along the way which is shown as the animated purple patch. The final path is highlighed when the traversing and exploration is done. So how did we get this path? It is this question that forms the crux of our analysis!
Graph:
Frame Delay: 3.00s
Dijkstra’s Algorithm seeks to find the shortest path between two nodes in a graph with weighted edges. As we shall see, the algorithm only works if the edge weights are nonnegative. Dijkstra’s works by building the shortest path to every node from the source node, one node at a time. The nodes and edges that are part of shortest paths are colored black.
At each step in the algorithm we find the shortest path to another node. But how do we know which node is next? Nodes that are just one edge away from the shortest paths seem like good candidates. These nodes form the fringe and, together with the edges connecting them to the shortest paths, are colored bright red in our visualization. The fringe nodes and their costs are visualized in the priority queue below the visualization. This queue orders the fringe nodes by their total cost.
We calculate the cost of going from the source to a node in the fringe by summing edge weights along the black edges and then finally along the bright red edge connecting the node to the shortest paths we already have. If we pick the node with the shortest total cost, we can be confident that we have found a new shortest path. This is because any other possible path to that node will have to pass through a different node in the fringe, but that node is already further away from the source than the node we selected! (Note: This argument crucially relies on the fact that moving along edges can only increase the total cost. The negative graph shows an example where Dijkstra’s fails if there are negative edge costs.)
After we have selected a node and corresponding edge to add to our shortest paths, we need to update our knowledge about the rest of the graph. A node that is transitioning between the priority queue and the shortest paths is colored in darker red. To do this, we follow the edges from the node we just added and check whether our path to that node is shorter than any other path to it we’ve seen so far. If it is, we update the edge leading to that node (turning the old one dark red and the new one bright red) and add it to the priority queue, otherwise we make the edge dark red and continue on.
These two stages, adding nodes to the priority queue and removing the one with least cost, take turns until we finally add our target node to the shortest paths. Once we’ve done so, we can track the black edges back to the source to find the shortest path.
The visualization shows two alternating phases. In the first phase, nodes are placed on the fringe and the previously popped node is put on the shortest path tree. (Since there is no previously popped node the first time, nothing is put on the shortest path tree at the very beginning.) In the second phase the node with the least cost is removed from the priority queue and its neighbors are put into the priority queue.
To navigate the visualization, a good first step is to track the lifecycle of a particular node. Nodes begin unexplored (gray). If a node is visited by Dijkstra’s algorithm it is placed on the priority queue (bright red) and will eventually be removed (dark red) at which point its edges will be explored. Finally, the node will be added to the shortest paths (black).
Edges have a different, but related lifecycle. They also begin unexplored (gray), but when Dijkstra’s examines an edge it may color it either bright or dark red depending on whether or not the algorithm thinks it is part of a shortest path. An edge will become black if Dijkstra’s thinks it is on the shortest path and has also determined that the node the edge points to should be added to the shortest paths.
Instructions:
We recommend going from (2,1) to (3,0) on grid.
If you’re interested, here’s pseudocode for Dijkstra’s Algorithm:
Graph:
Frame Delay: 3.00s
Although Dijkstra’s Algorithm can always determine the shortest path from a source to a target in any graph with nonnegative edge weights, one wonders if we could do better by using information about our problem to inform our graph search. Indeed, usually when we want to find the shortest path between two nodes, we are doing so in a graph that models something like distance or time between locations.
Imagine you are trying to get from one end of a football field to another. Being a computer-minded individual, you decide to divide the field into squares, and construct a graph like the grid example above where each node is a square and each edge is the time it takes to move from one square to another. If you chose to run Dijkstra’s on this grid, it would see each direction as equally likely. It makes no difference to the algorithm whether you go forward, back, left, or right. The algorithm will explore each of them in turn. But we know that some of these directions are clearly worse than others! In the next section we will explore ways to modify Dijkstra’s to take into account problem-specific information that can help us solve problems like these in less time.
We now turn our attention away from an algorithm works pretty well on all graphs and towards an algorithm that can be tuned to work really well on graphs we’re interested in. We will combine Dijkstra’s algorithm with a custom heuristic that can be tailored to our specific problem.
A heuristic is an intuitive approach to problem solving. It is an instinct about what makes sense mathematically and could be applied to solve a problem faster when traditional methods to solve the problem fail. In location-based search and path-finding problems, for example, a heuristic might be some essential information about how close a node is to our desired destination. Thanks to the laws of nature, we know that on a flat surface the shortest distance between any two points is a straight line. The straight-line distance from a node to the target gives us a good estimation of how much farther we might actually have to go on a graph that encodes distances as edge weights. Adding our estimate for the distance we have left to the distance we traveled from the source gives us a better approximation for how costly a shortest path going through that node might be. Crucially, if we want to ensure that the path we find is the shortest, our estimated cost must underestimate the true cost. Otherwise we could run into the same problem that Dijkstra’s had with negative edges. If a heuristic always underestimates the true cost, it is called an admissible heuristic.
The following pseudocode illustrates A*Search. Notice that the only difference between Dijkstra’s and A* is that we add the heuristic to the cost we use to order nodes in the priority queue.
This visualization is nearly identical to the one above. The only difference is that the priority queue now adds the straight-line distance to cost of a node when it sorts node on the priority queue. You can now think of edge weights as encoding distances, and in fact the simulation ensures this is the case.
Note: The white labels on the bars in the priority queue show the sum of the Dijsktra node cost and the straight-line heuristic. We recommend going from (2,1) to (3,0) on grid.
Even though admissible heuristics guarantee A* will produce a shortest path, sometimes we care more about speed than getting the absolute best answer. In this section, you will explore tradeoffs between accuracy and speed.
Now that you know the basics of search algorithms and heuristics, it’s time to play aStarCommando!
In this game, you are a commander trying to move your platoon to a safehouse.
You can call in a vehicle of your choice, but you have limited fuel, so it is vital that you choose sensible transportation and find a short route to the safehouse. To find a route, you will send out scouts to explore the terrain; scouts are dispached whenever your search algorithm expands a node. To complicate things further, your scouts have a limited time to search before an airstrike is called in on your platoon, so your search algorithm cannot expand too many nodes.
As Commander, your job is to fine tune a search heuristic to dispatch scouts and lead your platoon to safety. You can control how much distance, as well as certain types of terrain, affect your search. Leaving aStar search unmodified will always produce the shortest path, but expands far too many nodes. In addition, turning up the distance multiplier can dramatically reduce node expansion, but finds expensive paths, while turning it down to zero will run Dijkstra’s Algorithm. You must find a balance between these two extremes to succeed. Good luck soldier!
Difficulty
Terrain
Vehicle
Distance Multiplier
1.00Delay 5.00
Deviation from Exploration Costs:Grass 0.00
Snow 0.00
Sand 0.00
Dunes 0.00
Pine 0.00
Wood 0.00
Rock 0.00
Dirt 0.00
Ocean 0.00
Coast 0.00