# Decision-Theoretic Approaches for Robotic Environmental Monitoring—A Survey

Near-Earth Sensing with Robots

Sung  Yoonchang  Das  Jnaneshwar  Tokekar  Pratap  [  [  [

###### Abstract

Robotics has dramatically increased our ability to gather data about our
environments. This is an opportune time for the robotics and algorithms
community to come together to contribute novel solutions to pressing
environmental monitoring problems. In order to do so, it is useful to consider
a taxonomy of problems and methods in this realm. We present the first
comprehensive summary of decision theoretic approaches that are enabling
efficient sampling of various kinds of environmental processes.
Representations for different kinds of environments are explored, followed by
a discussion of tasks of interest such as learning, localization, or
monitoring. Finally, various algorithms to carry out these tasks are
presented, along with a few illustrative prior results from the community.

Yoonchang Sung
and Jnaneshwar Das
and Pratap Tokekar copyrightowner=A. Heezemans and M. Casey, volume = xx,
issue = xx, pubyear = 2023, isbn = xxx-x-xxxxx-xxx-x, eisbn = xxx-x-xxxxx-
xxx-x, doi = 10.1561/XXXXXXXXX, firstpage = 1, lastpage = 18 survey_refs.bib
1]Department of Computer Science, The University of Texas at Austin, Austin,
TX 78712, USA<EMAIL_ADDRESS>2]School of Earth and Space Exploration,
Arizona State University, Tempe, AZ 85287, USA<EMAIL_ADDRESS>3]Department of
Computer Science, University of Maryland, College Park, MD 20742, USA;
<EMAIL_ADDRESS>
##  Chapter 1 Introduction

Environmental monitoring is a crucial field encompassing diverse applications
such as marine exploration, wildlife conservation, ecosystem assessment, and
air quality monitoring. The collection of accurate and timely data from hard-
to-reach locations and challenging environments is essential for understanding
and addressing environmental issues. Robots offer a promising solution by
enabling data collection at unprecedented spatio-temporal scales. However,
relying solely on teleoperation is impractical and limits the scalability and
effectiveness of environmental monitoring efforts. Autonomy plays a pivotal
role in unlocking the full potential of robots, allowing them to operate
independently and intelligently in these complex environments.

The goal of this survey paper is to focus on the specific problem of high-
level decision-making in autonomous environmental monitoring robots. Decision-
making at the high level involves strategic planning and coordination to
optimize data collection. By addressing these challenges, we can pave the way
for robots to autonomously navigate, explore, and gather scientific data in a
wide range of environmental monitoring applications.

While the potential benefits of autonomous environmental monitoring are
evident, several research challenges must be overcome. One such challenge is
developing effective high-level decision-making algorithms that can handle the
complexities and uncertainties of the environment while considering resource
constraints. These algorithms must enable robots to make informed decisions on
task prioritization, sensor selection, path planning, and collaboration with
other robots or human operators. Additionally, ensuring the robustness,
adaptability, and scalability of decision-making systems is critical for real-
world deployments. This survey will delve into the current state-of-the-art
decision-making algorithms, their strengths, limitations, and applicability to
environmental monitoring scenarios, aiming to shed light on the progress made
and highlight the open research problems in this field.

By focusing on high-level decision-making, this survey aims to provide
insights and understanding for researchers and practitioners in the field of
autonomous environmental monitoring robotics. The knowledge gained from this
survey can guide the development of advanced decision-making techniques,
paving the way for more effective and efficient environmental monitoring
efforts and contributing to the broader goal of sustainable resource
management and conservation.

Environmental monitoring encompasses a wide range of applications. Despite the
diversity of these applications, many decision-making problems share common
characteristics. Robotic systems operating in environmental monitoring
applications face complex decision-making challenges, requiring high-level
planning to optimize resource utilization and data collection. Effective
decision-making in these scenarios requires suitable abstractions to model the
complexities of the environment and formulate efficient solutions given the
inherent resource constraints. By identifying these commonalities, we can
uncover general principles and techniques that can be adapted and applied
across different environmental monitoring applications.

In particular, we will focus on three types of decision-making tasks that are
typical in environmental monitoring applications. First, scientists wish to
efficiently _learn_ representations for environmental processes. Then, they
want to _localize_ phenomena such as hotspots using these representations. And
finally, they want to _monitor_ change in the phenomena. For instance,
movement in the boundary of an oil spill, or the change in tree canopy size
through a season. This article is a comprehensive survey of environmental
monitoring literature, covering data-driven algorithms geared towards
deployment on cyber-physical systems such as wireless sensor networks and
networked robotic vehicles. The material is structured to serve as a tutorial
for engineers and scientists interested in applying information theoretic
algorithms to maximize the yield of scientific studies. This is particularly
necessary in the context of field data collection that can be dramatically
improved by the choice of efficient robotic sampling strategies.

###  1.1 Related Surveys

We present a compilation of relevant survey papers that discuss autonomous
monitoring applications.

[corke2010environmental] review environmental and agricultural applications
utilizing wireless sensor networks. [camilli2010bright] conduct an overview of
advanced platforms, power generation, communications, and sensing technologies
specifically for marine environmental monitoring. An environmental monitoring
survey paper ([dunbabin2012robots]) provides an introduction to various sensor
types, sensor network platforms, and commonly employed technologies for
measuring environmentally relevant variables. [lattanzi2017review] publish a
recent survey on robotic infrastructure inspection. Challenges examined in the
infrastructure inspection literature include the design of inspection robots,
trajectory planning, and handling GPS-denied environments. Precision
agriculture ([r2018research, vougioukas2019agricultural, sparrow2021robots,
oliveira2021advances, basiri2022survey]) has recently gained significant
attention in the field of robotics. Its objective is to monitor and enhance
crop health on a farm by utilizing multiple sources in a more efficient
manner. [murphy2016disaster] present robot designs, concepts, and open issues
in search and rescue for disaster scenarios. [liu2013robotic] introduce
control methods in robotic urban search and rescue, while a survey paper by
[queralta2020collaborative] focuses on multi-robot systems for search and
rescue.

In contrast to the aforementioned survey papers that focus on specific
applications, our emphasis is on providing a comprehensive algorithmic recipe
for a wide range of environmental monitoring tasks. This will serve as a
guideline for identifying the appropriate decision-making challenges,
assumptions, and algorithmic considerations applicable to various
applications.

The rest of the survey is organized as follows. In Chapter 2, we introduce
various methods of representing the environment, which can be broadly
classified into discrete and continuous approaches. In Chapter 3, we present
three primary tasks in environmental monitoring: the learning task, the
localizing task, and the monitoring task. Chapter 4 is the focal point of this
survey, where we delve into the details of various decision-theoretic
approaches based on 5W1H-driven classifications. We conclude the survey in
Chapter 5 with a discussion of future directions that merit attention and
concluding remarks.

##  Chapter 2 Robust Representations of the Environment

The algorithms used to select sensing location and planning for environmental
monitoring robots are tightly coupled with the way the environment itself is
represented. Choosing the right representation requires a careful balance
between the fidelity of the representation with how amenable that
representation is for planning and computation. In this chapter, we will
survey the commonly used environmental representations and their properties.

###  2.1 Representations

In this section, we will focus on how the phenomenon of interest is
represented. Environment representations can largely be classified into
discrete and continuous representations, although hybrid representations
(e.g., continuous space but discrete time) are also common. Planning algorithm
design and analysis depend closely on the choice of representation.

####  2.1.1 Discrete representations

Discrete representations are common due to their simplicity. The denser
resolution of the discretization becomes asymptotically closer to a ground
truth environment but requires a higher computational cost.

The most general representation of discrete environment is _grid cells_ and a
_graph_. Grid cells are used to partition a given environment into equal-size
cells. The shape of a grid cell in literature is mostly the square
[sung2019competitive], but other shapes were also employed, such as a
hexagonal cell [sujit2004search], to present more flexible robot actions. When
considering a 3D environment explored by aerial robots, a quadtree structure
can be appropriate to take into account a varying resolution of sensor
footprints [carpin2013variable, vidal2018optimized]. The higher altitude
aerial robots fly at, the sparser resolution of the quadtree.

_Occupancy grid map_ representation [thrun2003learning] is often adopted to
express free cells that robots can traverse and occupied cells as obstacles.
Octomap [hornung2013octomap] is a 3D probabilistic occupancy map that
incorporates uncertainty induced by imperfect sensing based on an octree
structure [palomeras2019autonomous]. Temporal aspect has been incorporated in
occupancy maps [arbuckle2002temporal] to model a spatiotemporal environment.
There have been recent works on continuous occupancy mapping that do not
require a predefined resolution of a map; we introduce these works in Section
2.1.2.

_Signed distance function_ computes the distance of a given point from the
boundary of the nearest object where a sign determines whether the point is
inside of the object or not. [curless1996volumetric] propose a discretized
signed distance function called signed distance fields. In comparison with
occupancy grid maps, the signed distance field representation makes collision
checking easy and can represent the contour of boundary contours accurately
[saulnierinformation].

_Graph_ representation is used to symbolically decompose a given environment
into a set of regions that robots can visit and a set of paths that connect
among the regions. In graph theoretic terms, regions and paths correspond to
nodes and edges, respectively. Edges can be either directed or undirected
depending on a problem which indicate traversability between adjacent nodes. A
cost of moving an edge can be represented by a weighted edge. Graph map
representation is also called _topological map_ that is reduced from metric
map to represent the relations among entities. _Topometric map_ is
additionally involved with local metric maps connected by edges similar to
_Voronoi graph_ [osswald2016speeding]. Grid cells are a special type of a
graph named a grid graph.

####  2.1.2 Continuous representations

A _scalar environment field_ is used to represent some quantity of interest,
such as temperature and salinity. Robots can observe those quantities from an
$n$-dimensional environment using a continuous environmental function that
maps from $\mathbb{R}^{n}$ to $\mathbb{R}$.

##### Gaussian processes

_Gaussian processes_ (GPs) are nonparametric Bayesian techniques that model a
spatio-temporal phenomenon and output some quantity of interest at any space
and time with a predicted uncertainty. A finite collection of random variables
that represent those quantities is normally distributed in GP. Due to its
simple implementation, practical usefulness and theoretical results (_e.g._ ,
near-optimality derived using submodularity [krause2008near,
Srinivas:2010:GPO:3104322.3104451]), GP has been employed with great
popularity in literature [jadaliha2013gaussian, nguyen2016information,
ma2018data]. GP has also been applied in multi-robot systems
[chen2015gaussian, luo2019distributed, ouyang2020gaussian], where each robot
only has access to local information; thus, alleviating the scalability issue
is a crucial challenge.

One notorious challenge of employing the GP is its cubic computational
complexity in the number of training samples, denoted by $\mathcal{O}(n^{3})$.
Since $n$ is usually enormous in environmental monitoring applications, many
approximation methods have been proposed to alleviate the complexity.111More
detailed summary on GP approximations can be found by [park2020gaussian]. The
most well-known approach is proposed by [snelson2006sparse] which models
smoothly-varying functions with high correlations by introducing sparse pseudo
inputs, so called inducing points, to reduce the complexity to
$\mathcal{O}(n_{i}^{2}n)$ where $n_{i}$ denotes the number of inducing points.
To model highly-varying functions with low correlations, local approximation
methods by [deisenroth2015distributed] divide an environment into
$\frac{n}{n_{i}}$ regions and apply a local GP in each region, reducing the
complexity to $\mathcal{O}(n_{i}^{2}n)$. Infinite-horizon Gaussian process
(IHGP) approximation by [solin2018infinite] is another local method which
builds a linear Gaussian state space model instead of a kernel matrix and
apply a Kalman filter. The complexity of IHGP is $\mathcal{O}(d^{2}n)$ where
$d$ is the dimension of the state space. [park2020gaussian] improve IHGP by
allowing to learn time-varying hyperparameters using a sparse and
nonstationary data stream.

