In many tasks in machine learning, it is common to want to answer questions
given fixed, pre-collected datasets. In some applications, however, we are not
given data a priori; instead, we must collect the data we require to answer the
questions of interest. This situation arises, for example, in environmental
contaminant monitoring and census-style surveys. Collecting the data ourselves
allows us to focus our attention on just the most relevant sources of
information. However, determining which of these sources of information will
yield useful measurements can be difficult. Furthermore, when data is collected
by a physical agent (e.g. robot, satellite, human, etc.) we must plan our
measurements so as to reduce costs associated with the motion of the agent over
time. We call this abstract problem embodied adaptive sensing.

We introduce a new approach to the embodied adaptive sensing problem, in which a
robot must traverse its environment to identify locations or items of interest.
Adaptive sensing encompasses many well-studied problems in robotics, including
the rapid identification of accidental contamination leaks and radioactive
sources, and finding individuals in search and rescue missions. In such
settings, it is often critical to devise a sensing trajectory that returns a
correct solution as quickly as possible.

We focus on the problem of radioactive source-seeking (RSS), in which a UAV must
identify the $k$-largest radioactive emitters in its environment, where $k$ is a
user-defined parameter. RSS is a particularly interesting instance of the
adaptive sensing problem, due both to the challenges posed by the highly
heterogeneous background noise, as well as to the existence of a
well-characterized sensor model amenable to the construction of statistical
confidence intervals.

We introduce AdaSearch, a successive-elimination framework for general adaptive
sensing problems, and demonstrate it within the context of radioactive source
seeking. AdaSearch explicitly maintains confidence intervals over the emissions
rate at each point in the environment. Using these confidence intervals, the
algorithm iteratively identifies a set of candidate points likely to be among
the top emitters, and eliminates other points.

Embodied Search as a Multiple Hypothesis Testing Scenario

Traditionally, the robotics community has conceived of embodied search as a
continuous motion planning problem, where the robot must balance exploring its
environment with selecting efficient trajectories. This has motivated approaches
where both trajectory optimization and exploration are combined into a single
objective, which can be optimized using receding horizon control (Hoffman and
Tomlin, Bai et al., Marchant and Ramos). Instead, we consider an
alternate approach in which we formulate the problem as one of sequential
best-action identification via hypothesis testing.

In sequential hypothesis testing, the goal is to reach conclusions on many
separate questions, by iteratively collecting data. An agent is given a set of
$N$ measurement actions, each of which yields observations according to a
distinct, fixed distribution.

The agent’s goal is to learn some prespecified property of these $N$ observation
distributions. For example, in a statistical “A/B test,” a measurement action
corresponds to showing a new customer either product A or product B, and
recording their assessment of that product. Here, $N=2$ because there are just
two actions, showing product A and showing product B. The property of interest
is which product is preferred on average (B in the illustration below). As we
collect measurements on preferences, we keep track of sample averages, as well
as confidence intervals around them, described by a lower confidence bound (LCB)
and an upper confidence bound (UCB) for each product. As we collect more
measurements, we become more confident in our estimate of preference for each
individual product, and therefore our ranking between products. This suggests a
condition for concluding that product B is preferred to product A: If the LCB
for product B is greater than the UCB for product A, then we can conclude that
with high probability, B is prefered to A, on average.

In the context of environmental sensing, each action may correspond to taking a
sensor reading from a given position and orientation. Typically, the agent
wishes to know which single measurement action yields observations with the
greatest mean observed signal, or which set of $k$ actions together have the
greatest mean observations. To do so, the agent may choose actions
sequentially, using previously measured observations to favor future actions
which are most informative for discerning the actions with largest mean
observations.

At first glance, sequential best-action identification may seem like too
abstract a framework to be useful in mobile, embodied sensing agents. Indeed,
the agent can choose any arbitrary sequence of measurement actions, without
considering the potential costs—such as movement time—associated with
changing actions. However, the abstract nature of sequential best-action
identification is also its most formidable strength. By formulating the embodied
search problem in precise statistical language, we develop actionable confidence
intervals about the observation means associated with each sensing action, and
determine the set of all actions which still need to be taken before the points
of interest can confidently determined.

Our proposed approach to embodied search, AdaSearch, uses confidence intervals
from sequential best-action identification and a global trajectory planning
heuristic to both achieve asymptotically optimal measurement complexity, and
effectively amortize movement costs.

Radioactive Source Seeking

For concreteness, we will present AdaSearch in the context of the radioactive
source seeking problem with a single source. We model the environment as a
planar grid, as in the depiction below. There is exactly one high-intensity
radioactive point source (red dot). However, locating this source is difficult
because sensor measurements are corrupted by the background radiation (pink
dots). Sensor measurements are obtained by flying a quadrotor equipped with a
radiation sensor above the grid. The goal is to devise a sequence of
trajectories so that the measurements obtained from the onboard sensor allow us
to disambiguate the radioactive point source from the background radiation
sources, as quickly as possible.

