Robotic path planning in static environment using hierarchical multi-neuron heuristic search and probability based fitness

Path Planning is a classical problem in the field of robotics. The problem is to find a path of the robot given the various obstacles. The problem has attracted the attention of numerous researchers due to the associated complexities, uncertainties and real time nature. In this paper we propose a new algorithm for solving the problem of path planning in a static environment. The algorithm makes use of an algorithm developed earlier by the authors called Multi-Neuron Heuristic Search (MNHS). This algorithm is a modified A* algorithm that performs better than normal A* when heuristics are prone to sharp changes. This algorithm has been implemented in a hierarchical manner, where each generation of the algorithm gives a more detailed path that has a higher reaching probability. The map used for this purpose is based on a probabilistic approach where we measure the probability of collision with obstacle while traveling inside the cell. As we decompose the cells, the cell size reduces and the probability starts to touch 0 or 1 depending upon the presence or absence of obstacles in the cell. In this approach, it is not compulsory to run the entire algorithm. We may rather break after a certain degree of certainty has been achieved. We tested the algorithm in numerous situations with varying degrees of complexities. The algorithm was able to give an optimal path in all the situations given. The standard A* algorithm failed to give results within time in most of the situations presented. (C) 2011 Elsevier B.V. All rights reserved.