In contrast to discrete occupancy maps, continuous occupancy mapping generates
a map at any resolutions without the restriction on a single-scale mapping and
thus does not suffer from pre-discretization inaccuracy. Also, discrete
occupancy maps generally consider the information on grids to be independent
of each other. Several continuous counterparts have been proposed to alleviate
those shortcomings. _Gaussian process occupancy maps_ [o2012gaussian,
wang2016fast] are proposed to handle the situation when an underlying
environment exposes a structure by encoding dependencies between grids.
_Hilbert map_ [ramos2016hilbert] is another continuous occupancy map which
projects data into the Hilbert space to preserve better local information and
allows for fast kernel approximation. Dynamic environments have also been
studied in Gaussian process occupancy maps [senanayake2017learning] and
Hilbert maps [guizilini2019dynamic]. _Bayesian Hilbert maps_
[senanayake2017bayesian] use kernels to perform Bayesian logistic regression
in a high-dimensional feature space. It reduces the computational complexity
to the cubic complexity in the number of features that are much smaller than
that of training samples. _Automorphing Bayesian Hilbert maps_
[senanayake2018automorphing] improve the accuracy over Bayesian Hilbert maps
by learning all location-dependent nonstationary kernel parameters using
variational inference. As automorphing Bayesian Hilbert maps require to
collect the entire dataset, [tompkins2020online] propose online domain
adaptation to support sequential training. Bayesian kernel inference-based
mapping by [doherty2019learning] deals with sparse and noisy sensor data
issues by inferring the state of unknown regions from neighboring regions. Its
computational efficiency over GP-based methods is highlighted, which is
logarithmic in the size of training data.

_Gaussian process implicit surfaces_ [williams2006gaussian,
hollinger2013active], a nonparametric regression model used to reconstruct
surfaces from 3D data, are adopted by [leeb2019online] to construct online
continuous mapping. The proposed map computes a probabilistic estimate of the
signed distance field and maintains a distance and its gradient which can be
useful for obstacle avoidance.

##### Modeling with basis functions

A parameterized approximation is proposed by [lynch2008decentralized] to
approximate this environmental function by a weighted sum of a finite set of
basis functions. Examples of basis functions include sinusoids in Fourier
series, wavelets, and polynomials. [jadaliha2013environmental] consider
weights as time-varying coefficient vectors to model a time-varying scalar
environment field.

##### Partial differential equations

A more realistic environmental model is needed to track dynamic plumes having
complex behaviors. [fahad2015robotic] use a Lagrangian model to capture both
time-averaged and instantaneous structures by assuming the plume to be
composed of particles. [wang2019dynamic] use an advection-diffusion partial
differential equation model to model dynamic dispersion.

Like dynamic plumes, accurate flow modeling is extremely challenging, reducing
its reliability when applied to control robots. Several control schemes have
been proposed to correct the modeling error, especially underwater
applications, such as data-driven flow models using basis functions
[chang2017motion], incompressible flow fields [lee2019online], and gyro-like
flow fields [knizhnik2022flow]. [salam2022learning] propose a method to
capture high-level features in flow-like environments where obtaining an
explicit flow representation is intricate.

Lastly, _sparsity_ in data across various domains can be utilized through a
suitable choice of feature space (_e.g._ , wavelets) to develop parsimonious
representations. If another feature space can be identified where the signal
is also incoherent, a sampling scheme can be devised to exploit the
parsimonious representations for extremely efficient ways of observing the
environment. This setting is referred to as compressive sensing and has
demonstrated significant impact in magnetic resonance imaging, with potential
applicability in environmental monitoring.

####  2.1.3 Hybrid representations

Hybrid representations are often employed to model the combination of discrete
variables (_e.g._ , environment partitions) and continuous variables (_e.g._ ,
their spatial groundings) for environmental phenomena.

_Dirichlet processes_ [teh2010dirichlet] are another nonparametric Bayesian
methods, often used for clustering problems where a cluster size is unknown in
advance. Automatically learning the number of clusters in a data-driven manner
(_i.e._ , unsupervised learning) as the task progresses is an attractive
feature for environmental monitoring applications. Several existing methods
adopt Dirichlet processes to leverage this feature as follows.
[ouyang2014multi] They propose a method that learns to partition the
environmental phenomenon into local regions based on a stationary spatial
correlation structure, which is modeled using a Dirichlet process mixture of
locally stationary GPs. [girdhar2019streaming] employ Chinese restaurant
processes, a discrete-time stochastic process that models the partition of
customers into tables in a restaurant context and is closely connected to
Dirichlet processes, to handle a priori unknown numbers of scene labels from a
discretized environment. [steinberg2011bayesian] use a variational Dirichlet
process model [kurihara2006accelerated] to cluster large quantities of
seafloor imagery.

_Topic modeling_ developed for text analysis has been adopted to generate a
summary for observations of low-dimensional descriptors to capture
semantically similar or different objects or patterns in the environment
[girdhar2014autonomous, girdhar2016modeling]. Image descriptors built by topic
modeling capture thematic changes in the scene while being robust to low-level
image changes. A distribution of spatiotemporal topics represents
observations. The objective of topic modeling is to compute the surprise score
for a newly observed image using the distance to the closest sample in the
summary in the topic space. Several extensions have been made to topic
modeling, such as multi-robot system applications [doherty2018approximate] and
a hierarchical topic model for the spatial distribution of categorical
observations (also called as the Gaussian-Dirichlet random field
[soucie2020gaussian]).

###  2.2 Properties

It is beneficial to understand and identify properties of environment due to
their huge impact on algorithm design. By doing so, we can narrow down to
particular algorithms from a large class of algorithm options and may be able
to find useful property-based guarantees that help solve a given environmental
monitoring problem. We show properties of environment that might vary greatly
depending on a problem instance.

####  2.2.1 Countability of the phenomenon

The target phenomena that the robot is tasked with monitoring can be
classified into _discrete objects_ and _continuous fields_ based on what is
monitored. Discrete objects are countable and can be represented by points,
for example, humans, animals, rocks, and fruits. Continuous fields are
uncountable and represent the density of environment attribute, such as gas,
water temperature, ocean salinity, and soil nitrogen levels. Special type of
continuous fields forms a certain region of interest with an arbitrary shape,
and often cannot be detected entirely by a single footprint of a robot sensor
due to its largeness in size. Examples of this variant include plumes of
pollutants, radioactive plumes, and fire.

####  2.2.2 (Non)-stationarity of the field

Most of environments for continuous fields vary spatially in practice.
Formally, the nonstationary property exhibits different local degrees of
smoothness in the spatial variation in different regions of environment
[ouyang2014multi]. Nonstationary versions of the covariance functions have
been proposed for GP [paciorek2004nonstationary]. [chen2022ak] design
nonstationary kernels, called the attentive kernel, for better accuracy and
uncertainty quantification. The work by [cao2013multi] exploits a spatial
correlation structure of the GP to improve the performance of their algorithm
in low spatial correlation. Specifically, they study an environment with a
higher spatial correlation along one direction than in its perpendicular
direction, called _anisotropic_ field.

####  2.2.3 Temporal characteristics

In literature, binary environment has also been considered where the
environment consists of region of interest and region of non-interest
[sung2019competitive]. This is particularly useful for coverage and
exploration where the objective is not to estimate the density of environment
but to completely cover every single point in regions of interest at least
once by the footprints of a robot sensor.

Generally, states of environment may vary over time due to external factors,
for example natural phenomena like wind and wave, and their own temporally-
varying property. The location of discrete objects and the density of
continuous fields may change temporally. To estimate time-varying states of
discrete objects, conventional state estimators, such as Kalman filters
[lynch2008decentralized], extended Kalman filters [hitz2015relaxing], and
particle filters [korner2010autonomous], can be employed, incorporating noisy
measurements. Searching for and tracking a single mobile target is still
actively studied in challenging scenarios, such as a pursuit evasion problem
[kalyanam2020graph]. As conventional state estimators are not suitable for
handling a varying number of objects, [mahler2003multitarget] proposes the
probability hypothesis density filter that simultaneously estimates both the
state and the number of objects, owing to random set theory. To avoid the
expensive exact computation of the probability hypothesis density filter,
sampling-based [dames2017detecting] and Gaussian-based [sung2021gm]
approximations have been adopted. [krajnik2015s] propose a frequency-based map
to represent the periodicity of environment states, _e.g._ , occurred by
human’s daily regular activities, that exhibit frequency spectra.

Previous work has considered both discrete time and continuous time aspects to
handle temporal dynamics in continuous fields. In case of discrete time,
[ma2018data] assume piecewise static intervals to approximate temporal
dynamics. GP is often used to account the continuous-time domain for modeling
a spatiotemporal environment representation. Most approaches using the GP add
an additional dimension to represent time so that the time domain is treated
independently of the state-space domain [binney2013optimizing,
marchant2012bayesian]. [singh2010modeling] study the effect of correlating
time with state space in terms of a covariance function in GP (_i.e._ , non-
separability). They design various covariance functions that exhibit different
combinations of stationarity and separability, and empirically conclude that
nonstationary separable covariance functions are the most suitable for
spatiotemporal GP models.

####  2.2.4 Measurement models

When the environmental monitoring task is data collection, that is, to obtain
sensor measurements or collect actual samples, the characteristics of
measurements/samples represent a given environment. Robots obtain noisy
measurements through imperfect sensors. While previous work mostly assumes a
measurement noise to be a Gaussian white noise, [wu2012robust] consider an
unknown non-Gaussian noise and propose a control method which only requires
the bounded power of noises. Samples that are physically collected by robots
from an environment can be either _in situ_ or _ex situ_ samples. In situ
samples can be analyzed online while a robot explores in a given environment.
The robot can adapt its precomputed plan using online streaming information
extracted from in situ samples. Ex situ samples, however, can only be studied
offline in the lab but at least estimate their scores based on how valuable
they are. Then, for ex situ samples, a robot should plan its trajectory to
collect the most valuable samples while considering its limited load capacity
[das2015data, flaspohler2018near]. Finally, heteroscedastic environments where
noise properties vary in state and action spaces have also been investigated
[martin2017extending].

##  Chapter 3 Using Representations to Solve Tasks

Having discussed the representation of the environments, in this section we
identify and describe three environmental monitoring tasks: _learning_ ,
_localizing_ , and _monitoring_. We then present what specific problems have
been addressed for each task in literature.

###  3.1 Learning

Environmental monitoring involves the robots exploring the environment to
gather information, either measured by an onboard sensor or physically
collected, to understand a domain of interest. From the local information
collected, global characteristics of the environment must be inferred through
some model learned from data. Therefore, deciding where to collect sensor
information or samples next is crucial. As such, learning is a necessary
component for successful environmental monitoring.

####  3.1.1 Accurate modeling

