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

NCU Institutional Repository > 理學院 > 數學研究所 > 博碩士論文 > Item 987654321/95728

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/95728

题名:	Multi-robot Search in 3D Environments using Submodularity with Matroid Intersection Constraints
作者:	李晏碩;Li, Yan-Shuo
贡献者:	數學系
关键词:	次模性;擬陣理論;多機器人搜尋問題;Submodularity;Matroid;Multi-robot search problem
日期:	2024-07-18
上传时间:	2024-10-09 17:13:10 (UTC+8)
出版者:	國立中央大學
摘要:	多機器人搜尋是一個具有挑戰性的問題，因為其涉及任務分配和覆蓋問題，而這些問題皆是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.
显示于类别:	[數學研究所] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	35	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....