Abstract
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) |
|---|---|
| Pages (from-to) | 205-229 |
| Number of pages | 25 |
| Journal | Autonomous Robots |
| Volume | 41 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1 2017 |
Bibliographical note
Funding 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.
Publisher Copyright:
© 2015, Springer Science+Business Media New York.
Keywords
- Coverage problem
- Overlapping group LASSO
- Probabilistic search
- Receding horizon control
- Submodularity