Effective Search for a Naval Mine with Application to Distributed Failure Detection - Search Theory: A Game Theoretic Perspective - page 112

Chapter 8
Effective Search for a Naval Mine
with Application to Distributed Failure
Detection
Jun Kiniwa, Kensaku Kikuta, and Toshio Hamada*
Abstract We consider a kind of reconnaissance problem which has an application
to distributed failure detection. The problem can be considered as a multistage two-
person zero-sum game. The two-person, player A and player B, consists of a trans-
port ship and a terrorist, respectively, where the ship is equipped with an unmanned
reconnaissance boat. The ship circulates ports again and again and the terrorist may
lay a naval mine on the shipping route. For safety, the ship dispatches the unmanned
reconnaissance boat and removes the risk of a mine. However, it is very rare that
the terrorist lays the mine, while the circulation of the reconnaissance boat is very
costly. So, we introduce a mine-preparing probability, represented by geometric dis-
tribution, preceding the terrorist's strategy. The ship has to determine when it should
dispatch the boat so that it can maximize its expected payoff. First, we assume that
the mine is laid at each beginning of a stage and investigate two cases, a game con-
tinuation case and a game termination case, after the ship has been broken by a
mine. Next, we assume that the mine may be laid at any timing of a stage and inves-
tigate two methods, dispatching two boats and dispatching one boat, for the game
continuation case. Finally, we state that the problem can also be applied to a failure
detection problem in a distributed system if we regard the ship as a token and the
terrorist as an adversary who causes a failure.
* Deceased.