Learning an environment model is a core challenge to carrying out downstream
tasks, especially when dealing with an unknown environment. Various
statistical models can be adopted for environment modeling from noisy
observations.

Among such statistical models, _expectation maximization_ (EM) is an iterative
method to estimate the parameters of an environment model when the model
depends on latent variables. EM is particularly suitable for underwater
applications where the ocean current cannot be directly measured but estimated
indirectly via other quantities, such as position drift. [lee2019online] study
this problem and propose a Gaussian process-based EM algorithm to estimate
ocean currents for navigation and planning.

Accurate modeling is often intractable in practice; thus, approximate state
estimation methods have been proposed that simplify intractable statistics.
For example, [jadaliha2013gaussian] address the challenge of resource-
constrained sensors, outputting observations under localization uncertainty.
The analytically intractable posterior predictive statistics are approximated
by Monte Carlo sampling and Laplace’s method. They analyze the approximation
error and complexity (_i.e._ , trade-offs between the error and complexity of
Laplace approximations).

Environment modeling by multi-robot systems has been researched with tools
like a distributed consensus estimator. [lynch2008decentralized] propose a
decentralized, scalable approach to model the environment based on average
consensus estimators.

####  3.1.2 Mapping

An alternative approach to learning about the environment is to cover and
explore the entire environment (or a partial environment depending on given
constraints). Robots with limited sensing capability learn the location,
shape, and size of the environment. This process of incrementally accumulating
environment information is _mapping_ – offline mapping if the environment is
given to robots, while online mapping if the environment is not known a
priori.

####  3.1.3 Lifelong learning

One of the desired goals for any learning method is to continually learn new
behaviors and adapt and refine a model over a long period. _Lifelong learning_
refers to such capability.

[girdhar2016modeling] propose curiosity modeling for long-term exploration in
aquatic environments where most of the collected data contain uninteresting
observations. Their goal is to achieve lifelong learning behavior of the
perception model based on topic modeling, which guides the robot to locations
with high topic perplexity for better learning.

###  3.2 Localizing

Localizing an object of interest from a vast environment in environmental
monitoring is undoubtedly critical. Depending on the characteristics of an
object, we classify localization into _search and tracking_ if an object is
dynamic and _hotspot identification_ if an object is stationary.

####  3.2.1 Search and tracking

We have introduced representative _search and tracking_ methods in Section
2.2, including Kalman filters, particle filters, and probability hypothesis
density filters. As an example, refer to [van2019online] proposing a
probability hypothesis density filter-based algorithm that jointly detects and
tracks unknown radio-tagged objects.

Plume tracking regards tracking a plume (_e.g._ , radioactive dispersal and
oil spill) to search for the source of the plume. The plume’s location, shape,
and size vary as it drifts in the water current or air. [neumann2013gas]
address gas source localization with a micro-drone and propose bio-inspired
plume tracking algorithms. [hajieghrary2017information] form source seeking in
plume tracking as an information-theoretic search problem. Their objective is
to find actions for multi-robot systems that maximize the change in entropy.
[sung2019competitive] consider an oil-spill scenario where the shape and size
of the plume are unknown while its translation information is given.

_Search and rescue_ is an active research field that may not be directly
related to environmental monitoring. However, algorithms developed in search
and rescue embrace objectives and contributions desirable for environmental
monitoring, as localization is also a key challenge in search and rescue.

An extensive survey on search and rescue can be found in
[queralta2020collaborative]. [liu2013robotic] survey search and rescue in
urban applications. Some specific objectives studied in search and rescue
include maximizing search efficiency under time constraints
[meera2019obstacle], optimal deployment [macwan2011optimal], and minimizing
the mean-time-to-find and maximizing the target finding probability
[meghjani2016multi].

Harsh conditions on observing measurements have been researched, such as
[song2011time, song2012simultaneous, kim2014cooperative]. [song2011time] study
a problem of searching for a stationary target that emits short-duration
signals intermittently under a limited sensing condition. Examples include an
airplane black box and an earthquake victim sending out signals repeatedly.
[song2012simultaneous] add more challenges, such as source anonymity and an
unknown number of sources, to their previous work. They use a spatiotemporal
probability occupancy grid to model the radio source and develop a motion
planning algorithm that ensures the robot travels in high-probability regions.
They extend this for multiple robots in their subsequent work
[kim2014cooperative] where pairs of robots are considered.

####  3.2.2 Hotspot identification

Finding hotspots from the field requires efficient exploration and sampling
strategies. [low2008adaptive] propose an adaptive exploration strategy for a
team of robots to localize hotspots and learn map phenomena simultaneously.
[garcia2012online] research spatially distributed sample collection from
hotspots based on the online calculation of sample utility where science
preferences or evolving knowledge about the feature can also be incorporated.

Radio signal mapping is one of the prime applications in environmental
monitoring. Online radio signal mapping is crucial for wireless communication
to model radio signal propagation. Its primary objective is to localize the
signal source in an unknown environment. [fink2010online] propose to map
received radio signal strength in the Gaussian process using a team of mobile
robots and propose exploration (based on the gradient of the predictive
variance) and exploitation (based on the maximum likelihood estimation) as the
control law. [atanasov2015distributed] design distributed algorithms for a
team of robots to localize the source of a noisy signal. They particularly
consider two scenarios with an available signal model and a model-free one.
[al2018gradient] develop a distributed source-seeking strategy for robotic
swarms that does not require gradient estimation and measurement sharing among
robots.

Previous work has researched detecting and localizing a leak, essentially
hotspot identification. [bennetts2013towards] work on methane leak detection.
Their algorithm generates 3D concentration maps from depth measurements and
integral concentration to localize a leak.

###  3.3 Monitoring

The goal of monitoring is to observe and track the environment of interest
over time instead of mapping in the learning task that acquires a globally
consistent representation of the environment.

####  3.3.1 Persistent monitoring

_Persistent monitoring_ seeks a strategy to persistently monitor (often
changing) environments where the task is endless (or at least over a long
period). This is hard to achieve in practice due to the limited budget (_e.g._
, battery life and time); several methods are proposed to increase the length
of execution time. [ding2019heuristic] consider mobile depots to recharge
persistent robots and propose a method for minimum cost tour.
[plonski2017environment] tackle the problem of unmanned surface vehicles
tracking invasive fish under unknown obstacles and energy-efficient
exploration based on the solar map enabling energy harvest.

We introduce several persistent monitoring methods from the literature.
[smith2011persistent] propose persistent monitoring for underwater vehicles
whose objective is to minimize deviation from the planned path because of
ocean currents while maximizing the information value. [smith2012persistent]
study persistent monitoring in changing environments and propose a controller
for multiple robots as a linear combination of a finite set of basis
functions. [palacios2016distributed] develop a distributed coverage estimation
and control scheme for persistent monitoring.

Multi-robot _patrolling_ is a task that multiple robots regularly visit
predefined regions of interest. [iocchi2011multi] evaluate the state-of-the-
art patrolling algorithms in practical applications where the environment is
characterized by linear, cycle, and mixed shapes.

The goal of _boundary detection_ is to monitor the boundaries of an unknown
environment to estimate its size. [matveev2015robot] propose a sliding mode
control method monitoring unknown and time-varying environmental boundaries.

####  3.3.2 Information gathering

An information-gathering task allows active monitoring and exploration of an
environment by minimizing information-theoretic measures, such as entropy and
mutual information. [ma2018data] propose an information-theoretic dynamic data
map that captures an environment’s temporal property using the Gaussian
process. [corah2018distributed] propose distributed sequential greedy
assignment for online exploration and mapping using multi-robot teams. Their
algorithm is an approximation to sequential greedy algorithm
[singh2009efficient] efficiently when dealing with many robots.
[bourne2020decentralized] work on information-theoretic control for multi-
agent and propose a method to efficiently compute mutual information based on
dynamic programming and multi-threading techniques. We present more details
regarding information gathering in Section 4.1.2.

##  Chapter 4 Decision-Theoretic Optimization to Solve Tasks

Based on a given environmental monitoring task, one must determine an
appropriate representation of environment, formulate a desirable objective
function, and develop algorithms that can satisfy chosen objectives. We
discussed various candidates on environment representation that one can choose
from in Section 2.1. Most environmental monitoring tasks are, in fact,
decision-making problems as there may exist a number of local or global
decisions a robot must make. Decisions can be made offline before the process
starts, or online as the robot obtains new information during the process. We
design algorithms to determine decision variables in a proposed objective
function, in order to exactly or approximately maximize a task utility.

In particular, we address decision-making problems from a 5W1H perspective:
(1) where to take measurements from; (2) which tasks to be assigned; (3) what
samples to collect; (4) when to collect samples; (5) how to learn environment;
and (6) who to communicate. We introduce detailed decision-theoretic tools
from literature based on this 5W1H perspective and present how existing works
employed these tools for their specific tasks.

Figure 4.1: Taxonomy of decision-theoretic tools illustrating the span of
objectives, tasks, and decisions in relation to diverse scientific goals.

###  4.1 Where to Take Measurements from

To learn an underlying phenomenon of a given environment, a robot or a team of
robots must collect measurements (_i.e._ , sampling) from the environment
while not violating time or energy constraints. The problem of where to take
measurements from the environment can thus be considered as a path planning
problem, associated with discrete sampling events along the robot trajectory.

Among many variants on path planning problems in literature, we focus on the
following variants: (1) shortest path exploration; (2) information gathering;
(3) reward collecting; (4) online and offline coverage planning, where the
environment is not given in the former whereas it is given in the latter; and
(5) deployment for multi-robot systems.

####  4.1.1 Shortest path exploration

For environmental monitoring, one of the desired objectives is to find a
minimum length path while visiting all sampling locations under some
constraints, such as collision avoidance and limited sensing capability. The
solution of this objective naturally addresses a minimum time tour or a
minimum energy tour as they are functions of a path length.

When sampling locations are represented as a set of points, _traveling
salesman problem_ (TSP) [applegate2006traveling] can be employed to find a
shortest path that visits every sampling location exactly once to be
monitored. As TSP is NP-hard [applegate2006traveling], there exist many
approximate algorithms that one can find a reasonable solution although not
optimal. _TSP with neighborhoods_ [dumitrescu2003approximation,
tokekar2016sensor, faigl2017autonomous] allows each sampling location to have
a certain area instead of a point, assuming that values nearby a sampling
location are similar. Visiting any point in an area implies that the
corresponding sampling location is monitored; this relaxes the requirement of
visiting a sampling location precisely. TSP with neighborhoods finds
approximate solutions for the case when areas can be either overlapped or non-
overlapped. _Generalized TSP_ [noon1993efficient, yu2019algorithms] is another
variant of TSP where the task is given by a set of clusters of sampling
locations. One possibility of obtaining a cluster of sampling locations is to
sample from continuous sampling locations. The goal is to find a minimum
length path that visits exactly one sampling location from each cluster of
sampling locations. [faigl2019fast] recently propose heuristics for
approximate solutions to the generalized TSP with neighborhoods where the
objective is to visit multiple goals in 3D environments.

A major limitation on TSP-based data collection introduced above is that all
sampling locations are assumed to be stationary and known a priori. There are
some previous methods for moving nodes in a TSP graph [smith2009dynamic,
hammar1999approximation, helvig2003moving] but limited settings, _e.g._ , all
nodes moving with the same speed and direction. Also, most guarantees do not
hold for an unknown and varying number of sampling locations. To address
related challenges, stochastic variants of TSP have been proposed, such as
stochastic radius of nodes for TSP with neighborhoods [kamousi2013euclidean],
stochastic node locations [citovsky2017tsp], and stochastic occurrence of
visiting a node [pavone2009stochastic].

