Path Planning on Static Environments based on Exploration with a Swarm Robotics and RRG Algorithms

Abstract

The coordination of a swarm of simulated robots is proposed as a method for finding paths to a specific target in unknown environments. The solution to creating the most viable pathway to a desired target can be derived through swarm robotics by deploying a bio-inspired exploration algorithm based in a cellular automata model. This algorithm uses virtual pheromones to execute a better dispersion of the agents through the environment in order to decrease the iterations need it to cover it. This model is compared with the classic Random Walk algorithm, which works in a probabilistic and random way. Using the environment map, once obstacles have been identified, an adapted Rapidly-exploring Random Graph (RRG) scheme is developed to structure the environment through a network. From there a Dijkstra path planning algorithm is applied with the aim of defining an optimized route to a specic target. Application of that procedure creates an efficient and effective scheme for finding a path into unknown environments. For this study, performance simulations have been included to refine parameters in order to compare results with different strategies.