Approximate solutions for expanding search games on general networks

Steve Alpern, Thomas Lidbetter

Research output: Contribution to journalArticle

Abstract

We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs a i such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.

Original languageEnglish (US)
Pages (from-to)259-279
Number of pages21
JournalAnnals of Operations Research
Volume275
Issue number2
DOIs
StatePublished - Apr 15 2019

Fingerprint

Paradigm
Minimax
Factors

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Management Science and Operations Research

Keywords

  • Defense and security
  • Networks
  • Search games
  • Zero-sum games

Cite this

@article{eda2066327704df9b9a2bce0b2b7aba9,
title = "Approximate solutions for expanding search games on general networks",
abstract = "We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs a i such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.",
keywords = "Defense and security, Networks, Search games, Zero-sum games",
author = "Steve Alpern and Thomas Lidbetter",
year = "2019",
month = "4",
day = "15",
doi = "10.1007/s10479-018-2966-0",
language = "English (US)",
volume = "275",
pages = "259--279",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer Netherlands",
number = "2",

}

Approximate solutions for expanding search games on general networks. / Alpern, Steve; Lidbetter, Thomas.

In: Annals of Operations Research, Vol. 275, No. 2, 15.04.2019, p. 259-279.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Approximate solutions for expanding search games on general networks

AU - Alpern, Steve

AU - Lidbetter, Thomas

PY - 2019/4/15

Y1 - 2019/4/15

N2 - We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs a i such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.

AB - We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs a i such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.

KW - Defense and security

KW - Networks

KW - Search games

KW - Zero-sum games

UR - http://www.scopus.com/inward/record.url?scp=85050318365&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050318365&partnerID=8YFLogxK

U2 - 10.1007/s10479-018-2966-0

DO - 10.1007/s10479-018-2966-0

M3 - Article

AN - SCOPUS:85050318365

VL - 275

SP - 259

EP - 279

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 2

ER -