  Adversarial search of a network for an immobile Hider (or target) was
introduced and solved for rooted trees by Gal (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
the signal has 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 to the
optimal Hider strategy in the classic search game of Gal, the Hider's optimal
distribution for this model is more skewed towards leaf nodes that are further
from the root.
