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.