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

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 1/2 (1 - 1/e) OPT, where OPT is the approximate optimum. The experiment results show that the proposed algorithm outperforms state-of-the-art approaches in multi-object search.