Computation-Aware Multi-object Search in 3D Space using Submodular Tree

Abstract

Searching for targets in 3D environments can be formulated as submodular maximization problems with routing constraints. However, it involves solving two NP-hard problems: the maximal coverage problem and the traveling salesman problem. Since the time constraint is critical for search problems, this research proposes a Computation-Aware Search for Multiple Objects (CASMO) algorithm to further consider the computational time in the cost constraints. Due to the submdularity, the greedy algorithm achieves \frac{1}{2}\left( {1 - \frac{1}{e}} \right)\overline {OPT} \frac{1}{2}\left( {1 - \frac{1}{e}} \right)\overline {OPT} , where \overline {OPT} \overline {OPT} is the approximate optimum. The experiment results show that the proposed algorithm outperforms state-of-the-art approaches in multi-object search.