The above TSP-related research assumes the robot’s sensing ability to be
short-sighted or mostly does not consider sensing distance. Some approaches
still have a restricted assumption that the robot can observe any points in
the environment as long as no obstacles lie between them, which is
$360\degree$ and unlimited sensing range, but exhibit desirable algorithmic
guarantees in the spirit of computational geometry. We introduce recent
approaches that alleviate these sensing range restrictions.

The _art gallery problem_ [o1987art] can be applied to a static sensor
placement problem whose objective is to find a minimum cardinality of a set of
sensing locations in a given environment such that every point in the
environment is visible from at least one sensing location in a chosen set.
[arain2015efficient] propose fan-shaped sensing regions via convex relaxation,
allowing overlapping field-of-view regions from multiple sensing locations.
Once a set of sensing locations is determined, they employ a TSP solver to
find a sequence of sites as a robot trajectory, commonly used in the art
gallery problem for robotic applications.

In contrast to the art gallery problem not involved with the sensor’s
mobility, its special variant, _watchman route problem_ [chin1986optimum], can
directly be applicable to the mobile robotics domain as its goal is to find a
shortest path so that every point in the environment is visible from at least
one sensing location in the path. [tokekar2015visibility] propose an optimal
algorithm and a constant factor approximation to observe a set of target
points using multi-robot systems equipped with an omnidirectional camera of
unlimited sensing range. The same visibility restrictions are considered in
[zhang2019tree] to address the problem of maximizing the visibility of a robot
when an adversarial target exists. Previous methods relax the visibility
conditions by restricting a sensing distance to be $d$: _$d$ -watchman route
problem_ [tan2003finding] that only observes the polygonal boundary of the
environment, and _$d$ -sweeper route problem_ [ntafos1992watchman] in which a
circular robot of radius $d$ sweeps the environment. A multi-robot version
with $d$-visibility is studied in [faigl2010approximate].

Among motion planning algorithms, _roadmap_ methods developed for path
planning (_e.g._ , probabilistic roadmap method [kavraki1996probabilistic])
have been adopted for environmental monitoring. A set of nodes is randomly
generated from the configuration space of the robot and is determined whether
it is in the free space. Graph search techniques are used to find feasible
paths from a start configuration to a goal configuration and choose the
shortest path among found paths. [mishra2016battery] improve a roadmap-based
approach for better scalability in handling battery constraints. In motion
planning, various decomposition techniques besides roadmap planning have been
proposed and adapted to environmental monitoring, such as boustrophedon cell
decomposition [strimel2014coverage] and Morse decomposition [acar2002sensor].
For a more detailed survey on motion planning algorithms, see
[galceran2013survey].

####  4.1.2 Information maximization

Information gain is frequently used to determine where to take measurements.
That is, solving a path planning problem to maximize the information gathered
along the trajectory, called _informative path planning_ (IPP).

An exploration process has been interpreted as a task of reducing the
uncertainty associated with the environment (_i.e._ , uncertain knowledge
about occupancy) to model and predict environmental phenomenon by adopting
fundamental quantities in information theory, such as entropy and mutual
information, used to represent the uncertainty. In case of the entropy, an
entropy value is assigned to each point in the environment and indicates that
a higher value implies a more uncertainty in the accessibility of the point
[bhattacharya2014multi]. On the other hand, mutual information is used to
evaluate the (expected) information gain of unsensed locations with respect to
a specific configuration of robots [bai2016information]. The goal of IPP is to
generate trajectories for robots by actively sensing environmental phenomena
that can either minimize the entropy or maximize the mutual information. This
is equivalent to gathering the most informative observations over path.

[krause2008near] propose a simple greedy algorithm of sequentially choosing
sensing locations that maximizes the mutual information, providing a formal
guarantee of near-optimal performance by exploiting the _submodularity_
[nemhauser1978analysis]. The notion of submodularity has been exploited often
in this line of research. A set function $F:2^{V}\rightarrow\mathbb{R}$ where
$V$ denotes a set of sampling locations is said to be submodular if it
satisfies: $F(A\cup x)-F(A)\geq F(B\cup x)-F(B)$ where $A\subseteq B$ and
$x\not\in A,\ B$. If a chosen utility function for a given environmental
monitoring task follows a submodular set function $F$ and satisfies
_monotonicity_ , it is proven by [nemhauser1978analysis] that a simple
sequential greedy algorithm finds a near-optimal set of sampling locations,
satisfying that $F(A_{\rm greedy})\geq(1-1/\epsilon)F(A_{\rm opt})$.

The same authors of [krause2008near] have proposed various variations to study
different aspects of the general submodular maximization problem. To overcome
_non-adaptability_ , [golovin2011adaptive] design a greedy algorithm for
adaptive submodular maximization where they allow to adjust the policy based
on currently available information. They also develop an exploration-
exploitation framework for nonmyopic active learning of the Gaussian process.
The theoretical bound depends on the difference between active learning and a
priori design strategies [krause2007nonmyopic]. Exploration implies decreasing
the uncertainty about model parameters, while exploitation implies finding a
near-optimal policy for sampling. In their subsequent work, [krause2008robust]
study minimizing the maximum posterior variance in Gaussian process regression
for outbreak detection, which highlights the _robustness_ of their algorithm.
They show the efficient performance of their algorithm with approximation
guarantees. [calinescu2011maximizing] investigate monotone submodular
maximization given _matroid constraints_.

Additional practical challenges have also been studied in the general IPP
problem. [binney2013optimizing] consider time-varying fields and edge-based
samples where the robot is allowed to collect samples while traversing from
one node in the search graph to another. [atanasov2014information] design a
non-myopic IPP algorithm that incorporates sensor dynamics. They show
suboptimality based on concavity, which has the trade-off between complexity
and optimality. [saulnierinformation] propose a truncated signed distance
field-based active exploration algorithm. They optimize a sensor trajectory
using a deterministic tree search that evaluates the information gain and
applies branch-and-bound pruning for efficient search.

Similar to the motivation in adaptive submodular maximization in
[golovin2011adaptive], previous work has researched online IPP that can modify
the current plan adaptively as new information is obtained. [ma2018data]
propose a planning and learning algorithm for persistent monitoring tasks.
Their method plans a trajectory that maximizes the mutual information and
learns a Gaussian process-based datamap to model a spatiotemporal field while
tuning hyperparameters online. [popovic2020informative] study the monitoring
objective of mapping discrete and continuous variables on the terrain in the
IPP framework. They also focus on strategies to modify plans online for
adaptive scenarios. [schmid2020efficient] propose an optimal motion planning-
driven IPP algorithm to overcome the suboptimality of sampling-based methods.

Multi-robot systems have also been investigated for more efficient IPP
solutions. [cao2013multi] develop an active sensing IPP algorithm for multiple
robots based on entropy and mutual information criteria. They prove guarantees
on the trade-offs between active sensing performance and time efficiency.
[corah2018distributed] extend the previous sequential greedy algorithm that
works only for a single robot to multiple robots and prove the near-optimality
guarantee for a multi-robot version. [nguyen2016information] propose a
resource-constrained adaptive sampling strategy for a team of mobile robots.
Their method has a theoretical guarantee on the upper and lower bounds of the
solution based on the conditional entropy. [low2008adaptive] present an
adaptive model-based exploration method that plans non-myopic multi-robot
paths by minimizing the expected sum of posterior variances over all
locations. Additional challenges have also been considered within the scope of
multi-robot IPP, such as uncertainty of a hidden state over a priori unknown
horizon [kantaros2021sampling], a phenomenon of interest not being able to be
observed directly [malencia2022adaptive], adversarial environments
[schlotfeldt2021resilient], unreliable communication among robots
[woosley2020multi] and limited communication ranges among robots and control
uncertainty [dutta2021opportunistic].

Multi-objective problem in information maximization has been studied by
[gautam2017science] that minimizes the path length while maximizing the
information gain for budgeted exploration. They use evolutionary algorithms to
solve this Pareto optimization. [meera2019obstacle] propose the problem of
maximizing the information gain and minimizing the collision cost.

_Ergodic theory_ regards time-averaged behavior along the trajectory of a
dynamical system with respect to the space of all possible states of the
system [miller2015ergodic]. Ergodicity can be used as another information
metric for environmental monitoring so that the robot distributes the allotted
time to regions proportional to the expected information gain in those
regions. Ergodicity can also address both exploration and exploitation for
coverage using the expected information density. The advantage of using
ergodicity over other information metrics is that ergodicity naturally encodes
the behavior of spending more time to explore near regions with high expected
information instead of only visiting the highest information region. Previous
work has shown the effectiveness of ergodicity in terms of active sensing,
including trajectory optimization of ergodic exploration for nonlinear and
deterministic control systems [miller2015ergodic], receding-horizon ergodic
exploration for both coverage and target localization [mavrommati2017real],
and ergodic exploration for multi-robot systems [abraham2018decentralized].

####  4.1.3 Reward maximization

When collecting a sample is associated with reward, one can address
environmental monitoring as a reward maximization problem. We would like to
find the trajectory of a robot that maximizes the reward from collected
samples while satisfying constraints, such as a limited energy budget, if it
exists. Examples of additional objectives studied in reward maximization
include maximizing a robot lifetime [jadaliha2013environmental] and reducing
resource usage [parker2013estimation].

Reward maximization has been studied in computational geometry; one of them is
called the _prize collecting_ traveling salesman problem [balas1989prize],
whose objective is to find a subset of cities to visit such that travel costs
and net penalties, getting a prize when visiting a city and a penalty when
failing to visit a city, can be minimized.

Reward maximization can be interpreted as cost minimization from the control
theory perspective. An optimization-based approach has been studied to
minimize some cost functions for optimal data collection.
[leonard2007collective] present a data collection scheme that computes optimal
multi-robot paths by minimizing the error in a model estimate of the sampled
field.

Another variant is the _orienteering problem_ , where the goal is to maximize
the reward collected until the budget is exhausted when a limited budget
(_e.g._ , time or fuel) is given. [chekuri2005recursive] propose a first
recursive greedy algorithm for the orienteering problem where the objective
function is a submodular set function. They prove their algorithm runs in a
quasi-polynomial time and its approximation is $\mathcal{O}(\log\rm{OPT})$.
Various methods in the robotics community built _submodular orienteering_
algorithms on the result of this recursive greedy algorithm, such as
[binney2013optimizing]. The previous work mostly considers the reward function
of a sampling location to be independent with rewards in other locations.
[yu2016correlated] propose a correlated orienteering problem where a quadratic
utility function is considered to capture a spatial correlation. Other
practical challenges have been addressed in the orienteering problem, such as
orienteering with neighborhoods [faigl2016self], service time dependant
rewards [mansfield2021multi], uncertain rewards [liu2021team], unknown rewards
[wilde2021learning], and uncertain environment model [peltzer2022fig].

Another problem, but closely related to the orienteering problem, is the
_optimal tourist problem_. Compared to the orienteering problem, the optimal
tourist problem treats the reward function as a function of the time spent at
the sampling location. [yu2015anytime] investigate the optimal tourist problem
based on two complementary problems. The first problem solves the same
objective as in the orienteering problem, and the second problem minimizes the
time for gathering a predetermined reward amount.

