PATH PLANNING USING BACTERIAL FORRAGING ALGORITHMS

Abstract

Path planning has been the subject of research for many years in the field of robotics and navigation. This thesispresentsa study of various approaches that utilizes the concept of evolutionary algorithm to solve the path planning problem. Bacterial foraging, a popular evolutionary algorithm has been used to compute paths. This is done by treating the entire working configuration space as a set of discrete points. Then from out of these free configuration points are extracted. These are those points that do notlie in any obstacle. These points are then inputted into the bacterial foraging algorithm. The bacterial foraging algorithm then outputs an optimal free configuration point. This serves as the next point in the path being constructed. Variations of this basic process have been described in this thesis. Results show that the method produces path in an acceptable time window.Finally another approach has been proposed that also produces optimal paths, but with greater efficiency and accuracy. This method first creates a visibility graph of the given working scenario. Then the A* algorithm, which is a heuristic search algorithm, is applied to the above computed graph to obtain regions from where the optimal path would go. Now free configuration points are generated only around these regions. Then bacterial foraging is applied to each of these regions to work out the optimal free configuration points. The optimal path is then finally constructed by joining all these optimal free configuration points.