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.
|Original language||English (US)|
|Number of pages||25|
|State||Published - Jan 1 2017|
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.
© 2015, Springer Science+Business Media New York.
- Coverage problem
- Overlapping group LASSO
- Probabilistic search
- Receding horizon control