\chapter{Multi-Mission Monitoring with Gaussian Process Models}
\label{ch:LTM1}

\minitoc


\section{Introduction}
\label{sec:LTM1_intro}


As autonomous robots become more capable and reliable, we are seeing increasing potential for \emph{long-term} monitoring and information gathering missions in unstructured environments.
% %
Robots deployed in such missions must be able to plan effectively in the face of unknown and ever-changing environment dynamics, often with limited and noisy observational data.
%
In many such applications, however, uninterrupted autonomous operation cannot yet be sustained indefinitely due to lack of autonomous docking or recharging capabilities.
%
The problem of autonomous docking has been studied for aerial~\cite{grlj2022decade}, ground~\cite{liu2022laser}, and underwater robots~\cite{yazdani2020survey}, but remains a significant challenge.
%
Further, in many applications in unstructured environments, the required infrastructure  may not be readily available, or may be prohibitively expensive.
%
As such, many robots deployed on long-term missions still require periodic, scheduled returns to a base station for recharging, data offloading, or maintenance.


In this chapter, we consider a mobile robot deployed over a \emph{sequence} of discrete, short missions over a period of weeks or months. %, with the ability to navigate its environment and take observations during each mission.
%
For example, the robot might be deployed during daylight hours, returning to a base station each night to recharge.
%
Our work takes inspiration from ecological domains and applications, from mapping and monitoring of coral reefs~\cite{flaspohler2019information,mccammon2022adaptive}, to crop monitoring~\cite{dong20174d} and wildfire prevention~\cite{couceiro2019semfire}. % Other crop monitoring citation \cite{fountas2020agricultural}
%
In these domains, environments typically exhibit daily cyclic patterns (due to the influence of the weather, for example) combined with slower (e.g. tidal or seasonal) variation.
%
Our mission objective is to maximise the cumulative value of observations taken by the robot of some environment feature, about which it has limited prior knowledge.
%
In the ecological setting, features of interest might be plant growth or biodiversity~\cite{jackson2022short}, which can be measured by a robot using an on-board sensor.

We formalise the problem of repeated monitoring missions in a partially observable, spatiotemporally-varying environment as a PKSMDP, and propose an online belief-based planning approach to solve it.
%%
At the core of our approach is the robot's model of the unknown environment feature, which persists across missions, improving over time as the robot makes more observations.
%
Here, we address \challengeref{challenge:modelling}, using a GP~\cite{williams2006gaussian} that captures both spatial and temporal variation.
%
GPs have been used to model continuous environment features in a variety of planning problems~\cite{flaspohler2019information, duckworth2021time, budd2020markov, budd2023bayesian, morere2017sequential, marchant2014sequential}, as they provide a flexible and principled predictive framework for settings with sparse observational data.
%
% Thus, they are well-suited to tackle \challengeref{challenge:modelling} in the long-term setting. 
%
We assume that our feature of interest varies smoothly through space and time, and focus specifically on features that exhibit periodic behaviour.
%
This reflects our interest in ecological and other outdoor settings which naturally have a daily periodicity, and informs the design of the GP kernel function.

% We model the robot's physical environment as a topological map, a graphical abstraction of the space with vertices representing locations that the robot can visit and edges representing traversable links between them.
%
% We combine this with the GP model, which is used to maintain a belief over the state of the unknown environment feature given a history of observations.
% 
The long-term setting gives rise to significant challenges in scalability, where it quickly becomes infeasible to plan over a full multi-mission horizon even in relatively simple environments.
%
We therefore decompose the planning problem into individual missions, in which the robot plans its next action online using MCTS, forward-simulating the outcomes of different actions up to the end of the current mission using the GP model.
%
Planning only within individual missions risks inducing myopic behaviour, so we explicitly reward exploratory actions that can benefit \emph{future} missions.
%
To do so, we plan in a belief-aware manner, balancing exploitation of current knowledge about the environment with exploration guided by GP uncertainty.
%
This requires performing GP belief updates during MCTS trials, which is computationally costly.
%
Thus, we propose an algorithm that performs GP updates only within the search tree, and estimates the reward for the rollout phase  without requiring a belief update at every step.
%
Finally, as a step towards addressing \challengeref{challenge:priors} and minimising our reliance on prior knowledge about the environment process, we do not assume that well-tuned GP hyperparameters are given at the start of the mission.
%
Instead, the GP hyperparameters are optimised based on the current dataset between missions, allowing the robot to learn a better model of its environment as more observations are made.

The key contributions of this chapter are
%
% \begin{enumerate*}[label=(\roman*)] % roman, alph, arabic
%   \item the formulation of long-term, multi-mission robot monitoring of a spatiotemporal process as an \pomdpshort; 
%   \item the integration of a spatiotemporal GP kernel function into a belief-based MCTS planner for long-term monitoring missions; and
%   \item a new method for evaluating GP-based rewards during MCTS rollouts for improved computational performance. 
% \end{enumerate*}
(a) the formulation of long-term, multi-mission robot monitoring of a spatiotemporal process as an MDP with a partially unknown state;
% (b) the integration of a spatiotemporal GP kernel function into a belief-based MCTS planner for long-term monitoring missions; and
(b) a planning approach for this setting using a GP belief over the unknown environment, which balances exploratory information-gathering  with reward-seeking behaviour; and
(c) a new method for evaluating GP-based rewards during MCTS rollouts for improved computational performance.
%
The work in this chapter first appeared in~\cite{stephens2024planning}, presented at IROS 2024.

\section{Problem formulation}
\label{sec:LTM1_problem_formulation}

We consider a mobile robot  deployed in a physical environment represented as a topological map $\tm = \langle \tmnodes, \tmedges \rangle$.
%
Each vertex $\tmnode \in \tmnodes$ represents a location of interest in the environment, i.e. $\tmnode = (x, y) \in \mathbb{R}^2$, and edges $\tmedge \in \tmedges$ represent traversable paths between vertices.
%
The robot can navigate through the environment according to the edges in~$\tmedges$, and we assume here that the outcomes of navigation actions are deterministic.
%
There is an \emph{a priori} unknown spatiotemporal mapping $\processfunction:\mathbb{R}^3 \rightarrow \mathbb{R}$, where $\processfunction(x,y,t)$ is the value of an environment process of interest at location $(x,y)$ and time $t$.


The objective is to maximise the cumulative reward from observations taken of $\processfunction$ across a set of \emph{missions} that span many days.
%
%
We model this problem as a \pomdpfull{}~(\pomdpshort{}).

\begin{definition}[\pomdpfull{} (\pomdpshort{})]
    \label{def:M2-PKSMDP}
    A \pomdpfull{} is a pair $\langle \pksmdp, \multimissionspec \rangle$, where $\pksmdp = \langle \pksmdpstatespace, \pksmdpinitstate, \pksmdpactionspace, \pksmdptransition,\pksmdprewardspace\rangle$ is a PKSMDP (see Definition~\ref{def:PKSMDP}), and $\multimissionspec =\{(\pksmdphorizon^i_s,\pksmdphorizon^i_f)\}_{i=1}^m$ is a multi-mission specification listing the start and finish times for $m$ consecutive missions.

