A new Multi-Bug Path Planning algorithm for robot navigation in known environments

摘要

This paper presents a new methodology for path planning of mobile robots in known environments with static obstacles, concept of which is similar to bug-algorithms, but uses multiple bugs. Multi Bug Path Planning (MBPP) works by assuming a virtual bug move towards the goal from the start state. If in case it meets an obstacle, then, that bug generates a new bug. The two bugs now move along walls of the obstacle in either direction until specific conditions are met. Bug generation continues whenever any of the current bugs hit a new obstacle, until target is reached by all live bugs. This algorithm thus evaluates best possible paths for a given environment and chooses the best route, supposed to be optimal. Simulation results shows that MBPP finds paths in lesser run-times, that are shorter and comparable with Post-Smoothed A*. Proposed work is an attempt to combine the features of offline and online methods, so that, the same algorithm could be used for both cases. Current work demonstrates the applicability of MBPP algorithm to offline path planning. Adaptation of this algorithm to online planning is left for future research.