The objective of this exercise is to learn A*.

The problem of planning a path given a start and a goal position is called the path planning problem. We often encounter such problems in the area of mobile robotics where the goal is to give the robot the ability to determine how it should navigate from its current location to some desired goal position. As such, we must consider the robot’s start and goal positions as well as the geometry of the environment, i.e. the location of the obstacles, the size of the obstacles, and the such. (This is also a common problem in video game design where the programmer must be able to compute the trajectories that the numerous characters follow in a game.) There are numerous existing methods that can be employed to solve the path planning problem. A common approach is to tesselate the workspace into cells. Once the workspace has been properly discretized, one can represent the layout of the workspace using what is called an occupancy grid. An occupancy grid is simply a data structure used to encode the layout of the workspace. One can interpret the occupancy grid as simply a map of the environment where free space is represented by clear cells and occupied space, i.e. space where obstacles reside, is represented by solid cells. Figure 1(a) shows an occupancy grid for a workspace that has been tesselated into cells of varied size and shapes while Figure 1(b) shows an occupancy grid obtained using a fix grid decomposition of th