Search Algorithm for Teams of Heterogeneous Agents with Coverage Guarantees

Among common intelligence, reconnaissance, and surveillance tasks, searching for a target in a complex environment is a problem for which autonomous systems are well suited. This work considers the problem of searching for targets using a team of heterogeneous agents. The system maintains a grid-based world model which contains information about the probability that a target is located in a given cell of the map. Agents formulate control decisions for a fixed number of time steps using a modular algorithm that allows parameterizations of agent capabilities. This paper investigates a solution that guarantees total map coverage. The control law for each agent does not require explicit knowledge of other agents. This yields a system which is scalable to a large number of vehicles. The resulting search patterns guarantee an exhaustive search of the map in the sense that all cells will be searched sufficiently to ensure that the probability of a target going unnoticed is driven to zero. Modifications to this algorithm for explicit cooperation between agents is also investigated.