The goal of search is to maximize the probability of target detection while covering most of the environment in minimum time. Existing approaches only consider one of these objectives at a time and most optimal search problems are NP-hard. In this research, a novel approach for search problems is proposed that considers three objectives: (1) coverage using the fewest sensors; (2) probabilistic search with the maximal probability of detection rate (PDR); and (3) minimum-time trajectory planning. Since two of three objective functions are submodular, the search problem is reformulated to take advantage of this property. The proposed sparse cognitive-based adaptive optimization and PDR algorithms are within (1 - 1 / e) of the optimum with high probability. Experiments show that the proposed approach is able to search for targets faster than the existing approaches.
Bibliographical noteFunding Information:
This research was completed thanks to the financial support from ONR Grant 1361538 and NSF CAREER CMMI 1254906. Kuo-Shih would like to thank his daughter, Chin-Chun Tseng. The hide-and-seek game they played inspires this research. The authors would also like to thank Alessandro Renzaglia for discussing the details about his PhD thesis, the CAO algorithm.
- Coverage problem
- Overlapping group LASSO
- Probabilistic search
- Receding horizon control