AdaSearch

Our algorithm, AdaSearch, combines a global-coverage planning approach with an
adaptive sensing rule based on hypothesis testing to define these trajectories.
In the first pass through the grid, we sample uniformly over the environment.

After observing the measurements during the first pass, we can eliminate some
regions from consideration. Points are eliminated if the upper bound of our
estimated confidence interval around their mean is smaller than the largest
lower bound of any interval. This means that with high probability, they are not
the source that we’re looking for.

In the next round, AdaSearch focuses on sampling the remaining points (teal
squares) more carefully, because they are still potential source locations.

This process continues, and with each round the set of candidate source
locations shrinks until only a single point remains. AdaSearch returns this
point (enlarged red point) as the radioactive point source we were searching
for.

Due to the crisp statistical formulation of confidence, we can be sure that
under known sensing models, AdaSearch returns the correct source with high
probability. We ensure a certain level of confidence in this probabilistic
guarantee by fixing the width (in standard deviations) of the confidence bounds
around each individual region, throughout the course of the algorithm.
Furthermore, AdaSearch comes with environment-specific runtime guarantees, as we
describe in detail in our paper.

Baselines

Perhaps the most popular approach for general adaptive search problems is
information maximization (Bourgault et al.). Information maximization
methods collect measurements in locations deemed promising according to an
information theoretic criterion, and follow a receding horizon strategy to plan
trajectories. We compare AdaSearch to a version of information maximization
tailored to radiation detection: InfoMax.

Unfortunately, for large search spaces, the real-time computational constraints
of this approach necessitate approximations such as limits on planning horizon
and trajectory parameterization. These approximations may cause the algorithm to
be excessively greedy and spend too much time tracking down false leads.

To disambiguate between the effects of our statistical confidence intervals and
global planning heuristic (vs. InfoMax’s information metric and receding horizon
planning), we implement as a simple global planning approach, NaiveSearch, as a
second baseline. This approach samples the grid uniformly, spending an equal
amount of time at each grid cell.

Results

We implemented all three algorithms and simulated their performance on ten
randomized instantiations of the problem on a 64 by 64 meter grid, at 4 meter
resolution, using realistic quadrotor dynamics and simulated radiation sensor
readings.

In our experiments, we observe that AdaSearch usually finishes faster than
NaiveSearch and InfoMax. As we increase the maximum background radiation level,
the ratio of AdaSearch’s run time to NaiveSearch’s runtime continues to improve,
which matches the theoretical bounds given in the full paper.

The increase in performance between AdaSearch and NaiveSearch suggests that
adaptivity does confer advantages over non-adaptive methods. Even more
strikingly, and somewhat unexpectedly, even NaiveSearch tends to outperform
InfoMax in this problem setting. This suggests that the locally greedy nature of
receding horizon control in InfoMax is indeed hurting its performance.
AdaSearch, by contrast, gracefully blends adaptive strategies with global
coverage guarantees.

AdaSearch more generally

The successful demonstration of AdaSearch operating onboard a UAV in the context
of finding radioactive sources prompts us to ask, in what more general problem
settings will AdaSearch also perform well? As it turns out, the core algorithm
applies more broadly, even to non-robotic embodied sensing problems.

For example, consider the problem of planning a pilot program at 10 out of 100
medical clinics spread across a region. We might wish to establish these
programs in the locations with the highest rates of a particular rare disease by
conducting surveys across potential clinic locations to assess rates of illness
in each region. This is an embodied sensing problem, as diagnoses are made in
person. Resources are limited in terms of the number of human surveyors, and
there are physical constraints both on the time required to survey a group of
people, and on the travel time between towns.

A survey planner could use AdaSearch to guide the decisions of how long to spend
in each potential clinic location counting new cases of the disease before
moving on to the next, and to trade-off the travel time of returning to collect
more data from a certain town with spending extra time at the town in the first
place.

In general, AdaSearch is expected to perform well when we think that
measurements are noisy enough to warrant multiple passes through space when
collecting data. Radioactive gamma ray emissions, as well as occurances of a
rare disease, can be modeled as Poisson distributed random variables, where the
variance scales with the mean. AdaSearch easily adapts to different noise
models (e.g. Gaussian), which might arise with different applications. So long
as we can calculate or bound the appropriate confidence intervals, AdaSearch
guarantees an efficient traversal of the region to find the points of interest.

For more information about AdaSearch, please see full video at the top of the
page, and the full text of the paper at: https://arxiv.org/abs/1809.10611.