Extended Search Planning for Multiple Moving Targets Incorporating Search Priorities
Abstract
This article deals with a one-searcher multi-target search problem where targetswith different detection priorities move in Markov processes in each discrete time interval over agiven space search area, and the total number of search time intervals is fixed. A limitedsearch resource is available in each search time interval and an exponential detection functionis assumed. The searcher can obtain a target detection reward, if the target is detected, whichrepresents the detection priority of target and does not increase with respect to time. The objective is toestablish the optimal search plan that allocates the search resource effort over the search areasin each time interval in order to maximize the total detection reward. The analysis shows that the given problem can be decomposed into interval-wise individualsearch problems, each being treated as a single stationary target problem for each timeinterval. Thus, an iterative procedure is derived to solve a sequence of stationary targetproblems. The computational results show that the proposed algorithm guaranteesoptimality.References
J. Berger, N. Lo, and M. Noel, A new multi-target, multi-agent search-and-rescue path planning approach, International Journal of Computer, Electrical, Automation, Control and Information Engineering, vol. 8, pp. 935-944, 2014.
S.S. Brown, Optimal search for a moving target in discrete time and space, Operations Research, vol. 28, pp. 1275-1289, 1980.
A. Charnes and W.W. Cooper, The theory of search: Optimum distribution of search effort, Management Science, vol. 5, pp. 44-50,1958.
F. Dambreville and J.P. Le Cadr, Detection of a Markovian target with optimization of the search efforts under generalized linear constraints, Naval Research Logistics, vol. 49, pp. 117-142, 2002.
R.F. Dell, J.N. Eagle, and G.H.A Martins, Using multiple searchers in constrained path moving target search problem, Naval Research Logistics, vol. 43, pp. 463-480, 1996.
J.B. Kadane, Optimal discrete search with technological choice, Mathematical Methods of Operations Research, vol. 81, pp. 317-336, 2015.
M.H. Kim, H.C. Baik, and S.C. Lee, Response threshold model based uav search planning and task allocation, Journal of Intelligent & Robotic Systems, vol. 75, pp. 625-640, 2014.
S.H. Kim, Locating direction finders optimally under risk of detection, Statistics, Optimzation & Imformation Computing, vol. 6, pp. 219-232, 2018.
B.O. Koopman, Search and Screening, 2nd ed, Pergamon Press, New York, 1989.
F.H. Smith and G. Kimeldorf, Discrete sequential search for one of many objects, Annals of statistics, vol. 3, pp. 906-915, 1975.
L.D. Stone, Whats happened in search theory since the 1975 Lanchester Prize?, Operations Research, vol. 37, pp. 501-506, 1989.
L.D. Stone, Theory of optimal search, 2nd ed. Operation Research society of America, Arlington, VA, 1989.
L.C. Thomas and J.N. Eagle, Criteria and approximate method for path-constrained moving target search problems, Naval Research Logistics, vol. 42, pp. 27-38, 1995.
L. Tierney and J.B. Kadane, Surveillance search for a moving target, Operations Research, vol. 31, pp. 720-738, 1983.
A.R. Washburn, On a search for a moving target, Naval Research Logistics, vol. 27, pp. 315-322, 1980.
A.R. Washburn, Search for a moving target: The FAB algorithm, Operations Research, vol. 31, pp. 739-751, 1983.
A.R. Washburn, Branch and bound method for a search problem, Naval Research Logistics, vol. 45, pp. 98-113, 1998.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
