A Modular Algorithm for Exhaustive Map Searching Using Occupancy Based Maps
Christopher W. Lum, Juris Vagners · AIAA Infotech@Aerospace Conference · 2009
Searching for a target in a complex environment is a common problem encountered by many autonomous systems. 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 any given cell of the map. Agents formulate control decisions for a fixed number of time steps using a modular algorithm that allows for individual capabilities and characteristics of individual agents to be encoded in several parameters. This paper investigates one aspect of the search strategy and presents a solution that guarantees total map coverage. The resulting search patterns executed by agents 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 being located in any given cell is driven to zero. Nomenclature B Set of z values defining spatial domain of occupancy based map BR Locations reachable by agent in d steps B ̃ Set of z values defining center of occupancy based map cells