\end{definition}
%
At the start of each mission $i \in [1, \dots, m]$, the robot is deployed at the initial location $\tmnode_0 = (x_0, y_0)$ at time $\pksmdphorizon^i_s$, and can explore the environment until the mission end time $\pksmdphorizon^i_f$.
%
Note that, since the unknown process $\processfunction$ is time-dependent, we include time as a component of the (known) PKSMDP state, i.e.,  $\pksmdpstateknown = (x, y, t)$.
%
Moreover, in contrast with the standard finite horizon MDP formulation (Definition~\ref{def:MDP}), we do not use a fixed number of discrete timesteps for each mission's planning horizon.
%
Instead, the horizons are based on the (real-valued) durations of actions, which are modelled explicitly.
%
Within each mission, at step $j$, let  $t(\processstate_{k,j})$ denote the time at the current state $\processstate_{k,j}$, and $\pksmdpaction_j$ the next action to be executed by the robot under the current policy.
%
The robot transitions to the next state $\processstate_{k,j+1}$ according to the transition function $\pksmdptransition$, where the time component of the state is updated according to the duration of the action, so $t(\processstate_{k,j+1}) = t(\processstate_{k,j}) + \dur{\pksmdpaction_j}$.
%
It then receives a noisy observation $\processobs_{j+1}$ of the unknown process $\processfunction$ upon arrival at the new state $\processstate_{k,j+1}$.
%
These observations are subject to measurement noise $\processnoise \sim \mathcal{N}(0, \processvar_z^2)$, so $\processobs_j = \processfunction(\processstate_{k,j}) + \processnoise_j$.
%
We refer to the sequence of known states visited and observations received during mission $i$ as a \emph{trajectory} $\traj^i = \trajstate_{k,1}^i \trajobs_1^i \trajstate_{k,2}^i \trajobs_2^i \dots \trajstate_{k,n_i}^i \trajobs_{n_i}^i$, where $\trajstate_{k,1}^i$ is the known component of the initial state of the $i$-th mission, i.e. $\trajstate_{k,1}^i = \left(x_0,y_0,\pksmdphorizon^i_s\right)$.
%
The length of each trajectory $\traj^i$ is bounded by the corresponding mission end time, so $t(\trajstate_{k,n_i}^i) \leq \pksmdphorizon^i_f$.
%
% Note that, compared to the standard finite horizon MDP from Definition~\ref{def:MDP}, we do not use a fixed number of timesteps for each mission.
% %
% Instead, we define a \emph{continuous} planning horizon for each mission, and the number of actions taken in that mission is determined by the durations of the specific actions chosen.
%
The full multi-mission trajectory is denoted by $\trajmulti=\{\traj^1, \dots, \traj^m\}$.


For the remainder of this chapter, based on our motivating setting of ecological monitoring, we consider the missions to be \emph{daily}, such that the multi-mission problem described by $\langle\pksmdp, \multimissionspec \rangle$ spans $|\multimissionspec|=m$ consecutive days.
%
We also assume, here and throughout this thesis, that $\processfunction$ models a single environment feature only.
%
However, as discussed in Section~\ref{ssec:bkg_PKSMDP}, this would be straightforward to generalise to multiple unknown state features.


% We assume the presence of an unknown continuous function $f: \mathbb{R}^3 \rightarrow \mathbb{R}$ representing the value the phenomenon of interest at a state $(x, y, t)$.

% We model the problem as a \pomdpfull~(\pomdpshort), which we define as a tuple $\mathcal{M} = \langle \mathcal{S}, \mathcal{A}, \mathcal{T}, R, \mathcal{Z}, \mathcal{O}, H, b_0\rangle$, where:
% \begin{itemize}
%     \item $\mathcal{S}$ is the continuous state space of the robot and environment, $\{s, f\}$.
%     \item $\mathcal{A}$ is a discrete set of actions corresponding to navigating the topological graph.
%     \item $\mathcal{T}: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{S}$ is a deterministic transition function.
%     \item $R: \mathcal{S}\rightarrow \mathbb{R}$ is a reward function defining the reward for visiting a state $s$.
%     \item $\mathcal{Z} \in \mathbb{R}$ is the continuous observation space, i.e. the codomain of $\processfunction$.
%     \item $\mathcal{O}: \mathcal{S}\times \mathcal{Z}\rightarrow [0, 1]$ is the probability of observing $z\in Z$ from state $s\in \mathcal{S}$.
%     \item $H =\{(\pksmdphorizon^i_s,\pksmdphorizon^i_f)\}_{i=1}^m$ is a list of start and finish times for each mission, where $|H|=m$ is the number of missions.
%     \item $b_0$ is the initial belief state. 
% \end{itemize}

% We model the problem as a \pomdpfull~(\pomdpshort), which we define as a tuple $\mathcal{M} = \langle \mathcal{S}, \mathcal{A}, \mathcal{T}, R, \mathcal{Z}, \mathcal{O}, H, b_0\rangle$, where:
%


%
Our monitoring objective is to find a policy $\mdppolicy$ that maximises the expected cumulative reward across all missions:
%
\begin{equation}
    \label{eq:value_function}
    V_\mdppolicy(\pksmdpinitstate) = \mathbb{E}_\mdppolicy {\left[ \sum_{\traj^i\in \trajmulti} \sum_{\pksmdpstate^i_j\in \traj^i} \pksmdprewardspace\left(\pksmdpstate^i_j \right) \right]}.
\end{equation}
%
In this work, for simplicity, we take the reward function to be the value of $\processfunction$ itself, so $\pksmdprewardspace(\pksmdpstateknown, \processfunction(\pksmdpstateknown)) = \processfunction(\pksmdpstateknown)$.
%
However, in principle a variety of other information-based objectives might be of interest in ecological or other scientific contexts.
%
For example, \citet{flaspohler2019information} use a maximum seek-and-sample objective, where the robot seeks to sample from the maximum of an unknown distribution.
%
The work presented throughout this thesis permits any reward function to be used, provided it is sufficiently smooth and continuous to admit a GP representation.

Effective planning in this setting requires addressing three key challenges.
%
First, the robot must be able to accurately model the spatiotemporal process $\processfunction$ using sparse and noisy observational data (\challengeref{challenge:modelling}).
%
Second, it must plan across multiple missions, balancing exploratory behaviour that may benefit future missions with exploitation of knowledge from past ones.
%
Third, the planning approach must scale to large numbers of missions, in order to enable planning in truly long-term monitoring scenarios.





\section{MCTS planning with GP beliefs}
\label{sec:belief_space_mcts}

In this section, we outline an algorithm for belief-space planning with a GP observation model.
%
This algorithm acts as the foundation of our approach to the monitoring problem in this chapter, as well as those in Chapters~\ref{ch:LTM2} and~\ref{ch:LTM3}.
%
We consider planning for a PKSMDP in a setting where $\processfunction$ can be observed and modelled as a GP, i.e. the GP is used to maintain a \emph{belief} over the true value of $\processfunction$.
%
This can be viewed as belief-space planning for a Bayes-adaptive MDP~\cite{duff2002optimal}, with a GP encoding the belief over the unknown environment dynamics.
%
Planning in belief space with GPs is computationally expensive, so we use MCTS to generate promising trajectories and select high-reward actions online.
%
Algorithm~\ref{alg:belief_space_mcts} summarises our procedure for action selection, which we describe in detail below.


