Information Technology Reference
In-Depth Information
2.1 Introduction
Since the conception of search games almost 50 years ago, the field has expanded
and developed in many different directions, as seen in Chap. 1 . In this chapter we
focus in on one particular theme: that of search games on a network with a mobile
searcher and an immobile hider. Games of this type may be described as 'hide-
and-seek' games. The classic results in this field can be found in Alpern and Gal's
monograph [ 4 ] and Gal's recent survey [ 13 ]. Here we do not aim to give an ex-
haustive list of all work in the field, but we follow on from Sects. 1.1.1 and 1.1.2 in
Chap. 1 , taking a more detailed look at some classic results and linking them to new
work on search games with an immobile hider.
We begin in Sect. 2.2 by discussing how Isaacs [ 14 ] first introduced search games
of this type, and how he described strategies for both the hider and the searcher
which would continue to be of fundamental importance in later work in the field. In
Sect. 2.3 we then turn to the first rigorous definition, given by Gal [ 10 ], of a search
game with an immobile hider and a mobile searcher who starts from a given point.
We indicate how Gal solved his game if the search space is a tree or if it is Eulerian.
We then show in Sect. 2.4 how Reijnierse and Potters [ 17 ] extended Gal's anal-
ysis to weakly cyclic networks, which have the structure of a tree with some nodes
replaced by cycles. We describe the solution of Gal's game on these networks, and
how Gal proved an analagous result for weakly Eulerian networks.
In the final two sections we discuss some more recent work on search games on
networks with an immobile hider. Section 2.5 deals with a version of Gal's original
game in which the searcher can start from any point in the network. Section 2.6
describes three new Search Game models [ 2 , 5 , 6 ] which all modify or generalize
Gal's classic model in some way.
2.2 The Birth of Search Games
Search games were first introduced by Rufus Isaacs in his 1965 topic Differential
Games [ 14 ], as indicated in Chap. 1 . The topic was originally motivated by combat
problems, and indeed, many of the problems discussed in the topic have a military
focus to them. Earlier chapters in the topic are concerned with so called Pursuit
Games ,inwhicha Pursuer (or Pursuers ) aim to capture an Evader whose location
is known to him at all times during the game. Search games are introduced later
in the topic in a chapter called 'Toward a Theory with Incomplete Information'.
The model presented differs from Pursuit Games in that Pursuers now aim to capture
an Evader about whose position the Pursuers now do not have complete information.
The terminology changes: the Evader becomes the hider and the Pursuers become
the searchers. This terminology has stuck and is now widely used in the search
games literature.
Isaacs begins by defining what he calls the simple search game . This could be
regarded as the simplest and most general possible search game, and is described in
informal terms. In an arbitrary region
R
, which may be a subset of Euclidean space
Search WWH ::




Custom Search