LAUSR

Various robotic problems (e.g., map exploration, environmental monitoring and spatial search) can be formulated as submodular maximization problems with routing constraints. These problems involve two NP-hard problems, maximal coverage and traveling salesman problems. The generalized cost-benefit algorithm (GCB) is able to solve this problem with a $\frac{1}{2}(1-\frac{1}{e})\widetilde{OPT}$ guarantee, where $\widetilde{OPT}$ is the approximation of optimal performance. There is a gap between the $\widetilde{OPT}$ and the optimal solution $(OPT)$. In this research, the proposed algorithms, Tree-Structured Fourier Supports Set (TS-FSS), utilize the submodularity and sparsity of routing trees to boost GCB performance. The theorems show that the proposed algorithms have a higher optimum bound than GCB. The experiments demonstrate that the proposed approach outperforms benchmark approaches.