Information-driven sensor path planning and the treasure hunt problem

2008 2008

Other formats: Order a copy

Abstract (summary)

This dissertation presents a basic information-driven sensor management problem, referred to as treasure hunt, that is relevant to mobile-sensor applications such as mine hunting, monitoring, and surveillance. The objective is to classify/infer one or multiple fixed targets or treasures located in an obstacle-populated workspace by planning the path and a sequence of measurements of a robotic sensor installed on a mobile platform associated with the treasures 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. A methodology is developed for planning the sensing strategy of a robotic sensor deployed. The sensing strategy includes the robotic sensor's path, because it determines which targets are measurable given a bounded field of view. Existing path planning techniques are not directly applicable to robots whose primary objective is to gather sensor measurements. Thus, in this dissertation, a novel approximate cell-decomposition approach is developed in which obstacles, targets, the sensor's platform and field of view are represented as closed and bounded subsets of an Euclidean workspace. The approach constructs a connectivity graph with observation cells that is pruned and transformed into a decision tree, from which an optimal sensing strategy can be computed. It is shown that an additive incremental-entropy function can be used to efficiently compute the expected information value of the measurement sequence over time.

The methodology is applied to a robotic landmine classification problem and the board game of CLUE®. In the landmine detection application, the optimal strategy of a robotic ground-penetrating radar is computed based on prior remote measurements and environmental information. Extensive numerical experiments show that this methodology outperforms shortest-path, complete-coverage, random, and grid search strategies, and is applicable to non-overpass capable platforms that must avoid targets as well as obstacles. The board game of CLUE® is shown to be an excellent benchmark example of treasure hunt problem. The test results show that a player implementing the strategies developed in this dissertation outperforms players implementing Bayesian networks only, Q-learning, or constraint satisfaction, as well as human players.

Indexing (details)

Mechanical engineering;
Artificial intelligence
0548: Mechanical engineering
0800: Artificial intelligence
Identifier / keyword
Applied sciences; Bayesian network sensor model; Computer games; Demining; Fusion; Geometric sensing; Information theory; Robotic sensors; Sensor path planning; Value of information
Information-driven sensor path planning and the treasure hunt problem
Cai, Chenghui
Number of pages
Publication year
Degree date
School code
DAI-B 69/03, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Ferrari, Silvia
Committee member
Carin, Lawrence; Chakrabarty, Krishnendu; Garg, Devendra; Scruggs, Jeffrey
Duke University
Mechanical Engineering and Materials Science
University location
United States -- North Carolina
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.