\begin{algorithm}[]
    \algsize
    \caption{{\sc Belief-Space MCTS}}
    \label{alg:belief_space_mcts}
    \textbf{Input}: PKSMDP $\pksmdp = \langle \pksmdpstatespace, \pksmdpinitstate, \pksmdpactionspace, \pksmdptransition, \pksmdprewardspace, \pksmdphorizon \rangle$, current GP model $\gp$ (dataset $\gpdataset$, hyperparameters $\gphypers$, kernel $\gpkernel(\gpstate, \gpstate')$).\\
    \textbf{Output}: Action $\pksmdpaction \in \pksmdpactionspace$ to take from the current state $\pksmdpinitstate$
    \begin{algorithmic}[1]
        %\PROCEDURE{Recursion}{$a$}

        % MCTS action selection 
        \Procedure{GetNextAction}{$\pksmdp$, $\gp$}
        \State $\mctsnodeb_\mathrm{root} \gets \textsc{InitialiseTree}(\mainmodelsymbol, \gp)$
        \For{$i \gets 1$ to $N_\mathrm{trials}$}
        \State $\mctsnodeb_\mathrm{leaf}, r_\mathrm{tree} \gets \textsc{SelectNode}(\pksmdp, \gp, \mctsnodeb_\mathrm{root})$
        \State $r_\mathrm{rollout} \gets \textsc{PerformRollout}(\mctsnodeb_\mathrm{leaf}, H)$ \label{line:rollout_phase}
        \State $r_\mathrm{total} \gets r_\mathrm{tree} + r_\mathrm{rollout}$
        \State $\textsc{Backpropagate}(\mctsnodeb_\mathrm{leaf}, r_\mathrm{total})$ \label{line:backprop_phase}

        \EndFor
        % \STATE $\vec{\theta} \gets \textsc{OptimiseHyperparameters}(G, \vec{\theta})$ \label{line:gp_opt}
        \State \Return $\textsc{BestChild}(\mctsnodeb_\mathrm{root})$ \label{line:select_return_action}
        \EndProcedure
        \item[]

        \Procedure{SelectNode}{$\pksmdp, \gp, \mctsnodeb_\mathrm{root}$}
        \State $\mctsnodeb \gets \mctsnodeb_\mathrm{root}$
        \State $r_\mathrm{tree} \gets 0$
        \While{$\mathrm{depth}(\mctsnodeb) < d_\mathrm{max}$}
        \State $\pksmdpavailableactions \gets \textsc{GetAvailableActions}(\pksmdp, \mctsnodeb)$
        \State $n_\mathrm{child}^{BA} \gets \textsc{SelectActionPUCT}(\mctsnodeb, \pksmdpavailableactions)$ \label{line:select_action_PUCT}
        \If{$\mctsnodeba_\mathrm{child} = \varnothing$}
        \State \Return $\mctsnodeb, r_\mathrm{tree}$
        \EndIf
        % Progressive widening belief step
        \State $\mctsnodeb_\mathrm{child}, r_\mathrm{child} \gets \textsc{GenerateBeliefChild}(\mctsnodeba _\mathrm{child})$ \label{line:generate_belief_child}
        \State $\mctsnodeb \gets \mctsnodeb_\mathrm{child}$
        \State $r_\mathrm{tree} \gets r_\mathrm{tree} + r_\mathrm{child}$
        \EndWhile
        \State \Return $\mctsnodeb, r_\mathrm{tree}$
        \EndProcedure
        \item[]

        \Procedure{PerformRollout}{$\mctsnodeb,\pksmdphorizon$}
        \State $s \gets s(\mctsnodeb)$
        \While{$t(s) \leq \pksmdphorizon$}
        % \State $\pksmdpavailableactions \gets \textsc{GetAvailableActions}(s, H)$
        % \State $\pksmdpavailableactions \gets \textsc{GetAvailableActions}(s, H)$
        \State $\pksmdpavailableactions \gets \emptyset$
        \For{$\pksmdpaction \gets \textsc{GetEnabledActions}(\pksmdp, \pksmdpstate)$}
        \State $\pksmdpstate' \gets \pksmdptransition(\pksmdpstate, \pksmdpaction)$
        \If{$t(\pksmdpstate') \leq \pksmdphorizon$}
        \State $\pksmdpavailableactions \gets \pksmdpavailableactions \cup \{\pksmdpaction\}$
        \EndIf
        \EndFor
        \State $\pksmdpaction \gets \textsc{RandomChoice}(\pksmdpavailableactions)$
        \EndWhile
        \State \Return $A$
        \EndProcedure


    \end{algorithmic}
\end{algorithm}


This algorithm is similar to the one presented by \citet{flaspohler2019information}, so we adopt their terminology, which refers to planning trees composed of two types of nodes: \emph{belief} nodes, which represent planning states, and \emph{belief-action} nodes, which represent action choices.
%
In the standard MCTS nomenclature introduced in Section~\ref{sec:MCTS}, belief nodes and belief-action nodes are decision nodes and chance nodes, respectively.
%
The root of the search tree is a belief node representing the current state of the mission, which we denote with a timestep index $j$ by $b_j = (s_{k,j}, g_j, s_{e,j} )$, where $s_{k,j} \in S_k$ is the known robot state, $g_j$ is a GP posterior over $\processfunction$ based on the history of observations \emph{prior} to timestep $j$, and $s_{e,j} \in S_e$ is an observation sampled from $g_j$ at known state $s_{k,j}$. % which we denote $\mathcal{D}_t$. 

Starting with just the root node, trials are performed, either for a fixed number of iterations or until some time budget is exhausted.
%
In the selection step, starting from the root node, an action $\pksmdpaction$ is selected (Line~\ref{line:select_action_PUCT}) according to the PUCT value:
%
\begin{equation}
    \label{eq:PUCT}
    \hat{V}^*(b_j, a) =
    \hat{V}(b_j, a) + C\sqrt{\frac{N(b_j)^{e_d}}{N(b_j, a)}},
\end{equation}
%
where $\hat{V}(b_j, a)$ is the average reward obtained by choosing action $a$ with belief $b_j$ in previous trials; $N(b_j)$ is the number of times that node $b_j$ has been simulated; $N(b_j, a)$ is the number of times that action $a$ has been selected from node $b_j$; $C$ is a constant that affects the exploration-exploitation balance; and $e_d$ is a depth-dependent parameter as per \citet{auger2013continuous}.

Since the observation space is the co-domain of $\processfunction$, which is  continuous, any observation sampled from the GP belief is guaranteed to be unique.
%
Thus, we use progressive widening to limit the size of the planning tree, parameterised by another depth-dependent parameter $\alpha_d$~\cite{auger2013continuous}.
%
If $\left\lfloor N(b_j, a)^{\alpha_d} \right\rfloor = \left\lfloor (N(b_j, a) - 1)^{\alpha_d} \right\rfloor$, then the successor state $b_{j+1}$ is randomly sampled from the existing children of node $(b_j, a)$; otherwise, a new state $s_{k, j+1}$ is sampled from  $T((s_{k,j}, s_{e,j}), a, .)$ and a new observation $s_{e, j+1}$ is sampled from the GP posterior $g_{j+1}$ at $s_{k, j+1}$.
%
These are used to add a new leaf node to the tree, $b_{j+1} = (s_{k,j+1}, g_{j+1}, s_{e,j+1})$, where the time at the leaf node is given by $t(b_{j+1}) = t(b_j) + \dur{a}$.
%

This process of alternating between action and belief-action nodes continues down the tree until a new (leaf) belief node is added (the expansion phase), as depicted in Figure~\ref{fig:mcts_explanation}. % , which we denote $b_{\ell}$. 
%
From this node, we enter the rollout phase (Line~\ref{line:rollout_phase}), in which we simulate a sequence of random actions up to the horizon $\mctshorizon$: that is, until we reach a node $b_j'$ where $t(b_j') + \min_\mctsaction \dur{\mctsaction} > \mctshorizon$.
% (i.e. belief-action nodes have the same depth as their parent belief nodes). 
%
This simulated trajectory yields a reward $r$, which is backpropagated (Line~\ref{line:backprop_phase}) to the tree root, updating the average reward and number of queries of each node visited in the selection step.
%
Our method for computing this trajectory reward $r$ is described in Section~\ref{sec:trajectory_rewards}.
%
Once trials are completed, the action corresponding to the most-visited belief-action child of the root node is selected (Line~\ref{line:select_return_action}) and executed.




\section{Algorithm}
\label{sec:LTM1_algorithm}

\subsection{Spatiotemporal modelling with GPs}
\label{ssec:spatiotemporal_gp_modelling}

The presence of temporal variation amplifies the challenge of building accurate predictive models using limited observational data.
%
Not only does it add to the dimensionality of the state space, but it also means---in the context of data gathered by a mobile robot---that no individual state can be observed multiple times.
%
The robot may return to the same location multiple times, but the value of the environment process at that location may have changed in the interim.
%
By accounting for the structure of the problem at hand in the design of our GP kernel function, we can reduce the amount of data required to accurately model the unknown process~\cite{goodman2011learning, ho2019value}.
% Goodman et al. refers to this as the \emph{blessing of abstraction}.

In this section, we describe the design of a spatiotemporal GP kernel that is intended to be used in ecological monitoring and similar applications.
%
The design encapsulates two key structural assumptions about the domains of interest: first, that the unknown process varies smoothly in both space and time, and second, that it consists of an underlying cyclic component.
%
While the latter assumption might seem rather specific, in fact many ecological processes exhibit periodic behaviour, whether due to daily cycles of temperature, humidity or sunlight, or the ebbs and flows of tides.
%
\correction{Processes involving more complex (periodic or aperiodic) components could be captured through alternative GP kernel designs}~\cite{williams2006gaussian}, \correction{provided the relevant domain knowledge is available, as our model is compatible with any GP kernel.
    %
    Thus, for our purposes, these structural assumptions are relatively general, and allow us to demonstrate the capability of our model within a relevant application context.}


In the following, let  $\statespatial=(x,y) \in \mathbb{R}^2$, $\statespatial'=(x',y') \in \mathbb{R}^2$, $\mdpstate=(\statespatial,\statetemporal) \in \mathbb{R}^3$ and $\mdpstate'=(\statespatial',\statetemporal') \in \mathbb{R}^3$.
%
Our kernel function can be expressed as a product of a spatial and temporal component:
%
\begin{equation}
    \label{eq:kernel_full}
    k(\mdpstate, \mdpstate') = k_{\statespatial}(\statespatial, \statespatial')k_\statetemporal(\statetemporal, \statetemporal').
\end{equation}
%
The spatial component is a radial basis function (RBF), which captures correlations between locations that are near one another:
%
\begin{equation}
    k_{\statespatial}(\statespatial, \statespatial') = \processvar_{\statespatial}^2 \exp \left(- \frac{\norm{\statespatial - \statespatial'}^2}{2\ell_{\statespatial}^2} \right),
    \label{eq:kernel_spatial}
\end{equation}
%
and the temporal component is a product of a periodic and RBF kernel:
%
\begin{equation}
    \label{eq:kernel_temporal}
    k_t(t, t') = \processvar_\statetemporal^2 \exp \left(- \frac{2\sin^2\left(\pi\left| \statetemporal - \statetemporal'\right|/p\right)}{\ell_p^2} \right)
    \exp \left( - \frac{(\statetemporal - \statetemporal')^2}{2\ell_q^2}\right).
\end{equation}
%
Here,  $\processvar_{\statespatial}$ and $\processvar_\statetemporal$ are the spatial and temporal variances respectively; $\ell_{\statespatial}$ is the spatial lengthscale; $p$ is the period of the temporal kernel; $\ell_p$ is the lengthscale of the periodic component; and $\ell_q$ is the lengthscale of the slowly-varying component.
%
On its own, a periodic kernel assumes \emph{purely} periodic behaviour; in combination with the RBF kernel, an element of periodicity is preserved, but points that are further apart in time are treated as less correlated, thereby allowing for slow variation between cycles with $\ell_q \gg p$.
%

Each of the hyperparameters mentioned above can either be assigned fixed values, or initialised with prior distributions and then learned during the mission.
%
In our experiments in Section~\ref{sec:LTM1_experiments}, for example, we assign a fixed value to the period of $p = \qty{24}{\hour}$, capturing our assumption that the environment will feature some diurnal rhythm.
%
The remaining hyperparameters are optimised between episodes, by maximising the log marginal likelihood for the model given the current history of observations.



\subsection{Evaluating trajectory rewards}
\label{sec:trajectory_rewards}

% The true state-dependent rewards in our POMDP (Equation~\ref{eq:reward}) depend on the unknown function $\processfunction$, so cannot be evaluated directly during rollouts --- instead, we estimate rewards using our GP model. 
%
% The multi-mission structure of our problem must also be considered: although we plan within a single-mission horizon, exploratory actions that seem unfavourable within this horizon may still contribute to increased reward in future missions. 
%
% We therefore use an upper confidence bound (UCB) heuristic~\cite{srinivas2012information} to represent rewards for belief state $b_\tau$.
%
% In effect, this adds an exploration bonus to states with greater uncertainty, encouraging exploratory actions that may benefit \emph{future} missions:
%
%
The state-dependent reward in our mission objective (Equation~\ref{eq:value_function}) depends on the unknown function $\processfunction$, and thus cannot be evaluated directly.
%
% so our MCTS algorithm estimates state-dependent rewards using the belief maintained by the GP. 
%
We therefore introduce an \emph{approximate reward function} similar to \citet{morere2017sequential}, which is based on the GP belief in lieu of the true function $\processfunction$, and encodes the desired trade-off between exploration and exploitation.
%
We use the GP belief at step $j$, denoted $g_j$, to compute an upper confidence bound (UCB)~\cite{srinivas2012information} reward for belief state $b_j=(s_{k,j}, g_j, s_{e,j} )$, given by
%
\begin{equation}
    \label{eq:ucb}
    \tilde{R}_\mathrm{UCB}(s_{k,j}, g_j) = \mu_j(s_{k,j}) + \kappa \sigma_j(s_{k,j}),
\end{equation}
%
where $\mu_j$ and $\sigma_j$ are respectively the mean and standard deviation of $g_j$ at state $s_{k,j}$, and $\kappa$ is a constant that affects the exploration-exploitation balance.
%
Note that the known state $s_{k, j}$ has both spatial and temporal components, so this reward is also spatiotemporal.
%
The UCB reward adds an exploration bonus to states with greater uncertainty, which is essential in our multi-mission setting since we are only able to plan over a single-mission horizon.
%
Exploratory actions that seem unfavourable within the current mission may still contribute to increased reward in future missions, and the UCB reward encourages taking such actions.
%
Over time, the uncertainty in the GP belief will decrease, so the UCB reward will converge to the true reward.


%
% Effective planning with MCTS relies on performing a sufficient number of rollouts to accurately estimate the value of each action available at the root node. 
% %
% Since our heuristic rewards are derived from an unknown GP belief model, simulating a sequence of observations accurately would require sampling from and updating a GP model after each action in the sequence. 
% %
% This is prohibitively computationally costly.
%
Thus, the reward accumulated over a simulated trajectory $\traj=\trajstate_{k,1} \trajobs_1 \trajstate_{k,2} \trajobs_2 \dots \trajstate_{k,n} \trajobs_{n}$ using the UCB reward is given by
%
\begin{equation}
    \label{eq:trajectory_true_reward}
    R^+(\traj) = \sum_{j=1}^n \tilde{R}_\mathrm{UCB}(s_{k,j}, g_j),
\end{equation}
%
where $g_j$ is the GP posterior given dataset $\trajobs_1 \trajobs_2 \dots \trajobs_j$.
%
\sloppy
However, evaluating each $\tilde{R}_\mathrm{UCB}(s_{k,j}, g_j)$ requires sampling an observation from the previous GP belief $g_{j-1}$, and updating a copy of that belief.
%
This is computationally costly, and reduces the capacity to perform sufficient MCTS trials to accurately estimate the value of each action at the root node.

To mitigate this, we estimate the reward accumulated during the rollout phase using the GP belief $g_\ell$ from the \emph{leaf} node $b_\ell$; i.e., we do not perform belief updates during this phase.
%
\correction{In doing so, we ignore the changes in the GP belief that would occur during each step of a rollout, with the expectation that the GP uncertainty this far into the future would be large enough that such updates would be of limited value anyway.}
%
%The accumulated reward starting from the root node is then the sum of the rewards from the trajectory through the MCTS tree to the leaf node, and the  rollout trajectory from there, using a UCB reward for each observation. 
%%
%If the  trial consists of an in-tree component $ b_{0}, \dots, b_{\ell}$ and a rollout component $b_{\ell+1}, \dots, b_{n}$, with $b_i=(s_{k,i}, g_i, s_{e,i} )$, then the estimated reward accumulated over the trial is:
%
%\begin{equation}
%    \tilde{R}^+(b_\tau)= \sum_{i = 0}^\ell \tilde{R}_\mathrm{UCB}(s_{k,i}, g_i) 
%    +  \sum_{i = \ell+1}^{n} \tilde{R}_\mathrm{UCB}(s_{k,i}, g_\ell).
%\end{equation}
%
Formally, for a trajectory $\traj=s_{k,1} z_1s_{k,2} z_2\dots s_{k,n} z_{n}$ with $1 \leq \ell \leq n$ being the index where the search moves to the rollout phase, we define the estimated cumulative reward as:
%
\begin{equation}
    \label{eq:rollout_reward}
    \tilde{R}^+(\traj)= \sum_{j = 0}^\ell \tilde{R}_\mathrm{UCB}(s_{k,j}, g_j)
    +  \sum_{j = \ell+1}^{n} \tilde{R}_\mathrm{UCB}(s_{k,j}, g_\ell).
\end{equation}
%
%
This approach removes the need to create and sample from many copies of the GP during the rollout phase, instead allowing the reward accumulated during this rollout phase to be estimated through a single GP query.
%
The in-tree component of each MCTS iteration is still quite computationally intensive.
%
However, since the rewards depend explicitly on belief uncertainty, this cannot be easily circumvented, and we show in Section~\ref{sec:LTM1_experiments} that we are still able to obtain good performance within reasonable computation times.

% The structure of our action selection process is designed to manage the high computational cost of explicit belief updates using GPs. 
% %
% Each belief node stores a copy of the GP model, which is queried when a new child node is generated --- a further GP query is required to calculate the UCB value of each belief node, although this is only ever done once per node. 
% %
% The heuristic values of all states in $T_{rollout}$ can then be evaluated

% \begin{enumerate}
%     \item Selection/expansion - move down the tree using PUCT policy, decide when to create a child based on progressive widening. Expansion step samples from GP at time action is completed, creates new GP at node. 
%     \item Random rollout to max depth, compute reward in batch
%     \item Backpropagate
% \end{enumerate}




\subsection{Planning algorithm}
\label{sec:planning_algorithm}

Our planning approach is summarised in Algorithm~\ref{alg:long_term_monitoring}.
%
Each mission $i$ begins with the robot at location $\vec{x}_0=(x_0,y_0)$, at the mission start time $t = \pksmdphorizon^i_s$.
%
At each step, actions are selected online~(Line~\ref{line:select_action}) using belief-based MCTS as described above, which plans over the \emph{current} mission horizon using a GP model based on the history of observations up to that point.
%
The selected action is then executed (Line~\ref{line:execute_action}), generating a new observation which is added to the dataset and used to update the GP model (Line~\ref{line:dataset_update}).
%
GP hyperparameters are optimised offline during the robot's down time between missions (Line~\ref{line:gp_opt}), improving the model over the course of the mission.

% \setlength\intextsep{0pt} % Reduce space above and below
% \begin{wrapfigure}{R}{0.5\textwidth}
% \vspace{-\parskip}
% \begin{minipage}{0.5\textwidth}
\begin{algorithm}
    \footnotesize
    \caption{{\sc Multi-Mission Monitoring}}
    \label{alg:long_term_monitoring}
    \Input \pomdpshort{} $\langle \pksmdp, \multimissionspec \rangle$ where $\pksmdp = \langle \pksmdpstatespace, \pksmdpinitstate, \pksmdpactionspace, \pksmdptransition,\pksmdprewardspace\rangle$ and $ \multimissionspec=\{(\pksmdphorizon^i_s,\pksmdphorizon^i_f)\}_{i=1}^m$, GP hyperparameter priors $\gppriors(\gphypers)$, kernel $\gpkernel(\pksmdpstate, \pksmdpstate')$\\
    \Output GP posterior over environment feature
    \begin{algorithmic}[1]
        \State $i \gets 1$ (current mission)
        \State $\gpdataset \gets \emptyset$
        \State $\gphypers \gets \gppriors(\gphypers)$
        \State Initialise GP model $\gp_{\gpdataset, \gphypers}$ with kernel $\gpkernel$,  hyperparameters $\gphypers$, dataset $\gpdataset$
        \While{$i \leq |\multimissionspec|$ }
        \State $\vec{x} \gets \vec{x}_0$
        \State $t \gets \pksmdphorizon^i_s$
        \State $\pksmdpstate \gets (\vec{x},t)$
        \While{$t \leq \pksmdphorizon^i_f$}
        \State $\pksmdpaction \gets \textsc{GetNextAction}(\pksmdp, \gp_{\gpdataset, \gphypers})$ \label{line:select_action}
        \State $\pksmdpstate', \gpobs' \gets \textsc{ExecuteAction}(\pksmdpaction)$ \label{line:execute_action}
        \State $\gpdataset \gets \gpdataset \cup \{(\pksmdpstate', \gpobs')\}$ \label{line:dataset_update}
        \State $\pksmdpstate \gets \text{new state } \pksmdpstate'$
        \EndWhile
        \State $\gphypers \gets \textsc{OptimiseHyperparameters}(\gp_{\gpdataset, \gphypers})$ \label{line:gp_opt}
        \State $i \gets i + 1$
        \EndWhile
    \end{algorithmic}
\end{algorithm}
% \end{minipage}
\vspace{-\parskip}
% \end{wrapfigure}


\section{Experiments}
\label{sec:LTM1_experiments}

\subsection{Experimental domains}

% We evaluate our approach experimentally on a series of synthetic domains, as well as one based on real-world data. 

% \paragraph{Synthetic domains} 
We demonstrate the performance of our algorithm on domains based on acoustic monitoring of coral reef activity using an autonomous underwater vehicle~(AUV).
%
Studies of these environments have found that sound levels at low frequencies correlate with density and diversity of coral reef fish species, which vary periodically over both daily and seasonal timescales~\citep{staaterman2017bioacoustic, mccammon2022adaptive}.
%
The mission goal is to focus observations of the reef on areas where bioactivity is highest, using acoustic sensing data to build a spatiotemporal GP model of bioactivity in the reef.


\paragraph{Synthetic domains}

We conduct experiments on 10 \textsc{Static} domains and 10 \textsc{Moving} domains, which capture different behaviours of the unknown environment process $\processfunction$.
%
Each of these domains is an $8 \times 8$ grid map with a 4-connected structure.
%
In the \textsc{Static} domains, $\processfunction$ consists of a set of randomly-placed Gaussian point sources at \emph{fixed} locations, whose amplitudes oscillate periodically over 24 hours; each source is spatially static, but still varies over time.
%
In these domains, $\processfunction$ is therefore purely periodic---it varies over the course of each day, but each day is identical to the one before.
%
In the \textsc{Moving} domains, $\processfunction$ consists of 1-2 \emph{moving} Gaussian point sources, which oscillate in amplitude in the same manner as the static sources but also drift slowly across the map, emulating gradual seasonal variation.
%
Figure~\ref{fig:moving_domain_example}depicts an example of the gradual variation of the \textsc{Moving} domains.
%
The design of these domains reflects patterns seen in many ecological phenomena, which often display similar combinations of daily cycles and longer-term variation.
%
In each case, the multi-mission duration is 20 days, and the robot is operational for 8 hours each day, performing 5 navigation actions per hour.

\begin{figure}
    \centering
    \begin{subfigure}[b]{0.24\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_7_0.pdf}
        \caption{Day 1.}
        \label{sfig:moving_env:1}
    \end{subfigure}
    \begin{subfigure}[b]{0.24\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_7_1.pdf}
        \caption{Day 2.}
        \label{sfig:moving_env:2}
    \end{subfigure}
    \begin{subfigure}[b]{0.24\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_7_2.pdf}
        \caption{Day 3.}
        \label{sfig:moving_env:3}
    \end{subfigure}
    \begin{subfigure}[b]{0.24\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_7_3.pdf}
        \caption{Day 4.}
        \label{sfig:moving_env:4}
    \end{subfigure}
    \caption[Synthetic domain snapshots]{Snapshots of one of the 10 \textsc{Moving} domains, shown at the same time across different days. The heatmap shows the value of the unknown process $\processfunction$ with contours indicating regions of similar value per-day, where yellow represents the maxima.}   \label{fig:moving_domain_example}
\end{figure}

\paragraph{Coral reef acoustic domain}

Our \textsc{Sesoko} domain simulates a realistic coral reef monitoring scenario, using acoustic spectrogram data captured at three sites in a coral reef near the island of Sesoko, Japan~\citep{lin2021exploring}.
%
Figure~\ref{fig:heatmap} shows a portion of the raw spectrogram data.
%
We compute the signal power at each site as a normalised root-mean-square over frequencies from \SIrange{400}{600}{\hertz}, a range within which acoustic signal strength is known to  correlate with coral cover and fish density~\cite{kaplan2015coral}.
%
We also apply some smoothing to remove high-frequency noise.
%
\correction{Each of the three signals is then used to modulate the amplitude of a Gaussian point source placed within a $10 \times 10$ grid environment, in order to generate a simulation of the acoustic signal across the full domain.}
%
Finally, we add a small drift velocity to one of the sources, to simulate possible long-term movement which could not be explicitly captured by the static acoustic sensor data.
%
\correction{Figure}~\ref{fig:coral_domain_vis} \correction{shows a series of snapshots of the domain over the course of a single day, in which subtle variations are visible in the intensity at each site.
    %
    Over the course of a full mission, an effective planner should be able to identify which location within the domain is most advantageous to visit at a given time.}
%
These multi-missions span 30 days, with the robot active for 20 hours per day, performing 3 actions per hour.


\begin{figure}
    \centering
    \begin{subfigure}[b]{0.3\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_coral_1.pdf}
        \caption{Hour 2.}
        \label{sfig:coral_env:1}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_coral_2.pdf}
        \caption{Hour 4.}
        \label{sfig:coral_env:2}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_coral_3.pdf}
        \caption{Hour 6.}
        \label{sfig:coral_env:3}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_coral_4.pdf}
        \caption{Hour 8.}
        \label{sfig:coral_env:4}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_coral_5.pdf}
        \caption{Hour 10.}
        \label{sfig:coral_env:5}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM1/figures/heatmap_env_coral_6.pdf}
        \caption{Hour 12.}
        \label{sfig:coral_env:6}
    \end{subfigure}
    \caption[Coral reef monitoring domain snapshots]{\correction{Snapshots of \textsc{Sesoko} reef monitoring domain, shown at intervals of two hours. The heatmap shows the value of the unknown process $\processfunction$ with contours indicating regions of similar value per-day, where yellow represents the maxima. Subtle differences are visible in the intensity at each site over the course of the day, which can be exploited by the planner.}}   \label{fig:coral_domain_vis}
