Searching and Patrolling Dispersed Locations
Creators: name: Mellor, Edward
Publisher: name: Lancaster University
Year: 2025

description: There are many real-world scenarios in which hidden objects or targets
 must be found. In searching for these targets, it may be necessary to
 traverse great distances, and practical search strategies should take into
 account the costs of moving between different locations. In this thesis,
 we present a discrete-time search model and a continuous-time patrol model
 that both explicitly take costs of movement into account.
 
 
 The search problem involves looking for a target which has been hidden in
 one
 
 of finitely many geographically distinct locations according to a known
 probability distribution. A searcher moves between these locations in
 order to find the target. For each location, a search takes some known
 amount of time to complete and independently finds the target with a known
 probability if the target is there. The searcher aims to minimise the
 expected total amount of time needed to find the target. The version of
 our problem without travel times can be solved to optimality using Gittins
 indices, which direct the searcher to always search the location that
 yields the maximal rate of target discovery. When travel times are
 included, the problem becomes much more challenging because the searcher
 becomes less willing to move to another location due to the potential
 future travel time back to the current location. In addition, when
 choosing the next destination, the searcher needs to take into account not
 only the
 
 distance to each destination, but also each destination’s distance to all
 other locations. We draw upon restless bandit theory to derive an index
 heuristic that takes travel times into account, and show that this
 heuristic has a tendency to leave a location prematurely. Subsequently, we
 use a range of methods to improve the index heuristic and demonstrate its
 strong performance via computational experiments. 
 
 
 The patrol problem also involves searching for a target (now perhaps best
 thought of as an attacker) among finitely many geographically distinct
 locations. Rather than being present at the start of the search, these
 attackers arrive over time. It is therefore necessary for the patroller to
 patrol continuously, visiting all locations infinitely often, to catch
 these attackers. Once the patroller arrives at a location, they can spend
 any amount of time searching for targets with some detection rate at that
 location, before moving to a different location. The objective of the
 patroller is to minimize the expected time an attacker stays undetected at
 a location regardless of where the attack occurs. In the special case
 where all travel times are set to zero, we elucidate an optimal cyclic
 policy in which the patroller allocates a fixed fraction of their effort
 to each location continuously. As in the case of the search problem, this
 patrol problem
 
 becomes significantly more challenging when travel times are introduced.
 We define two cycle types based on common patrol practice for perimeter
 patrol and border patrol, respectively, and derive formulae for the
 expected time to detecting an attack in each case. We also provide an
 algorithm for finding the best parameters for each cycle type subject to
 some unimodality conditions. We give several examples where these cycle
 types perform well and numerically demonstrate that the optimal patrol
 policy depends highly on the structure and parameters of each patrol
 problem.