_Multi-armed bandit_ (MAB) regards the problem of finding an arm associated
with an unknown black-box function out of a fixed number of arms that
maximizes the expected gain (or reward) when a finite number of arm
evaluations is allowed. Thus, MAB naturally addresses exploration versus
exploitation dilemma. To design algorithms having useful theoretical bounds in
MAB, the notion of _regret_ is defined to measure the expected gap of the
collected rewards between the optimal strategy and a designed algorithm. The
_upper confidence bound_ (UCB) algorithm is a well-known algorithm that gives
a theoretical upper bound on regret, owing to the principle of optimism in the
face of uncertainty. One can choose where to evaluate the black-box function
next according to UCB. [reverdy2014modeling] propose MAB with transition costs
and on graphs which can be appropriate for robotics applications.
[landgren2016distributed] study distributed MAB for cooperative decision-
making based on the consensus algorithm. However, a black-box function of one
arm is independent of that of neighboring arms in this setting.

Among various approaches to solve MAB, _Bayesian optimization_ is often used
for robotics environmental monitoring as it considers spatial correlation
between arms. It is a sequential sensor placement strategy for global
optimization of unknown black-box functions, used for Bayesian experimental
design and active learning. Bayesian optimization version of the UCB algorithm
is proposed by [Srinivas:2010:GPO:3104322.3104451] using the Gaussian process
(GP) to model the correlation of the environment, called GP-UCB. The
acquisition function (_i.e._ , surrogate objective function) to determine
which location to sample next follows this functional form:
$\mu(x)+\kappa\sigma(x)$, where $\mu(x)$ and $\sigma(x)$ are the mean and the
standard deviation at location $x$. The weight parameter $\kappa$ balances the
trade-off between exploration and exploitation. The next sampling location $x$
can be determined by maximizing the acquisition function.

[marchant2012bayesian] also incorporate the GP in Bayesian optimization for
robotics environmental monitoring. They design a new acquisition function,
called distance-based UCB, to reduce the total travel distance. The adaptive
sampling strategy proposed by [tan2018gaussian] is based on cross-entropy
trajectory optimization, whose objective is the same as GP-UCB. When unmanned
aerial vehicles are considered, _multi-fidelity GP-UCB_ [kandasamy2019multi]
has been studied to take into account different fidelity of sample values
observed at different altitudes of the robot [wei2020expedited,
sung2021environmental].

In some cases, the monitoring task would not necessarily be to find maximum
value points in the environment, but to find regions where values of points in
regions are above a predefined threshold value. The estimation of those
regions is referred to _level set estimation_ (LSE). [gotovos2013active]
employ GP to model the underlying function and formed LSE as a sequential
decision problem, which is inherently similar to GP-UCB
[Srinivas:2010:GPO:3104322.3104451]. They also present two extensions to LSE
where the first extension considers the threshold level implicitly defined as
a function of the maximum value, and the second one gathers a batch of
samples. [hitz2014fully] study the path planning aspect for the LSE algorithm
to monitor temporal and spatial dynamics of harmful cyanobacterial blooms in
lakes. They exploit dynamic programming to develop a receding horizon path
planner for LSE.

In sequential decision-making, _Markov decision process_ (MDP) computes an
optimal policy for the robot when the transition model and the reward model
are known. If the state of the target function is not fully observable, the
belief can be used to represent the state, _i.e._ , _partially observable_ MDP
(POMDP). [marchant2014sequential] formulate sequential Bayesian optimization
as POMDP. They apply _Monte-Carlo tree search_ (MCTS) and UCB for trees to
handle continuous state and observation spaces for spatial-temporal
monitoring. [morere2017sequential] redefine the reward function as a trade-off
between exploration and exploitation of gradients in the form of Bayesian
optimization POMDP. They employ GP and MCTS to allow continuous non-myopic
planning. As MCTS is limited to discrete actions, in their subsequent work
[morere2018continuous], they propose dynamically sampling promising actions
based on MCTS to achieve continuous action spaces. This approach is
incorporated by kernel-based trajectory generation from the theory of
reproducing kernel Hilbert spaces which yields the properties of smoothness
and differentiability. [flaspohler2019information] propose a POMDP algorithm
to localize and collect globally maximal samples from unknown and partially
observable continuous environments. [lauri2020multi2] study multi-agent active
information gathering by policy graph improvement in a POMDP setting.

####  4.1.4 Offline/online coverage planning

Robotic coverage is often used in environmental monitoring when one is
interested in observing all points in the environment at least once using a
robot sensor. In most cases, a finite field-of-view (FOV) of the sensor and
deterministic sample values are considered so that the focus is on designing a
robot trajectory that covers the entire environment in minimum time. Previous
work has analyzed the algorithmic aspect of their proposed algorithms, such as
_completeness_ and _competitiveness_. Coverage planning can be differentiated
depending on whether the information (_e.g._ , size and shape) of an
environment is available a priori (_i.e._ , _offline exploration_) or obtained
on the fly (_i.e._ , _online exploration_).

In offline exploration, the size and shape of the environment as well as the
size of the FOV of the sensor are given. If a designed algorithm is
approximation algorithm, _approximation ratio_ can be investigated, _i.e._ ,
the performance ratio between the approximation algorithm and optimal
solution. When the sensor has a symmetrical 2D FOV, such as circular FOV,
_Boustrophedon cellular decomposition_ [choset2000coverage] finds a complete
coverage path, also known as lawn mowing [bormann2018indoor].
[strimel2014coverage] propose complete battery-constrained sweep planning for
a single robot, which is the extension to the general boustrophedon
decomposition. This requires the assumption that a limited environment the
robot can cover completely with a single battery exists and that a recharging
station exists. [wei2018coverage] revisit a similar problem where the robot is
allowed to charge at the recharging station, but their objective is to
minimize the number of paths (_i.e._ , the new path starts after recharging)
and then to minimize the path length as the second objective. Their approach
is based on the traveling salesman problem over the grid map. They show the
approximation ratios of $4$ and $8$ for minimizing the number of paths and the
path length, respectively, for contour-connected environments. For arbitrary
environments, they prove $4(2r+4)$ and $8(2r+4)$–approximation ratios, where
$r$ is the number of reflex nodes. [hameed2014intelligent] develops an energy-
efficient coverage algorithm in 3D that considers terrain inclinations and
outputs the optimal driving direction by minimizing the total energy
consumption via the genetic algorithm.

In case of multi-robot exploration, optimizing the number of robots or the
amount of energy required is proven to be NP-hard [fraigniaud2006collective].
[mishra2016battery] study battery-constrained coverage for multiple robots
that is based on the roadmap approach. They take into account the
heterogeneous behavior among robots where there are worker and helper robots.
Their algorithm computes how long robots can explore before recharging without
having to set the battery threshold explicitly. [karapetyan2018multi] propose
heuristic algorithms for multi-Dubins vehicles that can evenly distribute
workloads among robots. [agarwal2020line] design a heuristic-based
approximation algorithm of multiple robots for line coverage, where the robots
must visit all points of linear environment features such as road networks and
power lines. Continuous 2D polygonal environment has been studied by
[farias2020planar] where they propose multi-robot navigation from source to
sink by computing the continuous maximum flow.

In online exploration, no prior information about the environment is
available, and therefore, the robot needs to adapt its plan as new information
is obtained on the fly. There are algorithms that are incomplete, _i.e._ , not
guaranteeing the complete coverage, but incorporate other challenges.
[sim2009autonomous] propose vision-based exploration strategies in combination
with SLAM, and employed a hybrid map for both localization and safe
navigation. Greedy and iterative strategies are demonstrated.
[cesare2015multi] study frontier-based exploration for multiple UAVs under the
limited communication and battery constraints. They introduce heterogeneous
behavior for efficient planning that robots can switch from four states
(_i.e._ , explore, meet, sacrifice, and relay). [hassan2019ppcpp] consider a
scenario where unexpected changes occur, such as the sudden appearance of
stationary or dynamic obstacles in an environment.

When a given problem is NP-hard in online setting, competitiveness is a useful
algorithmic guarantee that measures a theoretical gap from the unknown optimal
solution. The competitive ratio is the worst-case ratio between the
performances of the proposed online algorithm and the optimal offline
algorithm. There is previous work that proposes complete algorithms but
without a competitive guarantee. [bender2002power] tackle a problem of
exploring and mapping an unknown environment when the node labels are not
given. They define the notion of a _pebble_ to identify a node label. Although
their approach is for a single robot, they prove that only one pebble is
sufficient if an upper bound on the number of nodes (denoted by $n$) is known
or $\Theta(\log\log n)$ pebbles are both necessary and sufficient otherwise.
[das2007map] propose a strategy to construct a labelled map by using initially
dispersed robots in two stages: robots firstly exploring and marking nodes and
secondly sharing information to combine the partial maps. Their analysis
requires an assumption that the size of the graph is co-prime with the number
of robots and yields a deterministic solution irrespective of the structure of
the graph. [jensen2019effects] study different communication models, ranging
from the global communication to no direct communication, and evaluated
proposed algorithms empirically. The problem proposed by [osswald2016speeding]
does not explore a completely unknown environment. A topo-metric map that
provides background information is given by the user. They propose the faster
exploration strategy based on TSP by exploiting this information.
[lee2016structured] design distributed exploration algorithms of multiple
robots based on triangulating an unknown environment. They address two related
problems: the problem of minimizing the number of robots for covering the
entire environment when the number of available robots is not bounded a
priori; the problem of maximizing the covered area if the number of available
robots is fixed. They show that the competitive ratio of the former is $3$
while the latter does not have one. They also present performance guarantees
on the coverage of the environment, exploiting the dual graph of the
triangulation with respect to the original geometric space.
[umari2017autonomous] study unknown environment exploration based on multiple
rapidly-exploring randomized trees. They construct local and global trees for
efficient frontier detections.

