A swarm-based algorithm for optimal spatial coverage of an unknown region

This paper presents an algorithm for optimal spatial coverage of an unknown region by a swarm of agents. The algorithm is based on the Ant Colony Optimization heuristic which is mapped and adapted to solve the current optimization problem. Each agent will leave a virtual pheromone trail during its movement through the unknown region, either attractor or repellent, represented by a positive or negative value, that decays in time. A novel stimergy technique is used to coordinate the agents´ behavior when deciding to follow or to move away from the pheromone trail, depending on the pheromone value. For exploring the unknown areas a combination of a greedy technique based on the concept of rejection vector and a probabilistic technique for selecting the agents´ rotating angles are employed. The obtained results are promising showing that our solution manages to obtain a coverage with up to 40% higher than classic rejection algorithm and with up to 25% that the distributed rejection algorithm.