The multi-robot search problem is challenging since it involves task allocation, minimal routing, and maximal coverage problems, which are NP-hard. To solve this problem with theoretical guarantees, it is reformulated as a maximal coverage problem subject to the intersection of matroid constraints. The coverage problem is solved by utilizing its submodularity. Additionally, the workload balance is considered to enhance search efficiency. The intersection matroid is composed of a routing constraint and a clustering constraint. The proposed algorithm, Multi-Robot Search with Matroid constraints (MRSM), achieves , where is the optimal performance under spanning-tree structures. Furthermore, Dynamic MRSM (D-MRSM) and MRSM with Hexagonal Packing (MRSM-Hex) are proposed for unknown and large-scale environments, respectively. The experiment results show that the MRSM approaches outperform state-of-the-art methods in terms of expected time to detection in multi-robot search problems and scale effectively for large search spaces.
AironiCCornellSSquartiniS (2022) Tackling the linear sum assignment problem with graph neural networks. In: International Conference on Applied Intelligence and Informatics, Reggio Calabria, Italy, 1-3 September, 90–101.
2.
BreuerABalkanskiESingerY (2020) The fast algorithm for submodular maximization. In: International Conference on Machine Learning, IEEE, 1134–1143.
3.
CorahMMichaelN (2019) Distributed matroid-constrained submodular maximization for multi-robot exploration: theory and practice. Autonomous Robots43: 485–501.
4.
CorrellNMartinoliA (2009) Multirobot inspection of industrial machinery. IEEE Robotics and Automation Magazine16(1): 103–112.
5.
FisherMLNemhauserGLWolseyLA (1978) An Analysis of Approximations for Maximizing Submodular Set Functions—Ii. Springer Nature, 73–87.
6.
GoarinMLoiannoG (2024) Graph neural network for decentralized multi-robot goal assignment. IEEE Robotics and Automation Letters9(5): 4051–4058.
7.
GolovinDKrauseA (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research42: 427–486.
8.
GunawanALauHCVansteenwegenP (2016) Orienteering problem: a survey of recent variants, solution approaches and applications. European Journal of Operational Research255(2): 315–332.
9.
JenningsJSWhelanGEvansWF (1997) Cooperative search and rescue with a team of mobile robots. In: IEEE International Conference on Advanced Robotics. IEEE, 193–200.
10.
JocherGChaurasiaAStokenA, et al (2022) ultralytics/yolov5: v7.0 - yolov5 sota realtime instance segmentation. DOI:10.5281/ZENODO.7347926.è.
11.
JorgensenSChenRHMilamMB, et al. (2017a) The Matroid Team Surviving Orienteers Problem: Constrained Routing of Heterogeneous Teams with Risky Traversal. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 5622–5629.
12.
JorgensenSChenRHMilamMB, et al. (2017b) The team surviving orienteers problem: routing robots in uncertain environments with survival constraints. In: First IEEE International Conference on Robotic Computing (IRC), IEEE, 227–234.
13.
KaempferYWolfL (2018) Learning the multiple traveling salesmen problem with permutation invariant pooling networks. arXiv preprint arXiv:1803.09621.
14.
KhullerSMossANaorJS (1999) The budgeted maximum coverage problem. Information Processing Letters70(1): 39–45.
15.
KoolWvan HoofHWellingM (2019) Attention, learn to solve routing problems. International Conference on Learning Representations, May 6-May 9, 2019, New Orleans, LA, USA.
16.
KorsahGAStentzADiasMB (2013) A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research32(12): 1495–1512.
17.
KorteBHausmannD (1978) An analysis of the greedy heuristic for independence systems. Annals of Discrete Mathematics2: 65–74.
18.
KrauseAGuestrinC (2007) Near-optimal observation selection using submodular functions. Association for the Advancement of Artificial Intelligence (AAAI)7: 1650–1654.
19.
KruskalJB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society7(1): 48–50.
20.
LauriMPajarinenJPetersJ, et al. (2020) Multi-sensor next-best-view planning as matroid-constrained submodular maximization. IEEE Robotics and Automation Letters5(4): 5323–5330.
21.
LeeMXiongYYuG, et al. (2018) Deep neural networks for linear sum assignment problems. IEEE Wireless Communications Letters7(6): 962–965.
22.
LiYSTsengKS (2024) Multi-robot Search in a 3d Environment with Intersection System Constraints. IEEE International Conference on Robotics and Automation (ICRA), 5963–5969.
23.
LinPTTsengKS (2023) Improvement of submodular maximization problems with routing constraints via submodularity and fourier sparsity. IEEE Robotics and Automation Letters8(4): 1927–1934.
24.
LiuJWilliamsRK (2018) Optimal intermittent deployment and sensor selection for environmental sensing with multi-robot teams. In IEEE International Conference on Robotics and Automation (ICRA). IEEE, 1078–1083.
25.
LiuJWilliamsRK (2019) Submodular optimization for coupled task allocation and intermittent deployment problems. IEEE Robotics and Automation Letters4(4): 3169–3176.
26.
LiuMYTuzelORamalingamS, et al. (2013) Entropy-rate clustering: cluster analysis via maximizing a submodular function subject to a matroid constraint. IEEE Transactions on Pattern Analysis and Machine Intelligence36(1): 99–112.
27.
LuBXTsengKS (2020) 3d map exploration via learning submodular functions in the fourier domain. In: IEEE International Conference on Unmanned Aircraft Systems (ICUAS). IEEE, 1199–1205.
28.
MartelloSTothP (1987) Linear assignment problems. North-Holland Mathematics Studies132: 259–282.
29.
MestreJ (2015) On the intersection of independence systems. Operations Research Letters43(1): 7–9.
30.
MittalMMohanRBurgardW, et al. (2019) Vision-based autonomous uav navigation and landing for urban search and rescue. The International Symposium of Robotics Research575–592.
31.
MohamedSCRajaratnamSHongST, et al. (2020) Person finding: an autonomous robot search method for finding multiple dynamic users in human-centered environments. IEEE Transactions on Automation Science and Engineering17(1): 433–449.
32.
MohamedSCFungANejatG (2022) A multirobot person search system for finding multiple dynamic users in human-centered environments. IEEE Transactions on Cybernetics. IEEE, 1–13.
33.
NemhauserGLWolseyLAFisherML (1978) An analysis of approximations for maximizing submodular set functions—i. Mathematical Programming14(1): 265–294.
34.
PaulSGhassemiPChowdhuryS (2022) Learning Scalable Policies over Graphs for Multi-Robot Task Allocation Using Capsule Attention Networks. IEEE International Conference on Robotics and Automation (ICRA), 8815–8822.
35.
QiCRSuHMoK, et al. (2017) Pointnet: deep learning on point sets for 3d classification and segmentation. In: IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 652–660.
36.
RalphsTKKopmanLPulleyblankWR, et al. (2003) On the capacitated vehicle routing problem. Mathematical Programming94: 343–359.
37.
SchlotfeldtBThakurDAtanasovN, et al. (2018) Anytime planning for decentralized multirobot active information gathering. IEEE Robotics and Automation Letters3(2): 1025–1032.
38.
ShengWGuoHYauWY, et al. (2022) Pd-fac: probability density factorized multi-agent distributional reinforcement learning for multi-robot reliable search. IEEE Robotics and Automation Letters7(4): 8869–8876.
39.
SinghAKrauseAGuestrinC, et al. (2007) Efficient planning of informative paths for multiple robots. International Joint Conference on Artifical Intelligence (IJCAI). 2204–2211.
40.
TolstayaEPaulosJKumarV, et al. (2021) Multi-robot Coverage and Exploration Using Spatial Graph Neural Networks. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 8944–8950.
41.
TsaiYCLuBXTsengKS (2019) Spatial search via adaptive submodularity and deep learning. In: IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR). IEEE, 112–113.
42.
WilliamsRKGasparriAUliviG (2017) Decentralized matroid optimization for topology constraints in multi-robot allocation problems. IEEE International Conference on Robotics and Automation (ICRA). IEEE, 293–300.
43.
ZhangHVorobeychikY (2016) Submodular optimization with routing constraints. In: Association for the Advancement of Artificial Intelligence, Phoenix, Arizona, February 12-17, 2016, Vol. 30.
44.
ZhangHChengJZhangL, et al. (2022) H2gnn: hierarchical-hops graph neural networks for multi-robot exploration in unknown environments. IEEE Robotics and Automation Letters7(2): 3435–3442.
45.
ZhangHLiRWuZ, et al. (2023) Nonmonotone submodular maximization under routing constraints. National Conference of Theoretical Computer Science3–17.
46.
ZhengKSungYKonidarisG, et al. (2021) Multi-resolution Pomdp Planning for Multi-Object Search in 3d. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2022–2029.
47.
ZhouBZhangYChenX, et al. (2021) Fuel: fast uav exploration using incremental frontier structure and hierarchical planning. IEEE Robotics and Automation Letters6(2): 779–786.
48.
ZhouBXuHShenS (2023) Racer: rapid collaborative exploration with a decentralized multi-uav system. IEEE Transactions on Robotics39(3): 1816–1835.
49.
ZhuXVanegasFGonzalezF (2020) An approach for multi-uav system navigation and target finding in cluttered environments. In: International Conference on Unmanned Aircraft Systems (ICUAS). IEEE, 1113–1120.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