We present a list of competitive algorithms for multi-robot online
exploration. Often, the tree structure is used to analyze the competitiveness,
_i.e._ , tree exploration. The competitive ratio differs depending on the
definition of cost (_e.g._ , the maximal time or the maximal energy taken to
explore the environment) and the sensing model (_e.g._ , (1) one can observe
up to incident edges from the current node and (2) one can observe up to
neighboring nodes). For communication among robots, two models are generally
assumed: global communication if robots can exchange information of each other
at any time and local communication if robots must be simultaneously on the
same node [das2015collaborative]. Another popular communication model is to
introduce bookkeeping devices that can write and read information on visited
nodes. Let $n$ be the number of robots. [fraigniaud2006collective] call this
_write-read communication_ and propose a
$\mathcal{O}(\frac{n}{\log{n}})$–competitive algorithm that minimizes the
exploration time with the sensing model (1). They also prove the lower bound
of $2-1/n$. [brass2011multirobot] also use the same sensing model and improve
the competitive ratio to $2e/n+\mathcal{O}((n+r)^{n-1})$, where $e$ and $r$
denote the number of edges and the radius. [dynia2007robots] improve the lower
bound to $\Omega(\frac{\log{n}}{\log{\log{n}}})$. They also propose a
$4-2/n$–competitive algorithm when the cost is the maximal energy of a robot.
[higashikawa2014online] develop a
$\frac{n+\lfloor\log{n}\rfloor}{1+\lfloor\log{n}\rfloor}$–competitive
algorithm of multi-robot exploration for a static plume when the time cost is
considered under the local communication. This competitive ratio is extended
by [sung2019competitive] for a translating plume to
$\frac{2(s_{r}+s_{p})(n+\lfloor\log{n}\rfloor)}{(s_{r}-s_{p})(1+\lfloor\log{n}\rfloor)}$,
where $s_{r}$ and $s_{p}$ are the speed of the robot and that of the plume,
and to
$\frac{2(s_{r}+s_{p})(18n+\lfloor\log{n}\rfloor)}{(s_{r}-s_{p})(1+\lfloor\log{n}\rfloor)}$
if the plume shape is not restricted to grid cells but an arbitrary shape.
[preshant2016geometric] study the environment that is an orthogonal polygon,
proposing the competitive ratio of $\frac{2(\sqrt{2}n+\log{n})}{1+\log{n}}$.
[megow2012online] analyze the competitive ratio for any general graphs with
arbitrary weights using the DFS. They also study the cases of general graphs
with bounded genus. [das2015collaborative] address the problem of minimizing
the team size, given a limited energy, that can explore an unknown
environment. Denoting the amount of energy as well as the maximum possible
tree height by $B$, they show a $\mathcal{O}(\log{B})$–competitive algorithm.
[mahadev2017mapping] develop a $\mathcal{O}(\log{D}/\log\log{D})$–competitive
algorithm in $1$ dimension, given an unknown distance $D$, for MR imaging
while considering two different and independent costs for moving and for
measuring. [shnaps2016online] study battery-constrained sweep planning. The
robot starts from the recharging station, returns to it when the battery level
becomes low, and continue the coverage task. They propose $(L/S)$–competitive
algorithm for a mobile robot, where $S$ is the size of the robot and $L$ is
the path length that the robot can move with a full battery charge. They also
analyze the competitive ratio for online tethered coverage where a robot of
size $D$ is tethered at a fixed point by a cable of length $L$
[shnaps2014online]. They prove upper and lower bounds on the competitive
ratio. For the sake of the complete survey, we summarize the competitiveness
of various problems and algorithms in Table 4.1.

Table 4.1: Online exploration algorithms with the proposed competitive ratio (CR). $n$ is the number of robots; $c$ is the number of critical points to observe; $e$ is the number of edges; $r$ is the radius; $s_{r}$ and $s_{p}$ are the speed of the robot and that of the plume; $g$ implies that graphs of genus at most $g$; $B$ denotes the amount of energy as well as the maximum possible tree height; $D$ is an unknown distance; $S$ is the size of the robot; $L$ is the path length that the robot can move with a full battery charge; and $\epsilon$ is a nonnegative value. UB and LB stand for the upper bound and the lower bound, respectively. Ref. | Problem | CR
---|---|---
[lee2016structured] | Minimizing the number of robots for covering all of | $3$
the region
Maximizing the covered area with a fixed number of | Not provided
robots
[plonski2017environment] | Navigation around an unknown obstacle | $\mathcal{O}(1)$
Energy-efficient exploration of the solar map of the | $\mathcal{O}(\log{c})$
environment
[fraigniaud2006collective] | Minimizing the time of multi-robot tree exploration | $\mathcal{O}(\frac{n}{\log{n}})$
LB: $2-1/n$
[brass2011multirobot] | Minimizing the time of multi-robot tree exploration | $2e/n+\mathcal{O}((n+r)^{n-1})$
LB: $\max(2e/n,2r)$
[dynia2007robots] | Minimizing the time of multi-robot tree exploration | $\Omega(\frac{\log{n}}{\log{\log{n}}})$
Minimizing the energy of multi-robot tree exploration | UB: $4-2/n$
[higashikawa2014online] | Minimizing the time of multi-robot tree exploration | UB: $\frac{n+\lfloor\log{n}\rfloor}{1+\lfloor\log{n}\rfloor}$
LB: $\lceil\frac{n}{1+\lfloor\log{n}\rfloor}\rceil-\epsilon$
[sung2019competitive] | Minimizing the time of multi-robot tree exploration | UB:
of a translating plume | $\frac{2(s_{r}+s_{p})(n+\lfloor\log{n}\rfloor)}{(s_{r}-s_{p})(1+\lfloor\log{n}\rfloor)}$
Minimizing the time of multi-robot tree exploration of | UB:
a translating arbitrarily-shaped plume | $\frac{2(s_{r}+s_{p})(18n+\lfloor\log{n}\rfloor)}{(s_{r}-s_{p})(1+\lfloor\log{n}\rfloor)}$
[preshant2016geometric] | Maximizing the coverage area where the envionment | UB: $\frac{2(\sqrt{2}n+\log{n})}{1+\log{n}}$
is an orthogonal polygon |
[megow2012online] | Minimizing the time of multi-robot exploration of | UB: $2(2+\epsilon)(1+2/\epsilon)$
general graphs with arbitrary weights
Minimizing the time of multi-robot exploration of | UB:
general graphs with bounded genus | $2(2+\epsilon)(1+2/\epsilon)(1+2g)$
[das2015collaborative] | Minimizing the team size of multi-robot tree | $\mathcal{O}(\log{B})$
exploration given a limited energy | $\Omega(\log{B})$
[mahadev2017mapping] | Minimizing the moving and measuring costs of | $\mathcal{O}(\log{D}/\log\log{D})$
multi-robot exploration in 1 dimension
[shnaps2016online] | Minimizing the time of a single-robot battery- | UB: $L/S$
constrained coverage when recharging is allowed | LB: $\log{(L/4S)}$
[shnaps2014online] | Maximizing the coverage area using a robot of size $D$ | UB: $2(L/D)$
when tethered at a fixed point by a cable of length $L$ | LB: $\log{(L/D)}$
[gul2022online] | Watchman route problem where there is a convex | UB: $89.83$
polygonal obstacle
[icking2005exploring] | Online milling problem | UB: $\frac{4}{3}$
[kolenderska2009improved] | Online milling problem | UB: $\frac{5}{4}$

Another perspective to approach the coverage problem is whether the robot is
constrained to move only within the boundary of the environment, or allowed to
move outside the boundary. The former is _milling_ and the latter is _lawn
mowing_. In milling, [arkin2000approximation] present $2.5$–approximation
algorithm for offline milling with a single robot. [arya2001approximation]
develop an approximation algorithm for offline milling for multiple robots.
[icking2000exploring] propose a strategy that yields a competitive tour for
online milling of an polygon which may contain holes with a single robot.
[icking2005exploring] present a $\frac{4}{3}$–competitive algorithm for online
milling of polygons without holes. [kolenderska2009improved] improve upon this
to give an online milling algorithm with a competitive ratio of $\frac{5}{4}$.
In lawn mowing, [arkin2000approximation] present $(3+\epsilon)$–approximation
algorithm for offline lawn mowing with a single robot. [reggente20103d] build
three-dimensional gas distribution maps from gas sensor and wind measurements
obtained with a mobile robot.

_Next-best-view_ (NBV) planning is online planning to reconstruct a 3D
environment, not assuming a prior model of the environment
[bircher2018receding], which has been extensively studied for 3D object
reconstruction [vasquez2017view]. Although NBV planning is not precisely
coverage planning, it often covers the environment as much as possible in
pursuing better 3D reconstruction. Every time the robot receives a new scan,
the robot evaluates a set of candidate viewpoints based on the sensor
specification and the utility of each viewpoint. Once one of the viewpoints is
chosen, the robot navigates to the designated viewpoint to obtain a new scan
which will be incrementally registered to the previous scans.
[vidal2018optimized] propose quadtree-based map representation for efficient
NBV planning. Subsequently, they develop an NBV planning algorithm for
exploration of complex underwater environments [palomeras2019autonomous].
[meng2017two] design a two-stage NBV planning algorithm based on heuristic
information gain in an unknown 3D environment. The two-stage algorithm
consists of frontier-based boundary coverage and a pathfinder using a TSP
solver. Their algorithm aims at both the exploration and reconstruction of 3-D
unknown environments. Most NBV planning copes with a single-object scene;
[heng2015efficient] propose an efficient planning algorithm achieving two
objectives of exploration and coverage for multi-object scenes.
[best2018online] address multi-robot path planning to observe a set of
continuous viewpoint regions maximally. Their polynomial-time algorithm
jointly finds the nodes and their sequence and allocates them to robots.
[lauri2020multi] formulate multi-sensor NBV planning as matroid-constrained
submodular maximization. [dharmadhikari2021hypergame] form a game between the
environment and the robot such that the environment provides unknown future
challenges, and the robot finds the best policy (_i.e._ , exploration and
visual search) without knowing which challenge it will face.

####  4.1.5 Deployment

To determine how to cooperatively distribute measurements for multiple robots,
_deployment_ algorithms have been developed to efficiently generate
trajectories of robots. Among various deployment methods, _Voronoi-based
coverage_ has drawn particular attention as it exhibits desirable behaviors
for multiple robots such that algorithms are adaptive, distributed,
asynchronous, and provably correct. Voronoi-based coverage is built upon
Voronoi diagram where the environment is equidistantly partitioned into
closest pairs of robots. Voronoi-based coverage is firstly proposed by
[cortes2004coverage], called _Lloyd’s algorithm_ , where the goal is to find
an optimal sensor allocation of the environment of interest. Following the
Voronoi diagram principle, this allocation can be achieved by partitioning the
domain such that each robot is assigned to one partition.
[bhattacharya2014multi] generalize the discrete-time Lloyd’s algorithm
proposed by [cortes2004coverage] to handle a non-convex environment in non-
Euclidean space due to obstacles. They prove the stability of their control
law for coverage on Riemannian manifolds with boundaries.
[elwin2019distributed] propose a distributed algorithm based on a finite
element method that accounts for the spatial correlation between measurements
and estimation locations. Their main focus is to reduce the memory consumption
and communication requirements of robots by incorporating the spatial
correlation. Still, the previous studies remain on how to learn a spatial
field and cover it simultaneously optimally as an open problem, which
[santos2021multi] address. Additional challenges in Voronoi-based coverage
have also been addressed: connectivity constraints in communication among
robots [luo2019voronoi] and energy constraints [jensen2020near]. A detailed
survey can be seen in [paley2020mobile].

####  4.1.6 Risk-averse planning

When monitoring hazardous environments, safe planning for robots is desirable
to avoid risky situations as much as possible while still achieving the task
goal, such as colliding with obstacles. Worst-case scenarios have been
analyzed in robust optimization and formal verification. Instead of focusing
on the worst-case behavior, which often results in a conservative plan,
various risk measures have been proposed, such as _value at risk_
[jorion2007value] and _conditional value-at-risk_
[rockafellar2000optimization], for stochastic risk management. Here, we
present existing work specific to environmental monitoring.

[hernandez2019online] propose a risk objective function that incorporates both
the length and safety of the path in underwater vehicle applications.
[ono2014safe] investigate safe path planning for marine robots. To avoid
capsizing and bow-diving, they propose a method of classifying safe velocities
and unsafe velocities. They then adopt model predictive control for planning a
path. [papachristos2019localization] research belief space planning for aerial
robotic uncertainty-aware path planning. Their algorithm ensures mapping
consistency while exploring an unknown environment. [hollinger2016learning]
propose a risk-aware Gaussian process to learn the uncertainty in ocean
current prediction for safe navigation. [somers2016human] develop a risk-
averse marine data collection method given by human operator’s preferences but
refined by probabilistic planning with nonparametric uncertainty modeling. A
more detailed survey can be found in [zhou2021multi].

