資訊軌跡規劃 (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.
