Open AccessExtended Search Planning for Multiple Moving Targets Incorporating Search Priorities
Author(s) -
Min-hyuk Kim,
Suhwan Kim,
Bongkyu Han
Publication year - 2020
Publication title -
statistics, optimization and information computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.297
H-Index - 12
eISSN - 2311-004X
pISSN - 2310-5070
DOI - 10.19139/soic-2310-5070-817
Subject(s) - interval (graph theory) , mathematical optimization , linear search , computer science , iterative deepening depth first search , search problem , markov chain , search algorithm , incremental heuristic search , markov decision process , resource (disambiguation) , beam search , algorithm , mathematics , markov process , machine learning , statistics , computer network , combinatorics
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.