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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：68

、訪客IP：18.227.72.55

姓名

李晏碩(Yan-Shuo Li) 查詢紙本館藏

畢業系所

數學系

論文名稱

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

相關論文

★ 3D Map Exploration and Search using Topological Fourier Sparse Set	★ 次模深度壓縮感知用於空間搜尋
★ Evasion and Pursuit Games via Adaptive Submodularity	★ Learning Spatial Search and Map Exploration using Adaptive Submodular Inverse Reinforcement Learning
★ Maximal Coverage Problems with Routing Constraints using Cross-Entropy Monte Carlo Tree Search	★ Localizing Complex Terrain for Quadruped Robots using Adaptive Submodularity
★ 使用成本效益生成樹的資訊軌跡規劃	★ Map Explorations via Dynamic Tree-Structured Graph

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2026-7-17以後開放)

摘要(中)

多機器人搜尋是一個具有挑戰性的問題，因為其涉及任務分配和
覆蓋問題，而這些問題皆是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.

關鍵字(中)

★ 次模性
★ 擬陣理論
★ 多機器人搜尋問題

關鍵字(英)

★ Submodularity
★ Matroid
★ Multi-robot search problem

論文目次

摘要 .................................................................................................... i
Abstract.............................................................................................. ii
Acknowledgements.............................................................................. iii
Contents ............................................................................................. iv
Figures ................................................................................................ v
Tables .................................................................................................viii
1 Introduction........................................................................ 1
1.1 Publication Note . . . . . . . . . . . . . . . . . . . . 4
2 Related Work...................................................................... 5
2.1 Target Search . . . . . . . . . . . . . . . . . . . . . 5
2.2 Multi-Robot Task Allocation (MRTA) . . . . . . . . 7
2.3 Routing Constraints . . . . . . . . . . . . . . . . . . 8
3 Background Knowledge ...................................................... 9
3.1 Submodularity . . . . . . . . . . . . . . . . . . . . . 9
3.2 Matroid . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Problem Formulation.......................................................... 16
4.1 Multi-robot search with independence system (MRSIS) 16
4.2 Multi-robot search with matroid (MRSM) . . . . . . 18
5 Proposed Algorithm ........................................................... 22
6 Experiments........................................................................ 24
6.1 Experiment Setup . . . . . . . . . . . . . . . . . . . 24
6.2 EX1: Comparison with Benchmarks on Targets Search 27
6.3 EX2: Parametric Analysis . . . . . . . . . . . . . . . 30
6.4 EX3: Scalability Analysis . . . . . . . . . . . . . . . 34
7 Conclusions and Future Work ............................................ 38
References ........................................................................................... 39

參考文獻