_Chance-constrained optimization_ is one of the optimization techniques where
some constraints dictate the probability of having risky events being bounded.
[ono2015chance] propose dynamic programming-based chance-constrained
optimization that handles joint chance constraints caused by uncertain terrain
conditions for space exploration.

There has been previous work employing _linear temporal logic_ to consider the
notion of safety encoded as user-defined specifications. [barbosa2019guiding]
adopt signal temporal logic, extended from linear temporal logic to handle
real-time and real-valued constraints, to explicitly model maximum and minimum
allowable distances from obstacles.

###  4.2 Which Tasks to be Assigned

In large-scale environmental monitoring, the size of the environment is
significantly larger than that of the FOV of a sensor mounted on a robot,
making the robot spend an enormous amount of time gathering useful
information. Therefore, multi-robot systems would expedite task completion by
distributing sensing burdens cooperatively. The deployment of multiple robots,
furthermore, yields beneficial features over single robot deployment, such as
resiliency against failures, reliability for complex tasks, and simplicity in
design [khamis2015multi].

In the multi-robot literature, discrete targets and disjoint regions are often
called tasks. The critical challenge to multi-robot coordination from the
planning perspective is the problem of assigning a set of given tasks to
robots. Tasks must be allocated among robots to minimize time or energy spent
by all robots and achieve desirable global task performance expressed in
utility.

As task allocation has a vast amount of literature, we redirect interested
readers to the survey papers [gerkey2004formal, korsah2013comprehensive,
khamis2015multi]. Here, we highlight some of the recent work related to
environmental monitoring. In particular, we present two constraints mainly
studied in task allocation; each robot can be assigned to at most a single
task at a time (_single task assignment_) or multiple tasks (_multi-task
assignment_).

####  4.2.1 Single task assignment

In the case of single-task robot and single-robot task, both robot and task
are assigned to at most a single counterpart. This can be formally defined,
shown in [gerkey2004formal], as:

$\leavevmode\nobreak\ \begin{aligned}
\max\quad&\sum_{i=1}^{M}\sum_{j=1}^{N}\alpha_{ij}w_{j}U_{ij},\\\
\textrm{s.t.}\quad&\sum_{i=1}^{M}\alpha_{ij}=1,\ \forall\ j\in\\{1,..,N\\},\\\
&\sum_{j=1}^{N}\alpha_{ij}=1,\ \forall\ i\in\\{1,..,M\\},\\\ \end{aligned}$
(4.1)

where $i$ is the robot index, $j$ is the task index, $U_{ij}$ is the utility
of choosing task $j$ for robot $i$, $w_{j}$ is the weight of the $j$-th task,
and $\alpha$ is a non-nagetive integer. The goal is to determine $\alpha_{ij}$
for all robot and task pairs that maximizes the weighted sum of utility in
Equation (4.1). Several challenges studied for single-task robot and single-
robot task include interrelated tasks and resource contention among robots
[nam2015assignment].

There are cases where multiple robots can allocate the same task. For example,
each robot can execute at most a single task while some tasks can be shared
(single-task robot [gerkey2004formal]), and some tasks can be achieved by
multiple robots (multi-robot task [gerkey2004formal]). A coalition-formation
game is adopted by [jang2018anonymous] to form subteams of robots where the
selfish robots seek to increase their reward by forming a coalition. They
provide a decentralized algorithm requiring a strongly connected communication
graph and prove a suboptimal Nash stable partition under some conditions.

The online assignment problem is solving task allocation repeatedly to ensure
dynamic task allocations on the fly in many robots and tasks. [liu2012large]
study online assignment problem in terms of single-task assignment that
dynamically mixes centralized and decentralized approaches to generate
efficient and robust allocation.

####  4.2.2 Multi-task assignment

Often, each robot from a robot team must be able to deal with more than a
single task, particularly when the number of tasks (_e.g._ , monitoring sites
or targets of interest) is larger than that of robots. Robots can determine
which tasks they are assigned either a priori if tasks are stationary or
online if tasks are dynamic in space and time.

Multi-robot multi-target assignment is fundamentally more challenging than
conventional multi-task assignment among immobile agents because planning
robot trajectories is also involved. It is undesirable in terms of time and
energy that one robot travels a long distance to reach a task where another
robot is nearby. Thus, distributing a fair amount of traveling distance and a
fair number of tasks is critical. Communication challenges, such as limited
communication range, limited bandwidth, and communication delay, can bring
additional complexity.

Combinatorial optimization techniques, such as mixed-integer linear
programming and mixed-integer quadratic programming, are often employed to
solve the assignment problem between a set of robots and a set of tasks.
However, most multi-task assignment problems are NP-hard
[vazirani2013approximation], increasing the computational complexity
dramatically as the number of robots and tasks increases. Algorithmic efforts
have been mostly focused on alleviating the computational complexity by
developing approximation algorithms [vazirani2013approximation] or distributed
algorithms [lynch1996distributed].

To avoid a single central processor that treats all information and
computations, _auction algorithm_ [bertsekas1988auction] has been popular as
distributed algorithms, which works for both single and multi-task assignment.
The idea of the auction algorithm originates from market-based coordination,
where robots are considered self-interested participants and bid for tasks.
The value of a task is computed by the difference between a reward and a price
(_e.g._ , distance robot and task location) of achieving the task. An
auctioneer determines an appropriate selection of bids among robots based on
computed task values. The auction algorithm achieves globally efficient
solutions from selfish robots maximizing their rewards and minimizing others’
rewards [zlot2006auction]. Variants of the auction algorithm have been
proposed to include additional features and show theoretical guarantees,
including exploiting local information [zavlanos2008distributed], a conflict-
free assignment guarantee [choi2009consensus], and optimal assignments
[liu2013optimal].

In multi-task assignment literature, various algorithmic challenges motivated
by practical applications have been proposed. Examples, but not limited to,
include tasks exhibiting different levels of priority [notomista2019optimal],
balancing the workload among robots to reduce idle robots
[schwarzrock2018solving], scheduled tasks with time window [nunes2015multi,
suslova2020multi], and disjoint groups of tasks [luo2014provably].

###  4.3 What Samples to Collect

There are often requirements for physically collecting ex-situ samples that
are spread in the environment, especially when samples are needed to be
analyzed in the lab. Due to the limited load capacity (_i.e._ , budget) of a
robot, only a limited number of samples can be gathered by a robot in a single
deployment. Suppose all the sample information, such as the location and the
quality, is revealed to the robot a priori. In that case, the optimal strategy
of collecting samples can be constructed, maximizing a reward or utility given
a limited budget. However, in reality, partial or no information is given in
most cases, which makes finding an optimal solution offline often infeasible.
Although a sample currently available to be collected exhibits a good quality
of interest, the robot may still want to give up on that sample and move on to
the next sample, hoping that samples at a later time have better quality.
Given these challenges, the robot must be able to determine what samples to
collect among the stream of observed samples in exploring unknown and
stochastic environments.

The _hiring_ (or) _secretary problem_ [freeman1983secretary,
ferguson1989solved] involving the optimal stopping theory
[shiryaev2007optimal] addresses a relevant problem that can be related to the
question of what samples to collect. The problem formulation is as follows.
Given $n$ number of secretary applicants of unknown quality, the interviewer
interviews one applicant at a time, evaluates the quality of the applicant and
determines whether to hire the applicant. If the interviewer decides to hire
the current applicant, the process ends, or otherwise, the next applicant
comes in. The process repeats until one applicant is hired. The rejected
applicant cannot be considered anymore, so the interviewer makes irrevocable
decisions. [das2015data] present a data-driven sampling strategy that
minimizes cumulative regret for batches of plankton samples using a
combination of Bayesian optimization in the bandit setting, with online best-
choice with hiring algorithm. [flaspohler2018near] propose irrevocable sample
selection for a periodic data stream. [manjanna2018heterogeneous] consider two
robotic boats for exploring the lake and sampling water samples using the
Gaussian process-based modeling. They propose a variant of the secretary
problem for finding the sampling locations, but their version allows the robot
to visit previous sampling locations.

###  4.4 When to Collect Samples

When environmental monitoring involves multiple complex objectives, such as
avoiding obstacles, reducing state uncertainty, and periodically collecting
samples, it becomes challenging to determine the timing of the action of
collecting samples from an environment. Nonetheless, the question of when to
collect samples is less explored than other decision-making problems in the
literature.

Since deciding when to collect samples is related to temporal reasoning,
previous work has studied it in formal verification, specifically _linear
temporal logic_ (LTL). In LTL, a user defines task specifications, such as
eventually or infinitely often holding an event (_i.e._ , LTL formulas) along
with many others, and synthesizes a control policy that satisfies those
specifications. As such, deciding when to collect samples can be encoded as
one of the specifications along with other task specifications to determine
the sample collection timing implicitly.

[lu2018mobile] use the LTL to enforce a team of robots to infinitely often
visit a partitioned set of environments. [nilsson2018toward] and
[leahy2019control] employ the LTL for aerial-ground robots to collect samples
from uncertain environments collaboratively. For interested readers, refer to
the survey papers on formal specifications in robotics [kress2018synthesis,
luckcuck2019formal].

The intermittent deployment problem proposed by [liu2019submodular] address
the challenge of dependency between current and future monitoring to determine
when to deploy a team of robots for monitoring (_e.g._ , collecting samples).
This challenge arises from a scenario where current monitoring influences
underlying environmental dynamics.

###  4.5 How to Learn Environment

Generally, environment representation is not given a priori; thus, we must
learn task-specific representation by gathering relevant data in the field. In
Chapter 2, we have introduced numerous representations and their properties.
This section focuses on existing environmental monitoring methods, leveraging
recent machine learning advances. It is particularly fascinating to review
machine learning techniques due to the recent popularity of deep learning-
based approaches. An extensive summary of machine learning applied for data-
driven geoscience can be seen in [bergen2019machine]. We leave out the
Gaussian process-based methods in this section (_i.e._ , learning
hyperparameters in a data-driven way) as we present numerous studies in
Chapter 2 and Section 4.1.

####  4.5.1 (Un)supervised learning

Following the great success of replacing traditional machine learning
approaches [nuske2011yield] with deep neural networks in the computer vision
community, most efforts have been spent appropriately adopting deep learning-
based vision capabilities in environmental monitoring tasks. This _supervised
learning_ framework learns to predict attributes of an object of interest
(_e.g._ , location, size, and color) from an image input. Most work does so in
a _supervised-learning_ manner, requiring human supervision to label the data.

Numerous studies in agricultural robotics [r2018research,
vougioukas2019agricultural, sparrow2021robots, oliveira2021advances,
basiri2022survey] and forestry [oliveira2021forest] have applied convolutional
neural networks to detect objects of interest, such as weed classification
[sa2017weednet], tree diameter estimation [chen2020sloam], and corn stand
counting [kayacan2018embedded]. [hani2020comparative] conduct a comparison
study between the deep learning method and classical method (_i.e._ , Gaussian
mixture model-based approach) on apple detection and counting algorithms in
orchards. They show that the deep learning method outperforms the classical
technique on counting while the classical method still performs well on
detection.

