A Star Algorithm

Path planning is considered as elementary task in autonomous mobile robot that allows the robot to find the shortest path from starting point to destination point.  Path planning has evolved with different types of algorithm and has moved from shortest to optimal paths.

Assumptions:

1.We are going to discuss the algorithms on the basis of grid graph, which has identical square shaped blocks.

2. Each block is denoted as node, moreover there is only single starting node and single destination node.

3. The location of starting and destination node is known.

Grassfire algorithm, as by its name, it begins from destination point, assigning each grid a value equivalent to the distance from the destination point spreading like fire in every direction.

It assigns the value '0' to the destination point, and value '1' to all the immediate surrounding neighbors.  

This step is repeated till starting point is assigned a value. Now the path is formed from the starting point to the destination point, according to the reducing value of distance. 

For example: if the starting point is assigned value '10' , then the path is formed in such a manner '10'-'9'-'8'...so on till '0'. 

Grassfire Algorithm is effective for small dimension grid graphs.

But as we increase the number of dimensions the complexity increases and thus we need a smarter algorithm which can find the shorter distance by visiting few and relevant nodes. 

A* algorithm also known as best first search algorithm  is one such algorithm which not only finds the shortest path but does it with less computational time. 

A* algorithm finds Heuristic function. It determines distance between a given node/current node to the goal node.

This information plays a vital role in the A* algorithm to search nodes which are nearer to the goal. 

A* algorithm computes function f , which is:

                                        

                                          f = g + h

where: g: the distance between current node and start node

            h: the heuristic cost  of current node

In every iteration it chooses nodes with the smallest f value or a node which is likely to be on shortest path.

Once node is chosen , f and g value is updated. This process is repeated until we encounter destination node or run out of nodes to consider.

A* is quicker than Dijkstra and Grassfire, due to its consideration of the heuristic distance. 

It might be wrong, but in many cases we can come up with informative heuristics that cause the algorithm to explore more efficiently.

We have coded the algorithm on MATLAB and its video is available on our YouTube channel 'Electro-Bugs'. 

Here is the link:

https://youtu.be/_V6-HSh5vDc

References:

'Robotics:Computational Motion Planning' course by University of Pennsylvania