Moving Target Search Algorithm with Informational Distance Measures

ABSTRACT

We consider an Ishida and Korf Moving Target Search (MTS) algorithm with informational distance measures. Similarly to the previously defined Informational Learning Real-Time A* algorithm, the suggested algorithm acts on the set of partitions of the sample space, on which the probability mass function is defined. The information-based Rokhlin metric and its lower bound – Ornstein metric, give the necessary distance measures. We prove that similarly to the Ishida and Korf MTS algorithm, the proposed Informational MTS (IMTS) algorithm always terminates and finds the target. The comparison of the IMTS algorithm with known models shows that it outperforms known Markov decision process model of search with probabilistic and informational decision criteria. These findings help to construct a unified framework of search after both static and moving targets, and to bridge the gap between different search procedures that are related to both artificial intelligence and information theory.

Keywords: