Multi-agent search strategy based on centroidal Voronoi configuration

Abstract

We propose a combined deploy and search strategy for multi-agent systems using Voronoi partition. Agents such as mobile robots (AGVs, UAVs, or USVs) search the space to acquire knowledge about the space. Lack of information about the search space is modeled as an uncertainty density distribution, which is known a priori to all the agents at the beginning of search. It is shown that when the agents are located at the centroid of Voronoi cells, computed with the perceived uncertainty density, reduction in uncertainty density is maximized. While moving toward this optimal configuration, the agents simultaneously perform search acquiring the information about the search space, thereby reducing the uncertainty density. The proposed search strategy is guaranteed to reduce the average uncertainty density to any arbitrary level. Simulation experiments are carried out to validate the proposed search strategy and compare its performance with sequential deploy and search strategy proposed in the literature. The simulation results indicate that the proposed strategy performs better than sequential deploy and search in terms of faster search, and smoother and shorter robot trajectories. �2010 IEEE.