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

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/95728

Title:	Multi-robot Search in 3D Environments using Submodularity with Matroid Intersection Constraints
Authors:	李晏碩;Li, Yan-Shuo
Contributors:	數學系
Keywords:	次模性;擬陣理論;多機器人搜尋問題;Submodularity;Matroid;Multi-robot search problem
Date:	2024-07-18
Issue Date:	2024-10-09 17:13:10 (UTC+8)
Publisher:	國立中央大學
Abstract:	多機器人搜尋是一個具有挑戰性的問題，因為其涉及任務分配和覆蓋問題，而這些問題皆是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.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	31	View/Open

社群 sharing

Loading...