Map Explorations via Dynamic Tree-Structured Graph

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

Title:	Map Explorations via Dynamic Tree-Structured Graph
Authors:	謝瑞煦;Shieh, Rei-Shu
Contributors:	數學系
Keywords:	次模性;3D地圖探勘;最大覆蓋問題;Submodularity;3D map exploration;Maximal coverage problem
Date:	2023-07-25
Issue Date:	2024-09-19 17:19:37 (UTC+8)
Publisher:	國立中央大學
Abstract:	在未知環境中進行地圖探勘是具有挑戰性的，因為最大化覆蓋率是個NP-hard的問題，這項研究提出了基於動態更新樹狀結構路徑而最大化覆蓋率之邊際效益的方法。由於缺少環境資訊，樹狀結構路徑需於不同時間段進行更新。因此，此項研究證明出每個時間段的理論保證值。實驗結果說明此項研究提出的方法效能更勝於其他方法。;Map exploration in unknown environments is challenging since find ing the optimal solution to maximize the environmental coverage is NP hard. This research proposes a method that maximizes the dynamic marginal gain of the coverage with the tree-Structured routing. Since the map is unknown, the tree-structured routing is dynamically updated at each time step. Thus, the theoretical guarantees at each time step are proved. The experiments show that the proposed method outperforms benchmark methods.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing