Search for an Immobile Hider on a Binary Tree with Unreliable Locational Information

Steve Alpern () and Thomas Lidbetter ()
Additional contact information
Steve Alpern: Warwick Business School, University of Warwick, Coventry CV4 7AL, United Kingdom
Thomas Lidbetter: Department of Management Science and Information Systems, Rutgers Business School, Newark, New Jersey 07102

Operations Research, 2025, vol. 73, issue 2, 583-594

Abstract: Adversarial search of a network for an immobile Hider (or target) was introduced and solved for rooted trees by Shmuel Gal in 1979. In this zero-sum game, a Hider picks a point to hide on the tree and a Searcher picks a unit speed trajectory starting at the root. The payoff (to the Hider) is the search time. In Gal’s model (and many subsequent investigations), the Searcher receives no additional information after the Hider chooses his location. In reality, the Searcher will often receive such locational information. For homeland security, mobile sensors on vehicles have been used to locate radioactive material stashed in an urban environment. In a military setting, mobile sensors can detect chemical signatures from land mines. In predator-prey search, the predator often has specially attuned senses (hearing for wolves, vision for eagles, smell for dogs, sonar for bats, pressure sensors for sharks) that may help it locate the prey. How can such noisy locational information be used by the Searcher to modify her route? We model such information as signals which indicate which of two branches of a binary tree should be searched first, where all signals have a known accuracy p < 1. Our solution calculates which branch (at every branch node) is favored , meaning it should always be searched first when the signal is in that direction. When the signal is in the other direction, we calculate the probability the signal should be followed. Compared with the optimal Hider strategy in the classic search game of Gal, the Hider’s optimal distribution for this model is more skewed toward leaf nodes that are further from the root.

Keywords: Military; and; Homeland; Security; games/group decisions; search/surveillance; tree algorithms: networks/graphs (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0128 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:2:p:583-594

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().