An Exhaustive Swarming Search Strategy based on Distributed Pheromone Maps

Abstract Swarms of Unmanned Air Vehicles (UAVs) are well suited to perform missions comprising a search stage where multiple entities must be located over a wide geographic area. Because of their decentralized control architecture, swarms are scalable, robust and adapt to environmental changes. Pheromone maps are a common coordination mechanism that emulates the foraging behavior of insects. Swarming agents use such a map to coordinate with each other and to guide their search. Most pheromone frameworks require an uninterrupted wireless network connection for every agent in the swarm. This is incompatible with real world applications were UAVs are link limited because of environmental factors or mission requirements. Furthermore, search heuristics based on pheromone gradients are susceptible to local minima and only offer statistical guaranty of coverage. In this paper, we present an exhaustive search strategy and its supporting distributed pheromone map scheme. This approach does not require any network infrastructure. It relies on agents exchanging pheromones in an ad-hoc fashion. Its optimal search heuristic guaranties coverage and finite search times. Through experimental data, we show how distributed maps compare favorably with centralized ones.