Solving the Datum Search as a Partially Observed Stochastic Game

Abstract

The Flaming Datum (FD) problem refers to the search for a hostile Evader that is fleeing after momentarily revealing its position. If Evader’s direction is fixed but unknown, while its maximal speed is known, Koopman argued in 1980 that the best trajectory for Searcher is a spiral starting from the revealed position. The objective of our study is to verify the hypothesis of a spiral search path, by formulating the FD problem in the framework of a finite two-player zero-sum partially observed stochastic search game, where the opponent plays repeatedly a fixed but unknown pure strategy. Using a realistic sensor model, current information about the position of Evader is represented by an occupancy map, updated in the Bayesian framework. The utility is computed as the entropy reduction of the occupancy map. The game was implemented in software and solved using the maxmin method. By running repeatedly the described search game, we have found that the search pattern, although random (due to the uncertainties in sensing and mixed strategies), is indeed a spiral on every play of the game, thus confirming the hypothesis.

Keywords

• Search games
• Bayesian estimation
• entropy
• machine intelligence