Multi-Agent Search Using Voronoi Partition

Abstract

This thesis addresses a multi-agent search problem where several agents, equipped with sensors and communication devices, search an unknown area. Lack of information about the search space is modeled as an uncertainty density distribution. A sequential deploy and search (SDS) strategy is formulated where the agents are first deployed to maximize single step search effectiveness. To achieve an optimal deployment, a multi-center objective function defined using the Voronoi cells and the uncertainty distribution is optimized. It is shown that the critical points of this objective function are the centroids of the Voronoi cells. A proportional control law is proposed that makes the agents move to their respective “centroids”. Assuming agents to be first order dynamical systems and using LaSalle's invariance principle, it is shown that the closed-loop system converges globally asymptotically to the critical points. It is also shown that the sequential deploy and search strategy is spatially distributed with respect to the Delaunay graph corresponding to any given agent configuration. Next, a combined deploy and search (CDS) strategy is proposed where, instead of first deploying agents and then performing the search, the agents engage in search operation as they move toward the centroids. This strategy gives rise to shorter agent trajectories compared to the SDS strategy. Then the problem is formulated with practical constraints such as sensor range limits and limit on maximum speed of the agents. A few issues relating to implementation of the proposed search strategies are also addressed. Finally, the assumption of homogeneous agents is relaxed and agents equipped with sensors with heterogeneous capabilities are considered. A generalized Voronoi partitioning scheme is proposed and used to formulate a heterogeneous locational optimization problem. In this problem the agents are deployed in the search space optimizing the sensor effectiveness. As earlier, the two search strategies are proposed. Simulation experiments are carried out to validate the performance of the proposed search strategies. The simulation results indicate that both the proposed search strategies perform quite well even when the conditions deviated from the nominal. It is also shown that the combined deploy and search strategy leads to shorter and smoother trajectories than those of the sequential deploy and search strategy with the same parameters.