Developments in autonomous vehicles and
sensor technologies are producing modern surveillance systems with
increased capabilities, where the sensors and their platforms are characterized
by a high degree of functionality, reconfigurability, and redundancy.
When
robotic sensors are deployed for sensing or surveillance purposes, the
whole system constitutes a new paradigm, where the measurement process
should guide the control and navigation of autonomous vehicles. Considering
that the sensors are mounted on the robot, we address the coupled problems
of motion and sensor planning, so called Treasure Hunt Problem, for a robot
whose purpose for navigating a given workspace is to enable measurements
from a subset of available targets from which an unknown variable is to be
inferred. Examples of related applications include landmine
detection and identification by sensors installed on ground vehicles;
sensor networks for monitoring endangered species; and, robot-installed
sensors to monitor an urban environment or the production in a
manufacturing industry. The detective
game of CLUE® is a research and educational benchmark for Treasure Hunt
Problem. These applications constitute a shift with respect to the
traditional paradigm of a sensor that is employed in order to enable robot
navigation. However, the overall system performance can still be optimized
by planning strategies that maximize the expected benefit of information of
the measurement sequence, while minimizing the cost associated with the use
of sensor and platform resources, such as, energy and distance.
Problem
Formulation: Given a layout W
and a joint probability distribution P(yi; Mi) of hypothesis variable yi and a set of
test variables or sensor
measurements Mi = {mi1, …, miM}, for any target Ti ⊂W,
i = 1, …, r, find the sequence of decisions σ* = {u(tk), a(tk) | k = 0, …, f}, where u(tk) is the test decision
on whether to make an observation and in which mode to make an observation
at time tk and a(tk) is the action
decision on where for the robot to move, that maximizes the expected
observation profit V(tf ) = E( R(t0) + …+
R(tf)), where R(ti) is the expected
reward function at time ti, along an obstacle-free channel t = { k0, ki,
…, kj, kf }, where k is the cell obtained via the cell
decomposition of W , for
a robotic sensor S
installed on a platform A
traveling from the initial configuration q0 in k0 to final configuration qf in kf .
A
novel and systematic approach has been proposed to solve Treasure Hunt
Problems. Using cell decomposition, the pruning algorithm and the
benefit-of-information function, a reduced subset of feasible solutions is
obtained in the form of a pruned connectivity tree, which can be folded
into a decision graph, such as, decision tree or in influence diagram. The
solution of the decision graph is an optimal policy for both robot motions
and sensor measurements.
Compared
to classical cell decomposition, our method accounts not only for the
geometry of the obstacles and the robots, but also for the geometry of the
targets and of the sensor field of view. A comparison example of the
decomposition is shown in Fig. 1 and 2.
Fig. 1. our
modified cell decomposition
Fig. 2 classical
cell decomposition
Conducting
the research at Duke University
is Dr.
Silvia Ferrari , Assistant Professor in Mechanical Engineering at Duke
University , and her graduate
student, Chenghui Cai.