Neural networks have also been applied to improve planning performance.
[saroya2020online] use convolutional neural networks to learn topological
features in mining tunnels and caves to inform frontiers to robots for
improved subterranean exploration. [li2021attention] propose the convolutional
neural network-recurrent neural network to learn a multivariate spatiotemporal
environment. They also incorporate the attention mechanism to detect
parameterwise dependencies and spatial correlations, driving active sensing.

_Weakly supervised learning_ refers to supervised learning with noisy labeled
data. [koreitem2020one] learn a visual similarity operator via a weakly
supervised method to guide visual navigation.

The _self-organizing map_ [faigl2016self, best2018online,
jayaratne2019unsupervised, best2020decentralised] has been developed to learn
a lower-dimensional representation of an input space without its violating
topological properties. This _unsupervised learning_ procedure is used for
active perception and data collection.

####  4.5.2 Reinforcement learning

Due to the burst of advances in _reinforcement learning_ (RL), numerous recent
studies have employed RL to learn a policy for robots via online interaction
with environments. RL algorithms developed recently show promising
performances in sample efficiency and generalization, known challenges in RL,
motivating researchers in environmental monitoring to adopt for their
applications.

Several previous work has extended existing RL algorithms to tackle
environmental monitoring-specific challenges. [martin2017extending] address
heteroscedastic marine environments where noise varies over states and
actions, as opposed to environments having homogeneous noise in general RL
problems, and propose a model-based algorithm. In their subsequent work
[martin2018sparse], they propose a model-free algorithm for navigation in
marine environments by reducing temporal difference updates to Gaussian
process regression for data efficiency. [chung2015learning] develop resource-
constrained exploration that is adaptive and directed. They use the Gaussian
process regression to model the value function and proposed a Gaussian
process-based state–action–reward–state–action (SARSA) algorithm. To generate
non-myopic action sequences, the objective function is involved with resource
weights and a future information gain. [chen2019deep] design deep RL tree to
find near-optimal sampling locations by computing maximum information gain
from the spatiotemporal field. [notomista2022multi] study RL to learn a
coordinated-control policy for multiple robots based on a a control-theoretic
measure of the information (_i.e._ , a norm of the constructability Gramian).

The RL framework has been adopted for various environmental monitoring
applications. We present several studies demonstrating how environmental
monitoring tasks can benefit from RL. [zhi2019learning] construct a 2D map by
obtaining semantic segmentation obtained by visual images, which then becomes
an input to the deep RL framework to determine the robot’s action.
[niroui2019deep] introduce deep RL to the conventional frontier-based
exploration to handle high-dimensional state spaces. Their deep RL takes the
map, robot, and frontier locations as input and yields a goal location as
output. They adopt asynchronous advantage actor-critic as a learning tool
instead of deep q-network due to its slow convergence rate.
[doroodgar2014learning] propose hierarchical RL that can learn and make
decisions with human supervision given multiple tasks. In their subsequent
work [hong2018investigating], they extend to the control of multi-robot teams
so that the operator reduces interaction effort while improving task
performance. [chen2019adaptive] employ RL to a known environment coverage task
to reduce application-specific customization. [ruckin2022adaptive] propose a
Monte Carlo tree search with a convolutional neural network for informative
path planning in unknown environments.

In urban search and rescue, (hierarchical) RL is adopted to learn to explore
unknown environments while allocating rescue tasks to multiple robots
[doroodgar2014learning, hong2018investigating, niroui2019deep].

####  4.5.3 Other learning methods

_Graph neural network_ (GNN [wu2020comprehensive]) is designed to perform
inference from graph-structured data, leveraging the notion of _equivariance_
for efficient learning. GNN is particularly useful for multi-robot systems as
a graph can naturally represent the communication network among robots.
[tolstaya2020multi] exploit GNN to learn the spatial equivariance of the
multi-robot coverage task so that it can generalize to larger maps and larger
teams. [gosrich2022coverage] focus on designing a GNN-based decentralized
control policy addressing limited sensing range within a team of robots.

[tompkins2020online] consider _domain adaptation_ of occupancy map models
leveraging the observation that real-world structures contain similar
geometric features. Their optimal transport-driven method learns to transfer
parameters from domain to domain, static to dynamic environments, and
simulation to real-world.

###  4.6 Who to Communicate

Often, the field of interest is extensive and cannot be monitored by a single
robot. Thus, we deploy multiple robots to aggregate local information obtained
by a single robot to estimate global information. When deploying multiple
robots for environmental monitoring, the robots must decide who to communicate
due to the limited communication capability. As communication challenge in
multi-robot systems has long been researched in robotics (see the survey
papers [yan2013survey, rizk2019cooperative, gielis2022critical]), we introduce
environmental monitoring-related studies in this section.

Communication is one of the major bottlenecks, especially for field robots to
deploy, as a stable WiFi connection is hard to achieve in practice due to the
jerky motion of robots, mechanical issues, and WiFi interference. Thus,
existing methods assuming perfect communication (_i.e._ , centralized
communication or all-to-all communication) may not be readily applicable to
real-world deployment. We need a mechanism to enhance robot coordination, such
as a communication map [li2019multi].

Distributed _consensus_ is one of the frequently-used coordinating methods
whose objective is to reach an agreed value among multiple robots.
Measurements taken by neighboring robots are averaged and shared through
communication. Analysis of convergence is critical in consensus-based
algorithms. [lynch2008decentralized] allow for heterogeneity and unknown and
varying communication network among robots. [aragues2012distributed] propose a
dynamic consensus method for map merging applications. [tamjidi2019efficient]
improve a consensus filter for a dynamically changing network of robots by
separating correlated information from uncorrelated one to achieve robustness
to network failure. [jang2020multi] propose a consensus-based distributed
Gaussian process algorithm.

_Topology control_ allows robots to actively determine which communication
link to enable from a set of available links under limited communication and
sensing constraints. [williams2013constrained] propose a distributed
interaction control scheme considering a set of topological constraints. Their
scheme allows robots to actively retain and reject communication links from
their neighbors, which is discrete switching, and to control based on
attractive and repulsive potentials fields. Aggregation and dispersion with
node degree constraints are verified with stability analysis.
[mukherjee2020optimal] study optimal topology selection when asymmetric
interactions among robots exist.

Multi-robot coordination requiring connectivity always is undesirable as this
constraint may deteriorate the task performance of multi-robot systems.
Breaking the connectivity for some time may yield more flexible planning,
called _periodic connectivity_ in the literature. [hollinger2012multirobot]
develop an online algorithm scaling linearly with the number of robots and
allowing for periodic connectivity constraints. They also show
inapproximability results for connectivity-constrained planning.
[wu2012robust] propose a switching strategy between individual and cooperative
exploration to find a local minimum of an unknown field. Robots switch to
cooperative exploration when converging to a local minimum at a satisfying
rate is not detected and to individual exploration when the signal-to-noise
ratio is improved. [banfi2018multirobot] study multi-robot reconnection
planning on graphs. Their algorithm consists of two phases: optimizing the
environmental monitoring objective and reconnection planning to regain global
multi-hop connectivity.

While periodic connectivity enforces fixed-interval connectivity,
_intermittent interaction_ relaxes this fixed-interval constraint and asks an
algorithm to determine when to connect. [kantaros2019temporal] investigate a
scenario where multiple robots conduct an information-gathering task without
requiring the connectivity condition at all times. Their approach is based on
linear temporal logic (LTL). They propose a global LTL that ensures
intermittent connectivity among groups of robots and a local LTL that achieves
a local task of a robot, such as the monitoring task. Their algorithm is
distributed, online, and asynchronous. [heintzman2020multi] address an
interaction planning problem, avoiding obstacles and respecting the
constraints on random position samples. Their method is greedy and yields a
theoretical guarantee using submodular objective function and matroid
constraint.

##  Chapter 5 Conclusions and the Future Work

In this article, we survey algorithms for efficient sampling for environmental
processes. First we discuss robust representations of the environment,
followed by a listing of various tasks we are interested in carrying out on
these environments, and finally, algorithms to execute these tasks.

Environmental monitoring involves the development and implementation of
comprehensive autonomous systems, incorporating key components such as
perception, state estimation, planning, and control. In addition to improving
the performance of algorithms within the taxonomy to create reliable and
successful systems for deployment in the real world, there are several
promising future directions that have yet to receive sufficient research
attention. We conclude the survey by introducing these future directions.

Following the trends in the vision and language communities, several benchmark
simulations have recently been developed in robotics. These simulations serve
the purpose of facilitating performance comparison among various methods and
data collection for learning or pretraining. A crucial aspect of simulations
is to minimize the sim-to-real gap, ensuring that running a robot in
simulation closely resembles its behavior in the real world. However, there is
limited research that applies the same level of effort to field robotics,
specifically in the domain of environmental monitoring. Conducting robot
experiments in real-world environments is significantly more challenging and
resource-intensive, which justifies the need for building realistic and
reliable simulations. Additionally, as algorithmic efforts in environmental
monitoring are diverse and not easily comparable to other approaches, the
development of such simulations can help converge towards promising approaches
in the community and boost collaborative efforts.

Environmental monitoring presents inherently complex challenges, even when
considering a single type of robot and a single type of sensor. It is evident
that a heterogeneous team of robots or the utilization of heterogeneous sensor
modalities within a single robot holds great potential for enhancing
monitoring performance and addressing challenges that homogeneous teams or
sensors may struggle with. For instance, the collaboration between aerial
robots and ground robots can leverage the agility of aerial robots and the
close perception and physical interaction capabilities of ground robots,
resulting in synergistic benefits. Agriculture robots equipped with a
combination of camera sensors and heat sensors have the potential to
outperform robots equipped with either sensor alone. However, to fully harness
the advantages of heterogeneity in environmental monitoring, there is a
pressing need for a principled approach to merging different environment
representations and addressing algorithmic considerations, which currently
remains an open problem.

In environmental monitoring research, the focus has primarily been on robots
serving as passive observers or collectors of samples, with limited
consideration given to their active interaction with the environment. However,
in the real world, there are numerous scenarios where manipulability would
offer significant benefits. For instance, in hazardous environmental
monitoring, the ability to push and manipulate hazardous materials would
optimize the collection of a larger amount in a single deployment. Moreover,
manipulability equates to increased exploration capabilities for robots.
Leveraging techniques developed in manipulation planning and control can not
only address new challenges in environmental monitoring but also tackle more
complex monitoring tasks. By embracing the potential of robot manipulability,
the field of environmental monitoring can advance and effectively tackle a
wider range of monitoring objectives.

Environmental monitoring typically occurs in unstructured, dynamic, and
uncertain physical environments. One of its primary objectives is to gain a
deeper understanding of scientific phenomena, which can significantly enhance
the achievement of monitoring goals compared to situations where the
environmental dynamics are poorly understood. Surface vehicles and underwater
robots, for instance, can greatly benefit from understanding flow currents to
accomplish their objectives more effectively. Similarly, monitoring natural
disasters such as fires would be facilitated if the underlying physical laws
governing fire behavior can be revealed and utilized. While some efforts have
been made in this direction, there are numerous valuable techniques and
methods from scientific fields that can be leveraged to develop physics-
informed perception, planning, and control approaches. By harnessing these
approaches, environmental monitoring tasks can be tackled with greater
efficacy and efficiency.

###### Acknowledgements.