Multi-agent search using sensors with heterogeneous capabilities

ABSTRACT

In this thesis we address the problem of multi-agent search. We formulate two deploy and search strategies based on optimal deployment of agents in search space so as to maximize the search effectiveness in a single step. We show that a variation of centroidal Voronoi configuration is the optimal deployment. When the agents have sensors with different capabilities, the problem will be heterogeneous in nature. We introduce a new concept namely, generalized Voronoi partition in order to formulate and solve the heterogeneous multi-agent search problem. We address a few theoretical issues such as optimality of deployment, convergence and spatial distributedness of the control law and the search strategies. Simulation experiments are carried out to compare performances of the proposed strategies with a few simple search strategies.

References

1. K. R. Guruprasad and D. Ghose, Deploy and search strategy for multi-agent systems using Voronoi partitions, Proceedings of the 4th international Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), University of Glamorgan, Wales, UK, July 9--11, 2007, pp. 91--100.
2. J. Cortes, S. Martinez, and F. Bullo, Spatially-distributed coverage optimization and control with limited-range interactions, ESAIM: Control, Optimization and Calculus of Variations 11 (4), 2005, pp. 691--719.
3. Q. Du, V. Faber, M. Gunzburger, Centroidal Voronoi tessellations: Applications and algorithms, SIAM Review, Vol 41, no. 4, pp. 637--676, 1999.
4. F. Aurenhammer, Voronoi Diagrams - A survey of a fundamental geometric data structure. ACM Computing Surveys, 23(3), 1991, pp. 345--405.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Distributed artificial intelligence

      • Multi-agent systems

    • Search methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming

    • Data structures design and analysis

      • Sorting and searching