Information-driven search strategies in the board game of CLUE.

Journal Article

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.

Full Text

Cited Authors

  • Ferrari, S; Cai, C

Published Date

  • June 2009

Published In

Volume / Issue

  • 39 / 3

Start / End Page

  • 607 - 625

PubMed ID

  • 19174352

Electronic International Standard Serial Number (EISSN)

  • 1941-0492

Digital Object Identifier (DOI)

  • 10.1109/TSMCB.2008.2007629


  • eng

Conference Location

  • United States