多機器人搜尋是一個具有挑戰性的問題，因為其涉及任務分配和 覆蓋問題，而這些問題皆是NP-hard。 它可以重新定義為在擬陣限制 下的覆蓋率最大化問題。 覆蓋率最大化問題可透過次模性來解決。 擬陣限制是由路徑限制和分群限制所組成。 此研究提出Multi-robot Search with Matroid constraints (MRSM)的方法，此方法達成1/3OPT，其中 OPT是基於生成樹結構下的近似最優性能。 實驗結果顯示，所提出MRSM方法在多機器人搜尋問題中優於其他演算法。;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, Multirobot Search with Matroid constraints (MRSM), achieves 1/3OPT, where 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.