\end{figure}


\subsection{Planning with a spatiotemporal GP kernel}

Our first set of experiments investigates whether the spatiotemporal GP kernel described in Section~\ref{ssec:spatiotemporal_gp_modelling} is able to produce improved planning behaviour in practice, compared with simpler baselines.
%
In all experiments, we assign a fixed value of $p = \qty{24}{\hour}$ to the period of the temporal kernel.
%
The remaining GP hyperparameters are initialised with relatively uninformative priors, and learned over the course of the missions.
%
We run 10 multi-missions in each of the 10 \textsc{Static} and \textsc{Moving} domains, testing three different GP kernel configurations:

\begin{enumerate}
    \item \textbf{Spatiotemporal mixed~(STM)}: the full spatiotemporal kernel $\gpkernel(\gpstate, \gpstate')$ from Equation~\ref{eq:kernel_full}, incorporating gradual spatial and temporal variation as well as a periodic temporal component.
    \item \textbf{Spatiotemporal periodic~(STP)}: the spatiotemporal kernel with the gradual temporal variation component removed, so the kernel is purely periodic in time.
    \item \textbf{Spatial static~(SS)}: a purely spatial RBF kernel, corresponding to the component from Equation~\ref{eq:kernel_spatial} only.
\end{enumerate}



The results from these experiments are shown in Figure~\ref{fig:gp_kernels_comparison_boxplot}.
%
We see that in the \textsc{Static} domains, the STP kernel achieves the best performance, since the unknown function in these domains is completely periodic and thus can be captured accurately by a kernel with a periodic temporal component.
%
The STM kernel performs well, although its performance is reduced slightly by the presence of the non-periodic temporal component.
%
This is as  expected, since the additional term in $\gpkernel_t$ (Equation ~\ref{eq:kernel_temporal}) reduces the weight of older observations in GP inference---in a purely periodic environment, this is a slight disadvantage, resulting in predictions being made using less data.
%
Over a longer mission, we would expect to see the performance of the STM kernel converge to that of the STP kernel.
%
The SS kernel performs worst, since it is unable to capture temporal variation; it can only identify the region of the map with the highest \emph{average} reward across all missions.

In the \textsc{Moving} domains, where the environment process evolves gradually between days, Figure~\ref{fig:gp_kernels_comparison_boxplot} shows that the performance of both the STP and SS kernels are weaker than the STM kernel.
%
In these domains, it is no longer possible to simply identify the best location to visit at particular times of day, since these locations change over time.
%
However, the STM kernel is able to learn and exploit an accurate model after a few days, and continues to perform well across all subsequent missions.


\begin{figure}
    \centering
    \includegraphics[width=0.8\linewidth]{chapters/chLTM1/figures/reward_vs_gp_kernels_boxplot.pdf}
    \caption[Planner performance with different GP kernels]{Average reward over 10 \textsc{Static} and 10 \textsc{Moving} domains, using planners with different GP kernels. Rewards are normalised per-domain to the highest reward obtained on that domain across all complete runs (10 runs per domain). \correction{The STM kernel performs well in both domain groups, particularly outperforming the other two configurations in the \textsc{Moving} domains.}}
    \label{fig:gp_kernels_comparison_boxplot}
\end{figure}


Finally, Figure~\ref{fig:real_data_results} shows the results of the \textsc{Sesoko} domain experiments.
%
Here, we see that the the planner with the STM kernel achieves the highest reward, with the SS and STP kernel performance degrading considerably in the latter half of the mission.
%
The STM kernel captures the underlying periodicity in the acoustic data, despite significant noise and artifacts in the raw data.
%
\correction{This demonstrates a strength of GP models in their ability to handle noisy data, effectively smoothing out this noise during inference.
    %
    Conversely, however, domains in which sharp transitions in the environment process occur would likely prove more challenging for the GP kernels explored here, and require more sophisticated kernel designs.}



Overall, these experiments  validate our GP kernel design, and more broadly demonstrates GPs as effective models for these monitoring tasks.
%
We see that the combination of periodic and RBF kernels allows the robot to build informative models of different environments relatively quickly.
%
These models then enable effective planning with respect to the long-term monitoring objective, despite the limited observational data and multiple layers of temporal variation present in the domains.

\begin{figure}
    \centering
    \begin{subfigure}[b]{1.0\linewidth}
        \centering
        \includegraphics[width=0.8\textwidth]{chapters/chLTM1/figures/coral_heatmap.pdf}
        % \caption{A portion of the frequency spectrogram data from Site C, located to the north of Sesoko island.}
        \caption{Frequency spectrogram data from Site C, north of Sesoko island.}
        \label{fig:heatmap}
    \end{subfigure}
    % \hspace{1.5cm}
    \figvspace
    \begin{subfigure}[b]{\linewidth}
        \centering
        \includegraphics[width=0.8\textwidth]{chapters/chLTM1/figures/reward_vs_gp_kernels_coral.pdf}
        \caption{Average cumulative reward across 10 30-day missions in the \textsc{Sesoko} environment; shaded regions indicate standard deviation. \correction{This result demonstrates that the STM kernel is able to model real-world acoustic data well enough to support effective planning.}}
        \label{fig:real_data_results}
    \end{subfigure}
    \caption[Coral reef acoustic monitoring results]{Input data and experimental results for the coral reef acoustic monitoring domain in Sesoko, Japan~\citep{lin2021exploring}. }   \label{fig:real_data}
\end{figure}

\subsection{Belief-based MCTS across multiple missions}
\label{ssec:LTM1_expts_belief_based_MCTS}
%
We now investigate how the core components of our \pomdpshort{} planner design contribute to performance.
%
The planner uses a belief-based MCTS algorithm which rewards exploration of uncertain states using a belief-dependent UCB reward.
%
This requires sampling from and updating a GP model each time a new node is added to the search tree.
%
During the rollout phase, however, trajectory rewards are evaluated in a single batch \emph{without} updating the GP, allowing for fast evaluation across many actions.
%
We therefore compare our approach to two baselines which remove these elements.

The first baseline uses a root sampling approach similar to that of \citet{budd2023bayesian}, where instead of updating the GP during MCTS, each observation is sampled directly from the belief at the root node, and no exploration bonus is used.
%
In their work, this approach is shown to converge to the reward-maximising policy and  significantly reduces the time taken for each trial.
%
However, it does not allow for the explicit rewarding of exploration provided by the belief-dependent rewards in our approximate reward function (Equation~\ref{eq:ucb}).
%
Thus, the policies generated by a root sampling approach will greedily maximise reward for each individual mission, without accounting for the benefits that exploration in one mission might have on performance in later missions.

The second baseline modifies the rollout phase to update the GP after each action, rather than using the GP from the leaf node.
%
In this configuration, each step in the rollout phase involves sampling from the GP model, updating the dataset, and then using the updated model to evaluate the reward term---similar to the process used in the in-tree part of MCTS.
%
This should mean that the rollouts more accurately estimate the value of the leaf node, at the expense of a significantly higher computational cost.
%
% %
% The reward function that we use during planning includes a UCB exploration bonus (Equation~\ref{eq:ucb}), which depends on the belief uncertainty at each step. 
% %
% Computing this belief during MCTS is computationally intensive, requiring GP belief updates and copying of data at each node. 
% %
% In order to validate that this extra computation is worthwhile, we compare the full planner with a baseline which uses root sampling similar to \citep{budd2023bayesian} --- that is, the GP is not updated during MCTS, and no exploration bonus is used, so the reward at each node is simply the mean of the GP at the root node. 
%

\begin{figure}
    \centering
    \begin{subfigure}[b]{\linewidth}
        \centering
        \includegraphics[width=0.7\textwidth]{chapters/chLTM1/figures/algs_comparison_boxplot.pdf}
        \caption{Average cumulative reward (normalised per-domain).}
        \label{fig:alg_comparison_reward}
    \end{subfigure}
    \figvspace
    \begin{subfigure}[b]{\linewidth}
        \centering
        \includegraphics[width=0.7\textwidth]{chapters/chLTM1/figures/algs_comparison_win_rate.pdf}
        \caption{Win rate, indicating the proportion of runs on which each algorithm obtained the highest reward.}
        \label{fig:alg_comparison_win_rate}
    \end{subfigure}
    \caption[Performance of different planner configurations]{Planner performance under fixed per-action planning time. Each configuration was run 5 times on each of the 10 \textsc{Moving} domains. \correction{We see that the} \pomdpshort{} \correction{consistently performs well relative to the other approaches tested, although root sampling performs reasonably well when planning time is highly constrained.}}
    \label{fig:algs_comparison}
\end{figure}

Figure~\ref{fig:alg_comparison_reward} compares the rewards obtained by the three algorithms in the \textsc{Moving} domains when given different amounts of planning time per action.
%
We see that performing GP belief updates during the rollout phase of MCTS does not improve overall performance, indicating that computation time is better spent simply performing \emph{more} trials.
%
The difference is most pronounced when computation time is limited, since in this case performing unnecessary belief updates results in the planner being unable to perform enough trials to select good actions.
%
However, given sufficient computation time, the performance of this method slowly improves, as it more accurately estimates the value of each leaf node.

Figure~\ref{fig:alg_comparison_win_rate} compares the win rates of each algorithm, indicating the proportion of runs in which each algorithm obtained a higher reward than the other two.
%
We see that when given \qty{10}{\second} of planning time per decision step, the computationally expensive belief-updating method is able to achieve the highest reward on some runs.
%
However, this is a significant amount of additional planning overhead for a relatively small domain, and as such it is likely that this approach would not be computationally feasible in larger domains.
%
Furthermore, our planner with a planning budget of \qty{1}{\second} still outperforms the planner performing GP updates during rollouts when given a budget of  \qty{10}{\second}.
% However, its performance plateaus, and even at \qty{1}{\second} per action the full planner performs equally or better on all 10 domains.
%
The root sampling baseline performs similarly to the \pomdpshort{} planner when planning time per action is limited to \qty{1}{\second}.
%
However, as we increase the planning time, we see that the  \pomdpshort{} planner outperforms the root sampling method, obtaining higher average cumulative reward and a win rate of at least 60\% in all cases.


From these results, we can conclude that the belief-based exploration reward has the intended effect of encouraging exploration, to the benefit of overall performance on long-term missions.
%
However, to achieve this improvement, updating of the GP belief should be done only during the in-tree component of MCTS.
%
During the rollout phase, it is preferable to use a fixed belief in order to achieve faster computation and allow for \emph{more trials} to be completed.

% with  despite the  computational cost of evaluating belief-based rewards during MCTS.   

% We find that the full planner performs equally or better than the root sampling baseline on all of these domains, achieving on average 6.6\% higher reward.
% %
% It is worth noting also that these are relatively small domains, and it is likely that these differences would be accentuated further when scaling up the problem domains.




% \paragraph{Experiment 3: Batch evaluation of trajectory rewards during MCTS rollouts}

% In Section~\ref{ssec:trajectory_rewards}, we presented a technique for efficiently estimating the heuristic reward accumulated during a random rollout, using the GP from the leaf node at which the trajectory began. 
% %
% We compare this technique against a baseline in which the GP model is updated after each action during the rollout, which in a sense provides a more accurate estimation of the UCB reward obtained during that trajectory.
% %
% However, we see in Figure~\ref{fig:trajectory_eval} that the estimated trajectory reward consistently leads to higher total reward within the same planning time.
% %
% The difference is more pronounced when less planning  time is available.
% %
% We conclude from this that the batch evaluation method produces sufficiently accurate rewards to converge to a good solution, and that the computation time saved by doing so is better spent performing \emph{more} rollouts.

% \begin{figure}[]
%     \centering
%     \includegraphics[width=0.8\linewidth]{fig/algs_comparison_boxplot.pdf}
%     \caption{Reward accumulated by different belief-based MCTS approaches, using different timeout durations for action selection. Rewards are normalised per-domain, with 10 runs on each of the 10 \textsc{Moving} domains.}
%     \label{fig:algs_comparison}
% \end{figure} 




\section{Discussion}
\label{sec:LTM1_discussion}

The multi-mission framework adopted in this chapter provides a planning solution motivated by the practical constraints of long-term robot missions.
%
Despite the advancements in robot technology to date, few robot systems are able to achieve long-term, uninterrupted autonomy in unstructured environments.
%
This is due to many factors, including the need for a high level of robustness in challenging environments, and the costs associated with the required infrastructure.
%
Thus, it is likely that in the near future, repeated deployments will remain a common way to enable long-term monitoring with mobile robots.

Our experiments demonstrate that GPs are a viable modelling tool for this type of long-term mission.
%
In our experiments, we see that with a well-chosen GP kernel, we can achieve consistent monitoring performance across a range of simulated domains.
%
\correction{Moreover, as previously discussed, clear avenues exist towards both scaling GPs to larger problems} (see Section~\ref{ssec:gp_scaling}), \correction{and to modelling more complex environment processes (see} Section~\ref{ssec:spatiotemporal_gp_modelling}).
%
In more complex time-varying environments, it is possible that GPs might struggle to provide useful predictions from the sparse data available from a robot's local measurements.
%
However, this could in turn be mitigated by incorporating additional sources of information as appropriate to the particular context, such as weather forecasts, or data from satellite imagery or static sensors.
%
Although in this work we assumed that data from previous missions was not available, if such data were available, it could be a valuable source of information which could be used to improve the GP model.

GPs also offer additional flexibility which is not explicitly leveraged in our work.
%
Our approach considers observations to be taken at waypoints only, but since GPs are continuous models, they can be queried at any point in their continuous input space.
%
Allowing the robot to take more frequent observations during navigation would be a straightforward way to improve the rate of data collection, and thus the quality of the GP model.
% 
However, since these data points would be highly correlated due to their proximity in the input space, it is also possible that the model would not benefit significantly from the additional data.


Trial-based planning algorithms in general face a trade-off when allocating computational resources, between optimising the accuracy of the value estimates versus performing more trials.
%
The baselines used in our experiments in Section~\ref{ssec:LTM1_expts_belief_based_MCTS} can be viewed as two opposite ends of this spectrum.
%
The root sampling planner reduces the cost of each trial by using a fixed GP belief, allowing for more trials within the same computation budget by sacrificing some accuracy in its value estimates.
%
On the other hand, performing belief updates during rollouts makes trials extremely computationally costly, but improves the accuracy with which they simulate the outcomes of future actions.
%
Our planner strikes a balance between these two extremes by performing belief updates only during the in-tree component of MCTS, and using a fixed belief during rollouts.
%
Our results show empirically that this approach produces better performance than either of the baselines, achieving higher rewards within the same computation budget.
%
However, the optimal balance between these extremes will vary depending on the specific domain and objective, as well as the computational resources available.
%
It is likely that in some domains, the root sampling approach would be sufficient to obtain reasonable performance, particularly since our results show that it performs relatively well with limited planning time.
%
\correction{More broadly, the planner would benefit from validation in larger-scale environments in order to assess its scalability in practice, in terms of both GP modelling and MCTS planning.}




\section{Summary}
\label{sec:LTM1_summary}

In this chapter, we introduced the \pomdpshort{}, a formalism for long-term, repeated robot monitoring missions in the presence of \emph{a priori} unknown environment processes.
%
We addressed \challengeref{challenge:modelling} using a GP kernel designed to capture spatiotemporally-varying processes, motivated by applications such as ecological monitoring.
%
We presented a continuous-observation MCTS planning algorithm, which uses a GP belief to plan online, balancing exploitation of observations from past missions with exploration to benefit future ones.
%
This algorithm used a novel technique for efficient estimation of the reward accumulated during rollouts, thereby mitigating the computational cost of GP belief updates and allowing more MCTS trials to be performed.
%
Additionally, we  incorporated online learning of GP hyperparameters to address \challengeref{challenge:priors}, reducing the need for manual tuning or domain-specific prior knowledge.
%
We demonstrated the performance of our planner empirically in a series of simulated experiments, including in a coral reef domain using real acoustic monitoring data.



% %
% In future work, we plan to extend the planning framework to consider longer multi-missions in more complex environments.
% %
% Interesting avenues could include learning causal models of multiple features, and incorporating influences from external factors such as temperature readings and weather forecasts.
