A search game for a mobile target with the conditionally deterministic motion defined by paths

In this paper, the authors investigate a search-and-hide game played by a searcher and a mobile target with a conditionally deterministic motion. The target space consists of discrete cells and there are possible target’s paths which specify the target’s position (cell number) at all times in future. The target selects one of paths at the beginning of the game and moves along the path thereafter. The searcher knows all possible paths of the target but he cannot know which path is selected by the target. The searcher is restricted by his total searching effort at each time, and allocating it among cells, he searches the target. The authors formulate this search situation as a two-person zero-sum game and derive the optimal solution. Several examples are examined and the meaning of the optimal conditions are elucidated.