IISc Logo    Title

etd AT Indian Institute of Science >
Division of Mechanical Sciences  >
Aerospace Engineering (aero) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2005/808

Title: Multi-Agent Search Using Voronoi Partition
Authors: Guruprasad, K R
Advisors: Ghose, Debasish
Keywords: 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
Submitted Date: Dec-2008
Series/Report no.: G22639
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.
URI: http://etd.iisc.ernet.in/handle/2005/808
Appears in Collections:Aerospace Engineering (aero)

Files in This Item:

File Description SizeFormat
G22639.pdf2.97 MBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01