使用成本效益生成樹的資訊軌跡規劃;Informative path planning via cost-benefit spanning tree

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

Title:	使用成本效益生成樹的資訊軌跡規劃;Informative path planning via cost-benefit spanning tree
Authors:	邱韋翔;Chiu, Wei-Hsiang
Contributors:	數學系
Keywords:	機率搜尋;次模性;普林-戴克斯特拉演算法;資訊軌跡規劃;空中機器人;貪婪演算法
Date:	2023-07-25
Issue Date:	2023-10-04 16:13:18 (UTC+8)
Publisher:	國立中央大學
Abstract:	資訊軌跡規劃 (IPP) 是無人機的關鍵應用之一。它可以重新定義為在軌跡限制下的次模性最大化問題。然而，尋找最佳搜索軌跡包括兩個NP-hard問題，即最大覆蓋問題和最小路徑問題。此研究提出成本效益生成樹(CBST) ，以提高IPP 的效能。理論說明樹的總曲率影響了理論保證值。實驗表明，所提出的 CBST 演算法的效能比其他演算法的效能更好。;Informative path planning (IPP) is one of key applications for unmanned aerial vehicles (UAVs). It can be formulated as the submodular maximization problem with routing constraints. However, fi nding an optimal search path includes two NP-hard problems, the covering problem and routing problem. In this research, the proposed algorithm generates the cost-benefi t spanning tree (CBST) to boost the IPP performance. The proofs show the theoretical guarantees depends on the total curvatures of the trees. The experiments demonstrate that the proposed method outperforms the benchmark approaches.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...