Improvement of Submodular Maximization Problems With Routing Constraints via Submodularity and Fourier Sparsity
Pao-Te Lin, Kuo-Shih Tseng · IEEE Robotics and Automation Letters · 2023
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.