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} $, where $\overline {OPT} $ is the approximate optimum. The experiment results show that the proposed algorithm outperforms state-of-the-art approaches in multi-object search.

Efficient task allocation is a challenge for multirobot search. The multi-robot search problem is reformulated as submodular maximization subject to intersection system constraints. The objective function is submodular and consists of a coverage function to cover environments and a balancing function to efficiently dispatch robots. The intersection system is composed of routing and clustering constraints. The experiment results show that the proposed approach outperforms state-ofthe-art methods in multi-robot search.