Multi-Agent Discrete Search with Limited Visibility
For researchers and practitioners in multi-agent search and optimization, the paper provides faster exact algorithms for a specific class and approximation guarantees for a harder variant, though the contributions are incremental improvements over known techniques.
The paper reformulates multi-agent discrete search with limited visibility as a minimum cost network optimization problem, developing a faster specialized algorithm with proven correctness and worst-case performance superior to general min-cost flow algorithms. For the NP-hard variant where detection depends on both location and agent, they reduce it to submodular maximization over a matroid and provide an approximation algorithm with guaranteed performance, validated through simulations.
The problem of search by multiple agents to find and localize objects arises in many important applications. In this paper, we study a class of multi-agent search problems in which each agent can access only a subset of a discrete search space, with detection performance that depends only on the location. We show that this problem can be reformulated as a minimum cost network optimization problem, and develop a fast specialized algorithm for the solution. We prove that our algorithm is correct, and has worst case computation performance that is faster than general minimum cost flow algorithms. We also address the problem where detection performance depends on both location and agent, which is known to be NP-Hard. We reduce the problem to a submodular maximization problem over a matroid, and provide an approximate algorithm with guaranteed performance. We illustrate the performance of our algorithms with simulations of search problems and compare it with other min-cost flow algorithms.