etd AT Indian Institute of Science >
Division of Mechanical Sciences >
Aerospace Engineering (aero) >
Please use this identifier to cite or link to this item:
|Title: ||Multi-Agent Search Using Voronoi Partition|
|Authors: ||Guruprasad, K R|
|Advisors: ||Ghose, Debasish|
|Keywords: ||Electronic Surveillance System|
Sequential Deploy and Search (SDS)
Combined Deploy and Search (CDS)
Heterogeneous Multi-Agent Search
Multi-Agent Search - Simulation
|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.|
|Appears in Collections:||Aerospace Engineering (aero)|
Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.