Multi-robot Search in 3D Environments using Submodularity with Matroid Intersection Constraints

[Author] Yan-Shuo Li, MS thesis, 2024.
[Abstract] The multi-robot search problem is challenging since it involves task allocation and coverage problems, which are NP-hard. This problem is reformulated as the maximal coverage problem subject to the intersection of matroid constraints. The coverage problem is solved by utilizing its submodularity. The intersection matroid is composed of a routing constraint and a clustering constraint. The proposed algorithm, Multi-robot Search with Matroid constraints (MRSM), achieves $\frac{1}{3}\widetilde{OPT}$, where $\widetilde{OPT}$ is an approximately optimal performance under a spanning tree structure. The experiment results show that the proposed approach outperforms state-of-the-art methods in multi-robot search problems.