title: Information-driven search strategies in the board game of CLUE.
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.
authors.affiliation: Department of Mechanical Engineering and Materials Science, Duke University, Durham, NC 27708, USA. sferrari@duke.edu
authors.forename: Silvia
authors.initials: S
authors.lastname: Ferrari
authors.forename: Chenghui
authors.initials: C
authors.lastname: Cai