Abstract:
Finding shortest path for robot navigation is still a hot task in the present era. Among the
vast number of path finding algorithms, A* algorithm is one of the best and popular
technique. It finds shortest path by searching among all possible paths. The A* uses two
different parameters to estimate the cost while moving towards to the destination. The first
parameter is g(n) which is the cost for moving from the starting point to a vertex n, and the
second parameter is h(n) which is the heuristic cost value from the vertex n to the
destination. The standard A* algorithm calculates g(n) and h(n) every time while it is
moving from one point to another. In this paper, we propose a method to calculate the cost
g(n) using the distance transform values. Two different masks, forward mask and backward
mask, have been used to calculate the distance values from the starting point to all other
points in the image. Based on these values, the g(n) values for the A* algorithm are
calculated. Morphological operations are used to pre-process the image, and then
thresholding is used in order to differentiate the floor and obstacles. Then all the obstacles
are excluded from the image, and the distance transformation is used to find the g(n). The
results shows that the devised system works about 2% faster than the standard A* algorithm.