[1] Yan-Shuo Li and Kuo-Shih Tseng. Multi-robot search in a 3d environment with intersection system constraints. IEEE International
Conference on Robotics and Automation (ICRA), 2024.
[2] Steve Paull, Payam Ghassemi, and Souma Chowdhury. Learning
scalable policies over graphs for multi-robot task allocation using
capsule attention networks. IEEE International Conference on
Robotics and Automation (ICRA), pages 88158822, 2022.
[3] Wenda Sheng, Hongliang Guo, Wei-Yun Yau, and Yingjie Zhou.
Pd-fac: Probability density factorized multi-agent distributional reinforcement learning for multi-robot reliable search. IEEE Robotics
and Automation Letters, 7(4):88698876, 2022.
[4] Brent Schlotfeldt, Dinesh Thakur, Nikolay Atanasov, Vijay Kumar,
and George J Pappas. Anytime planning for decentralized multirobot active information gathering. IEEE Robotics and Automation
Letters, 3(2):10251032, 2018.
[5] James S Jennings, Greg Whelan, and William F Evans. Cooperative
search and rescue with a team of mobile robots. IEEE International
Conference on Advanced Robotics (ICAR), pages 193200, 1997.
[6] Nikolaus Correll and Alcherio Martinoli. Multirobot inspection
of industrial machinery. IEEE Robotics & Automation Magazine,
16(1):103112, 2009.
[7] Samir Khuller, Anna Moss, and Joseph Se Naor. The budgeted maximum coverage problem. Information processing letters,
70(1):3945, 1999.
[8] G Ayorkor Korsah, Anthony Stentz, and M Bernardine Dias. A
comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research, 32(12):14951512, 2013.
[9] Haifeng Zhang and Yevgeniy Vorobeychik. Submodular optimization with routing constraints. Association for the Advancement of
Articial Intelligence (AAAI), 30(1), 2016.
[10] Amarjeet Singh, Andreas Krause, Carlos Guestrin, William Kaiser,
and Maxim Batalin. Ecient planning of informative paths for multiple robots. Proceedings of the 20th international joint conference
on Artical intelligence (IJCAI), pages 22042211, 2007.
[11] Yan-Shuo Li and Kuo-Shih Tseng. Computation-aware multi-object
search in 3d space using submodular tree. IEEE International Conference on Robotics and Automation (ICRA), 2024.
[12] Boyu Zhou, Yichen Zhang, Xinyi Chen, and Shaojie Shen. Fuel:
Fast uav exploration using incremental frontier structure and hierarchical planning. IEEE Robotics and Automation Letters, 6(2):779
786, 2021.
[13] Boyu Zhou, Hao Xu, and Shaojie Shen. Racer: Rapid collaborative
exploration with a decentralized multi-uav system. IEEE Transactions on Robotics, 39(3):18161835, 2023.
[14] Mayank Mittal, Rohit Mohan, Wolfram Burgard, and Abhinav Valada. Vision-based autonomous uav navigation and landing for urban search and rescue. The International Symposium of Robotics
Research, pages 575592, 2019.
[15] Mikko Lauri, Joni Pajarinen, Jan Peters, and Simone Frintrop.
Multi-sensor next-best-view planning as matroid-constrained submodular maximization. IEEE Robotics and Automation Letters,
5(4):53235330, 2020.
[16] Sharaf C. Mohamed, Sanjif Rajaratnam, Seung Tae Hong, and
Goldie Nejat. Person nding: An autonomous robot search method
for nding multiple dynamic users in human-centered environments. IEEE Transactions on Automation Science and Engineering, 17(1):433449, 2020.
[17] Sharaf C Mohamed, Angus Fung, and Goldie Nejat. A multirobot person search system for nding multiple dynamic users in
human-centered environments. IEEE Transactions on Cybernetics,
53(1):628640, 2022.
[18] Xiaolong Zhu, Fernando Vanegas, and Felipe Gonzalez. An approach for multi-uav system navigation and target nding in cluttered environments. In IEEE International Conference on Unmanned Aircraft Systems (ICUAS), pages 11131120. IEEE, 2020.
[19] Kaiyu Zheng, Yoonchang Sung, George Konidaris, and Stefanie
Tellex. Multi-resolution pomdp planning for multi-object search
in 3d. IEEE/RSJ International Conference on Intelligent Robots
and Systems (IROS), pages 20222029, 2021.
[20] Aldy Gunawan, Hoong Chuin Lau, and Pieter Vansteenwegen.
Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2):315332, 2016.
[21] Jun Liu and Ryan K Williams. Optimal intermittent deployment
and sensor selection for environmental sensing with multi-robot
teams. IEEE International Conference on Robotics and Automation
(ICRA), pages 10781083, 2018.
[22] Ted K Ralphs, Leonid Kopman, William R Pulleyblank, and
Leslie E Trotter. On the capacitated vehicle routing problem. Mathematical programming, 94:343359, 2003.
[23] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.
An analysis of approximations for maximizing submodular set functionsi. Mathematical programming, 14(1):265294, 1978.
[24] Stefan Jorgensen, Robert H Chen, Mark B Milam, and Marco
Pavone. The matroid team surviving orienteers problem: Constrained routing of heterogeneous teams with risky traversal.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 56225629, 2017.
[25] Jun Liu and Ryan K Williams. Submodular optimization for coupled task allocation and intermittent deployment problems. IEEE
Robotics and Automation Letters, 4(4):31693176, 2019.
[26] Ryan K Williams, Andrea Gasparri, and Giovanni Ulivi. Decentralized matroid optimization for topology constraints in multi-robot
allocation problems. IEEE International Conference on Robotics
and Automation (ICRA), pages 293300, 2017.
[27] Ekaterina Tolstaya, James Paulos, Vijay Kumar, and Alejandro
Ribeiro. Multi-robot coverage and exploration using spatial graph
neural networks. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 89448950, 2021.
[28] Hao Zhang, Jiyu Cheng, Lin Zhang, Yibin Li, and Wei Zhang.
H2gnn: hierarchical-hops graph neural networks for multi-robot exploration in unknown environments. IEEE Robotics and Automation Letters, 7(2):34353442, 2022.
[29] Andreas Krause and Carlos Guestrin. Near-optimal observation
selection using submodular functions. Association for the Advancement of Articial Intelligence (AAAI), 7:16501654, 2007.
[30] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization.
Journal of Articial Intelligence Research, 42:427486, 2011.
[31] Yu-Chung Tsai, Bing-Xian Lu, and Kuo-Shih Tseng. Spatial search
via adaptive submodularity and deep learning. IEEE International
Symposium on Safety, Security, and Rescue Robotics (SSRR),
pages 112113, 2019.
[32] Pao-Te Lin and Kuo-Shih Tseng. Improvement of submodular maximization problems with routing constraints via submodularity and
fourier sparsity. IEEE Robotics and Automation Letters, pages 18,
2023.
[33] Haotian Zhang, Rao Li, Zewei Wu, and Guodong Sun. Nonmonontone submodular maximization under routing constraints. arXiv
preprint arXiv:2211.17131, 2022.
[34] Bernhard Korte and Dirk Hausmann. An analysis of the greedy
heuristic for independence systems. Annals of Discrete Mathematics, 2:6574, 1978.
[35] Julián Mestre. On the intersection of independence systems. Operations Research Letters, 43(1):79, 2015.
[36] Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey.
An analysis of approximations for maximizing submodular set functionsII. Springer, 1978.
[37] Ming-Yu Liu, Oncel Tuzel, Srikumar Ramalingam, and Rama Chellappa. Entropy-rate clustering: Cluster analysis via maximizing a
submodular function subject to a matroid constraint. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(1):99
112, 2013.
[38] Glenn Jocher, Ayush Chaurasia, Alex Stoken, Jirka Borovec,
NanoCode012, Yonghye Kwon, Kalen Michael, TaoXie, Jiacong
Fang, imyhxy, Lorna, Zeng Yifu, Colin Wong, Abhiram V, Diego
Montes, Zhiqiang Wang, Cristi Fati, Jebastin Nadar, Laughing,
UnglvKitDe, Victor Sonck, tkianai, yxNONG, Piotr Skalski, Adam
Hogan, Dhruv Nair, Max Strobel, and Mrinal Jain. ultralytics/yolov5: v7.0 - YOLOv5 SOTA Realtime Instance Segmentation,
November 2022.
[39] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn
to solve routing problems! International Conference on Learning
Representations, 2019.
[40] Bing-Xian Lu and Kuo-Shih Tseng. 3d map exploration via learning
submodular functions in the fourier domain. IEEE international
conference on unmanned aircraft systems (ICUAS), pages 1199
1205, 2020.

指導教授

曾國師(Tseng, Kuo-Shih)

審核日期

2024-7-18

推文