A Distance Transform Method for Finding Shortest Path in Robot Navigation

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.