A-Star Algorithm: grid

Generally, when we use A* algorithm, there are two approaches: we either use the adjacent list of nodes (example: we have a network of paved roads and we don't want our robot to drive anywhere else). This is also a more efficient approach, as we should only consider limited number of nodes, ideally, only road intersections.

Second approach places the regular grid on the entire map. It works when our robot explores the unknown area, or when it runs in the ourdoors crossroad environment (or when it cleans the parking lot and doesn't care about lines).

The grid has more nodes than the adjacency list, but it allows thorough exploration.

In this chapter, we are going to take a look at the grid approach, while the next chapter is dedicated to using adjacency list.

a_star.py

Grid based A* algorithm, especially when implemented using Python, has severe speed limitations. First thing that comes to mind is using NumPy to speed it up, second thing is using C++.

Note, that there is a 3rd possibility: we can use RRT (rapidly exploring random tree) algorithm, that yeilds (almost) the same result, but is signifficantly faster.