Record Details

Multi-Agent Search Using Voronoi Partition

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Multi-Agent Search Using Voronoi Partition
 
Creator Guruprasad, K R
 
Subject Electronic Surveillance System
Multiple Sensors
Sequential Deploy and Search (SDS)
Combined Deploy and Search (CDS)
Heterogeneous Multi-Agent Search
Multi-Agent Search - Simulation
Voronoi Configuration
Voronoi Partitions
Heterogeneous Capabilities
Voronoi Decomposition
Aeronautics
 
Description 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.
 
Contributor Ghose, Debasish
 
Date 2010-08-05T11:31:35Z
2010-08-05T11:31:35Z
2010-08-05
2008-12
 
Type Thesis
 
Identifier http://hdl.handle.net/2005/808
 
Language en_US
 
Relation G22639