Information-Driven Search Strategies in the Board Game of CLUE $^{\circit{R}}$

Abstract

This paper presents an information-driven sensor management problem, referred to as treasure hunt, which is relevant to mobile-sensor applications such as mine hunting, monitoring, and surveillance. The objective is to infer a hidden variable or treasure by selecting a sequence of measurements associated with multiple fixed targets distributed in the sensor workspace. The workspace is represented by a connectivity graph, where each node represents a possible sensor deployment, and the arcs represent possible sensor movements. An additive conditional entropy reduction function is presented to efficiently compute the expected benefit of a measurement sequence over time. Then, the optimal treasure hunt strategy is determined by a novel label-correcting algorithm operating on the connectivity graph. The methodology is illustrated through the board game of CLUE, which is shown to be a benchmark example of the treasure hunt problem. The game results show that a computer player implementing the strategies developed in this paper outperforms players implementing Bayesian networks, Q-learning, or constraint satisfaction, as well as human players.