Optional Article: How the A* algorithm works

In the previous step, we implemented a new algorithm that can solve any instance of the path finding problem. This algorithm is called A*. In this step, we will go through some high-level description of this algorithm.

In this step I will talk about certain new concepts that you do not need to understand, but this is to explain how the code we provide to you works behind the scenes. I think this could be motivating to you to appreciate the beauty of algorithm design! You can write such algorithms in the future with further study and practice, but at this point the algorithm I will introduce is quite advanced.

Graphs

The A* algorithm uses the concept of a graph, which is a collection of vertices connected through edges. Graph theory is a branch by itself and is applied to numerous important problems, for example, Facebook uses graphs to represent relationships between people. The internet is a massive graph!

We can represent the robot environment as follows: vertices will represent the free cells in our environment, and edges will represent the possible actions of a robot from that cell to other cells. So, a cell will be connected to other cells if a robot can move from that cell to the other cells.

Consider the following environment:

It can be converted to a graph, and it will look something like the picture below. The squares are the vertices of the graph and the red lines are the edges connecting the vertices. Note that the occupied cells (marked with X in the figure above) are not part of the graph, and there are no edges to those cells (because the robot can’t move into them). You can now see a graph or a network, and A* algorithm will search through this network to find a sequence of cells that moves you from a starting vertex to a goal vertex.

A* also uses the concept of a heuristic, which is a function to estimate the cost of each cell in the network, so it can find a path that is optimal (or close to optimal). There are more algorithms for path finding, and graph theory is a very exciting subject! Again, you don’t need to understand this concept for this course.