\chapter{Related Work}
\label{ch:related_work}

\minitoc

In this chapter, we discuss existing models and techniques relating to long-term monitoring in unknown environments.
%
We first summarise the relevant literature on Gaussian processes, the primary tool used to model continuous environments throughout this thesis.
%
We then consider techniques for decision making in unknown environments in general, before focusing specifically on long-horizon and resource-constrained problems.

\section{GP modelling of continuous environments}
\label{sec:relwork_GPs}

\subsection{Modelling natural phenomena}

In recent years, GPs have become a popular tool for modelling in a breadth of applications, as they provide a flexible framework for capturing complex statistical distributions based on local observations \citep{williams2006gaussian}.
%
GPs have been demonstrated as effective tools for modelling a wide variety of natural phenomena, including species distributions \citep{golding2016fast, ingram2020multi, wright2021spatial}, biodiversity \citep{talluto2018multifaceted}, dissolved oxygen levels in water \cite{bottarelli2019orienteering}, and ocean currents \citep{duckworth2021time}.
%


\citet{golding2016fast} explore the power of GPs in the context of environment modelling, showing that they outperform a variety of other statistical methods for species distribution modelling, in both predictive accuracy and computational complexity.
%
They incorporate ecological knowledge into their GP models through Bayesian priors over the mean function and the kernel hyperparameters, demonstrating that doing so can improve model accuracy in cases where limited data is available.
%
More recent work in \citet{ingram2020multi} considers joint modelling of multiple species using \emph{multi-output} GPs, exploiting correlations between species to improve models of rarer species for which less data is available. % Also provides ML-based techniques for improving scalability of multi-output GPs ? 
%
In this thesis, we use GPs to model acoustic bioactivity in coral reefs~(Chapter~\ref{ch:LTM1}), wildfire hotspots (Chapter~\ref{ch:LTM2}), and hazardous gamma radiation (Chapter~\ref{ch:safe_exp}).


\subsection{Spatiotemporal modelling}

In the context of robot monitoring of dynamic environments, we are particularly interested in models that are able to capture \emph{temporal} variations in features.
%
This unlocks the capability to  plan future actions based explicitly on estimates of \emph{future} states, rather than simply the current state.
%
\citet{duan2018joint} use a hierarchical GP model to represent medical data at multiple levels, introducing a shared GP that captures correlations between two GP models which would otherwise be independent.
%
By doing so, they are able to make more efficient use of clinical data, improving outcomes in predicting the progression of diseases.
%
The ability to forecast accurately from limited data is extremely valuable in robotic monitoring, since it enables robots to plan ahead to be at particular locations when the most valuable measurements are expected.

GPs have also been used extensively in the planning literature, which we discuss in Section~\ref{ssec:relwork_GP_beliefs}.

\subsection{Alternative techniques}

Several alternatives to GPs have also been used to model environment features based on noisy data.
%
A common modelling approach in the ecological field is the generalised additive model~(GAM)~\cite{wood2017generalized}.
%
Although GAMs are relatively flexible, they tend to struggle with higher-dimensional data, requiring prohibitively large sample datasets in order to obtain an accurate fit~\citep{golding2016fast}.
%
This is a significant limitation in the context of robotics applications, where data-gathering is often costly, and it is therefore beneficial for models to perform well with less data.
%
By contrast, GPs provide a favourable trade-off between capturing complex interactions between features, while also fitting smooth and plausible predictive surfaces using relatively small amounts of sample data.

Alternatively, graphical models such as Bayesian networks can model probabilistic relationships between multiple variables~\cite{heckerman1998tutorial}, and have been used successfully in a variety of similar environment monitoring applications~\citep{uusitalo2007advantages, aguilera2011bayesian}.
%
However, these are somewhat less suited to managing continuous data, and the discretisation process introduces additional challenges.
%
These factors, combined with the ubiquity of GP models in the literature, motivate our choice of GPs as the primary modelling tool to address \challengeref{challenge:modelling}.

\subsection{Scaling GP methods}
\label{ssec:gp_scaling}

The computational demand of GPs (see Section~\ref{ssec:gp_complexity}) is one of the key limitations to their use in large-scale problems.
%
Our work considers GP models of unknown environment processes, which are updated online based on observations.
%
In long-term or persistent monitoring missions, the GP dataset can grow without bound, ultimately making inference operations intractable.
%
The work in this thesis does not explicitly address bounding the size of the GP dataset, as we limit ourselves to experiments where GP inference with the full dataset remains tractable.
%
However, there are several existing techniques that could be integrated with our work in order to scale it to larger problems---we provide a brief overview of some such techniques below.

The main class of techniques for scaling of GPs is known as \emph{sparse approximations}.
%
The idea of these methods is to approximate the GP posterior for a training set of $\gpsize$, using a small set of $\gpinducingpts$ \emph{inducing variables}.
%
This reduces the time complexity of inference from $\bigO{\gpsize^3}$ to $\bigO{\gpsize \gpinducingpts^2}$~\cite{bauer2016understanding}.
%
Many different sparse approximation methods have been developed, along with different methods for selecting the inducing points, each of which makes various assumptions about the form of the underlying data~\cite{quinonero2005unifying}.
%
More recent works have also incorporated techniques from deep learning to further improve the capability of GPs~\cite{damianou2013deep,wilson2016deep, salimbeni2017doubly, havasi2018inference, liu2020gaussian,jakkala2021deep}.

In this thesis, we use GPs as real-time models for data acquired through the on-board sensors of mobile robots.
%
\citet{osborne2008towards} present several useful optimisations for this setting in their work with GPs for real-time information processing.
%
First, they show that incoming data can be processed efficiently in an incremental manner, reducing the cost of model updates from $\bigO{\gpsize^3}$ to $\bigO{\gpsize^2}$.
%
Second, they note that accurate inference typically does not require the full observation history, and introduce a scheme for identifying and discarding stale (i.e. less informative) data points.
%
This provides a principled way of windowing the GP dataset, ensuring that its size remains bounded over long or indefinite horizons.


\section{Planning in unknown environments}
\label{sec:relwork_planning}

Objectives of exploration, information gathering, and learning in unknown environments have been the subject of many works in the planning literature.
%
In this section, we review some of the problem formulations and solution techniques that have been used to enable effective planning in such environments.

\subsection{Adaptive informative path planning}
\label{ssec:AIPP}

%
The adaptive informative path planning~(AIPP) problem involves planning a trajectory that maximises the information acquired in an unknown environment, subject to resource constraints on the path~\cite{popovic2024learning}.
%
AIPP is a core problem in robotics, arising across a breadth of applications including exploration, monitoring, inspection, and search and rescue~\cite{singh2009nonmyopic, fernandez2022informative, choudhury2020adaptive,cao2023catnipp,popovic2024learning}.
%
The work on long-term monitoring in this thesis does not explicitly use an information-based goal, instead adopting an objective of cumulative reward maximisation in an unknown, dynamic environment.
%
However, information gain is still an important consideration in the design of our planning approach, as we recognise that improving model accuracy can lead to better outcomes across the lifetime of the mission.
%
As such, we make use of techniques from several areas of the AIPP literature, which we provide an overview of in this section.


The \emph{adaptive} variant of the informative path planning~(IPP) problem refers to planning \emph{online}, reacting to incoming observations and adapting the plan accordingly.
%
Conventional (i.e. offline) IPP algorithms typically make strong assumptions about the environment, relying on a stationary environment with a known information distribution~\cite{galceran2013survey}.
%
These assumptions are extremely limiting in robotics, where domains are often characterised by high uncertainty and dynamic elements that cannot easily be modelled \emph{a priori}.
%
In Chapter~\ref{ch:safe_exp}, online replanning is an essential component of our safe exploration approach, allowing the robot to adapt to unexpected obstacles or failed traversal of difficult terrain.
%
Furthermore, offline methods tend to scale poorly to large environments, and do not generalise well across diverse environments and problems~\cite{tan2021comprehensive,popovic2024learning}.

\subsubsection{Environment representations}

The information-gathering objective in AIPP has been formulated in many different ways, depending on the environment representation and specifics of the task at hand.
%
In their recent review of learning-based methods for AIPP in robotics, \citet{popovic2024learning} introduce a taxonomy of AIPP methods which divides them into four environment representation categories: occupancy grids, GPs, graph-based, and neural representations.
%
The choice of environment representation depends heavily on the specifics of the problem---for example, neural radiance fields~\cite{mildenhall2021nerf} and variants thereof (e.g. \cite{yu2021pixelnerf}) are popular tools in mapping and 3D reconstruction.
%
In the case of information-gathering problems over continuous features $\processfunction$, GPs are a natural choice, and have shown success in many applications including mapping temperature distributions~\cite{ruckin2022adaptive}, light~\cite{cao2023catnipp,denniston2023fast}, water properties~\cite{hitz2017adaptive, yanes2023deep}, and vegetation~\cite{vivaldini2019uav, popovic2020informative}.
%
This, along with the  wider success  demonstrated by  GPs as tools for modelling natural processes as discussed in Section~\ref{sec:relwork_GPs}, motivates our choice of GPs as the primary modelling tool in this thesis.

It is worth noting that while we do make use of a GP model in this thesis, we plan over a compact, discrete representation of the physical environment as a topological map~(see Section~\ref{sec:topological_maps}).
%
This is in contrast to the works mentioned above, many of whose domains allow for fine-grained trajectory planning---although some previous works, such as \citet{ott2023sequential}, have also used graph-based environment representations for AIPP problems over GPs.
%
We employ the graph-based representation to make the long-horizon planning problem more tractable, in line with the literature in this area which we will discuss further in Section~\ref{sec:relwork_longterm}.
%
Lower-level aspects such as motion planning are delegated to separate subsystems, and fall outside the scope of this thesis.

\subsubsection{Evaluation metrics}

Another key aspect in AIPP problems is the \emph{evaluation metric}, which quantifies performance with respect to the mission objective, either as a direct representation or an approximation of the true objective~\cite{popovic2024learning}.
%
GP-based AIPP methods have used evaluation metrics including entropy~\cite{denniston2023learned}, mean uncertainty~\cite{wang2023spatio,hollinger2014sampling}, maximum value information~\cite{flaspohler2019information},  distribution divergence\cite{wang2023spatio}, and upper confidence bounds (UCBs)~\cite{marchant2014sequential}.
%
In Chapter~\ref{ch:LTM1}, we incorporate a UCB reward into our planning system in order to explicitly encourage information-gathering actions, while in Chapter~\ref{ch:safe_exp} we design a more application-specific volumetric gain measure to estimate information gain for environment mapping.
%
In each case, the information-based metrics are not themselves the mission objectives, but rather act as proxies which encourage the desired exploratory behaviour.

\subsubsection{Planning approaches}

We now consider the planning approaches used in the AIPP literature.
%
Many recent works have employed \emph{supervised learning} techniques, which use labelled datasets to learn the desired output behaviour.
%
Some works have created synthetic environments or simulators which approximate the real-world problem, using these to generate the training data~\cite{cao2023catnipp,popovic2020informative,ruckin2022adaptive, bai2017toward, zwecher2022integrating}.
%
Alternatively, training data can be acquired from previously executed missions~\cite{caley2019deep,hitz2017adaptive,hollinger2014sampling} or open-source datasets~\cite{georgakis2022uncertainty, hepp2018learn}.
%
However, for the purpose of this thesis, we consider each of these approaches to be too restrictive.
%
In the long-term missions we consider throughout this thesis, in areas such as coral reef monitoring~(Chapter~\ref{ch:LTM1}) and wildfire monitoring~(Chapter~\ref{ch:safe_exp}), it cannot be assumed that data from previous missions exists, nor that there is any other freely available data of sufficient quality to create a realistic simulator.
%
Indeed, in Chapter~\ref{ch:LTM2}, we note that one of the key limitations of the wildfire hotspot dataset~\cite{NASAmodis6} is its low temporal resolution, which was limited by the frequency of satellite passes over the region.
%
In general, long-term datasets with sufficient spatial and temporal resolution to build a high-quality simulator are rare, due to the high cost of data collection, so we choose not to use supervised learning methods which rely on the existence of such data.

We therefore turn to the \emph{reinforcement learning}~(RL) paradigm, which removes the reliance on pre-labelled data, and focuses instead on learning through feedback from interactions with the environment.
%
The AIPP problem can be formulated as a POMDP~\cite{kochenderfer2022algorithms}, in which the unknown process $\processfunction$ is a component of the state space, over which the robot maintains a belief.
%
With this in mind, we can consider the AIPP problem within the broader context of the literature on POMDP planning, which we explore in the following section.

A further alternative that has been used with success in AIPP is \emph{imitation learning}~\cite{choudhury2018data, liu2023learning}, where the policy is learned from expert demonstrations.
%
While such methods can produce highly effective policies, the work in this thesis assumes that we do not have access to expert demonstrations, and thus we rely entirely on online learning with minimal prior knowledge.


\subsection{Planning under partial observability}
\label{ssec:relwork_partial_observability}

Finding exact solutions to POMDP problems is known to be computationally intractable for problems of non-trivial size~\cite{papadimitriou1987complexity,silver2010monte}.
%
This is often attributed in the literature to two key factors, known respectively as the \emph{curse of dimensionality} and the \emph{curse of history}.
%
The curse of dimensionality refers to the fact that the size of the belief space used to solve POMDPs grows exponentially with $|\pomdpstatespace|$, the number of POMDP states~\cite{lee2007makes}.
%
The curse of history refers to the fact the belief-contingent planning space also grows exponentially with the planning horizon~\cite{pineau2006anytime}.
%
In this section, we discuss some of the key developments in the POMDP planning literature as they relate to the work in this thesis.
%
We restrict this discussion to online solvers, which have demonstrated significantly greater ability to scale to large problems than offline methods~\cite{lauri2022partially}.


The POMCP algorithm introduced by \citet{silver2010monte} has been hugely influential in POMDP planning, and uses MCTS to tackle both of the core challenges mentioned above.
%
POMCP extends the UCT algorithm from~\citet{kocsis2006bandit} to partially observable environments, using it to select promising actions during MCTS.
%
Combining this with a particle filter approximation of the belief state then allows for efficient belief updates as part of the same Monte Carlo procedure as the tree search.
%
The result is an algorithm that scales to much larger POMDP problems than were previously solvable.
%
A contrasting approach which has also seen much success is the DESPOT algorithm~\cite{somani2013despot}, which achieves POMDP planning at scale by randomly sampling a  set of determinised \emph{scenarios}.
%
While this approach has also demonstrated success in scaling to large POMDP problems, it has been shown to struggle in information-gathering problems in continuous spaces~\cite{sunberg2018online}.


% Subsequent works have taken further strides towards solving larger and more complex POMDP problems across diverse domains.
Subsequent works have extended POMDP techniques to continuous domains.
%
The POMCPOW algorithm from \citet{sunberg2018online} adapts POMCP to continuous action and observation spaces using progressive widening (see Section~\ref{ssec:progwiden}), with the addition of a weighted particle filter to encourage convergence to better solutions.
%
Continuous-time POMDPs have also been solved using discretisation~\cite{chaudhari2013sampling}, removing the continuous element altogether as a trade-off between model accuracy and computational tractability.
%
Alternatively, partially observable semi-MDPs~(POSMDPs)~\cite{mahadevan1998partially} explicitly model continuous-time actions, and have since been extended to solve asynchronous planning problems for multi-robot systems~\cite{omidshafiei2015decentralized,omidshafiei2016graph}.
%
In Chapter~\ref{ch:LTM2} we make use of temporal discretisation in our hierarchical planner in order to enable long-term planning, before extending this to an explicitly continuous-time model in Chapter~\ref{ch:LTM3}.

So far, this section has discussed some of the key developments that have paved the way for modern POMDP planning algorithms.
%
Within the broad area of planning under partial observability, the work in this thesis is guided by two key considerations: the GP belief representation of environment processes, and the goal of long-term planning.
%
We therefore dedicate the following section specifically to a discussion of planning with GP beliefs, before Section~\ref{sec:relwork_longterm} delves into the literature on long-term autonomy.


\subsection{Planning with GP beliefs}
\label{ssec:relwork_GP_beliefs}

The versatility of GPs as modelling tools (see Section~\ref{sec:relwork_GPs}) has led them to increasing prominence in the planning literature.
%
Our particular interest in this thesis is in GP representations of a robot's \emph{belief} over the dynamics of an unknown environment process, which can be updated online based on observations.
%
GP beliefs have been used in planning problems to model natural phenomena including terrain traversability~\cite{wachi2018safe}, radio signal strength~\cite{fink2010online}, hazardous radiation~\cite{turchetta2016safe, budd2020markov}, magnetic fields~\cite{viseras2019deepig}, ocean currents~\cite{duckworth2021time,budd2023bayesian}, and bacteria levels in a lake~\cite{hitz2017adaptive}.
%
In this section, we discuss some of the techniques that have been developed for planning with GP beliefs, across a variety of different---albeit interrelated---fields of study.

Several recent examples of planning with GP beliefs have approached problems through the framework of \emph{Bayesian optimisation}~(BO)~\cite{shahriari2015taking}, which seeks to find the optimum of an unknown function $\processfunction$ through an iterative process of noisy sampling.
%
BO typically uses a GP model of $\processfunction$, which is updated after each iteration as new observations are added.
%
Standard BO is a \emph{myopic} decision making approach, in that it only considers the next step when deciding on the best action, thereby failing to account for future rewards and often exhibiting suboptimal behaviour in multi-step problems.
%
The \emph{sequential} Bayesian optimisation~(SBO) framework presented by \citet{morere2017sequential} bridges this gap, building on decision making techniques introduced in previous works~\cite{marchant2014bayesian, marchant2014sequential}.
%
They introduce the BO-POMDP model for sequential Bayesian optimisation over GP beliefs, and demonstrate its capability as a non-myopic approach to informative path planning.
%
Note that the AIPP problem discussed in Section~\ref{ssec:AIPP} can be viewed as a sequential BO problem.
%
\citet{flaspohler2019information} take a similar approach to the maximum seek-and-sample problem, a close relative of IPP.
%
Their work leverages the maximum value information (MVI) heuristic from Bayesian optimisation to plan effectively for long-term information gathering with sparse data, using continuous-observation MCTS with a GP belief.
%
One limitation of both of these works is that the POMDP transition function $\pomdptransition$ is assumed to be deterministic and independent of $\processfunction$.
%
In Chapter~\ref{ch:LTM3} we focus specifically on stochastic transition dynamics as a component of a more realistic model for our long-term robot planning problem.
%
Moreover, while we do not explicitly consider cases where the unknown process can affect the transition dynamics, our formulation does leave this open to future work as a relatively straightforward extension.


These limitations are addressed in recent work by~\citet{budd2023bayesian}, which takes a Bayesian RL approach to planning in an unknown environment.
%
They frame their problem as a Bayes-adaptive MDP~(BAMDP)~\cite{duff2002optimal}, and develop a variant of the BAMCP algorithm~\cite{guez2013scalable} which allows for efficient planning over a GP-modelled environment process.
%
Importantly, the Bayesian framework optimally trades off exploration and exploitation, which ensures reliable performance in the single-mission setting they consider.
%
Their work also makes use of the \emph{root sampling} technique used in POMCP and BAMCP, demonstrating an equivalence relation which removes the need for computationally expensive GP belief updates during MCTS.
%
Despite the demonstrated success of this approach, however, we shall see in  Chapter~\ref{ch:LTM1} that this approach cannot be straightforwardly transferred to the long-term monitoring setting, where the mission lifetime might extend beyond the feasible planning horizon.


\subsection{Safe exploration}
\label{ssec:relwork_safe_exp}

Among the diverse environments in which autonomous robots are routinely deployed, many are marked by the presence of hazards or other safety-critical factors.
%
\emph{Safe exploration} addresses the problem of exploring an environment whilst respecting safety constraints, in order to prevent harm to the robot or its surroundings.
%
These constraints have been formulated in a variety of different ways, with the general goal of avoiding \emph{unwanted} or \emph{unrecoverable} states~\cite{pecka2014safe}.
%
\citet{sui2015safe} consider the problem of learning by sampling from a GP-modelled unknown function, requiring the sampled points to exceed some pre-specified safety threshold.
%
This work was later extended by \citet{sui2018stagewise} to separate the safety function from the objective function, allowing for efficient optimisation of the objective function while maintaining guarantees over the safety constraints.
%
In Chapter~\ref{ch:safe_exp}, we consider the objective of mapping as much of an environment as can be safely accessed, only visiting states in which the value of a GP-modelled unknown process---in this case, hazardous radiation---is within a safe bound.

In the context of safe exploration of MDPs, it is necessary to reason about state \emph{reachability} and \emph{returnability}---in contrast with the Bayesian optimisation setting, which assumes that observations can be taken freely from throughout the full domain.
%
\citet{moldovan2012safe} posit that in most physical systems, it is indeed \emph{not} the case that all states are accessible from all other states (a concept known as \emph{ergodicity}), and introduce an algorithm for MDP exploration which ensures returnability to the initial state.
%
The SafeMDP algorithm introduced by \citet{turchetta2016safe} extends this idea to safe exploration of MDPs using GPs, reasoning about both reachability and returnability.
%
However, this approach only ever selects goal states that are a single step away from the visited set, resulting in inefficient exploration.


\citet{budd2020markov} addresses this limitation with a safe exploration algorithm that reasons about multi-step reachability and returnability.
%
Their work models an unknown process as a GP, and incorporates a probabilistic transition function that can model influences of the unknown process on the robot's dynamics.
%
This is in contrast to the SafeMDP algorithm, which assumes deterministic transitions.
%
Consider, for example, an AUV exploring an ocean environment, where the  underwater currents are unknown \emph{a priori}---in this scenario, the currents directly affect the robot's navigation dynamics, and sufficiently strong currents could render certain states unsafe.
%
Certain actions may even become entirely infeasible if the current velocity exceeds the maximum velocity of the AUV.
%
Effective safe exploration in this setting requires an environment model that can be adapted as the mission progresses, and incorporated into the robot's reasoning about safety during exploration.
%
Similar concerns can arise in other domains, such as a UAV exploring in a windy environment~\cite{badings2022sampling}, or a ground robot navigating steep terrain~\cite{rutherford2021motion}.
%
However, the work by \citet{budd2020markov} assumes that the layout of the environment is given as a topological map, and considers only exploration of the unknown process itself.
%
In Chapter~\ref{ch:safe_exp}, we address the problem of safe exploration in a \emph{completely} unknown environment, where mapping of the environment is a component of exploration.

% We extend the reachability and returnability concepts to reason about multiple-step safety probabilities along paths.
%
% Along with the inclusion of transition costs in the exploration objective, this makes our algorithm far more cost-efficient and less myopic when exploring.
%
% Finally, we alleviate SafeMDP's deterministic transition function assumption and explore MDPs with probabilistic transitions than allow for modelling the impact of the unknown process on the robot's dynamics.
%
% For example, if the unknown process represents underwater currents acting on an autonomous underwater vehicle (AUV), high magnitude currents could push the robot into waypoints other than the intended goal waypoint~\citep{budd2022bayesian}.
%
% Some actions may even be entirely infeasible because the water current velocity from the goal waypoint towards the AUV is higher than the maximum water-frame speed of the AUV.
%
% Wind can have similar effects on an unmanned aerial vehicle~\citep{badings2022sampling}.
%
% If the unknown process is terrain steepness, higher terrain gradients could make it more likely that a wheeled robot slips into an unintended waypoint while trying to navigate to the goal waypoint~\citep{rutherford2021motion}.
%
% Other extensions of SafeMDP include multi-agent safe exploration~\citep{zhu2020multi}.

% The standard MDP formulation assumes a fully known model of the environment, and full observability of the current state.
%
% For sequential decision making under state uncertainty, the partially observable MDP (POMDP) formulation is commonly used~\citep{kaelbling1998aij,spaan2015jaamas,lauri2019aamas}.
%




\subsection{Mapping of unknown environments}
\label{ssec:relwork_exploration_unknown_envs}

So far, our discussion of unknown environments and partial observability has focused on cases where the unknown element has been some observable process or feature present throughout the physical environment, such as temperature or radiation levels.
%
We have assumed that the \emph{physical} layout of the environment as a topological map is known \emph{a priori}.
%
In this section, we consider the more general problem of exploration in completely unknown environments, in which a robot must explore without any prior map or knowledge of the environment layout.
%
This forms the foundation of the work in Chapter~\ref{ch:safe_exp}.


The problem of exploration of unknown environments has been addressed in many works through frontier-based approaches, which aim to guide the robot towards unknown areas of the map~\citep{yamauchi1998frontier, yamauchi1998mobile, freda2005frontier,akbari2021informed}.
%
As defined by \citet{yamauchi1998frontier}, a frontier is a location on the boundary between open space and unexplored space; thus, by moving to new frontiers, a robot can extend its map of the environment.
%
The research on exploration of unknown environments received significant attention in recent years due to the DARPA Subterranean Challenge (SubT), in which the goal was to develop teams of robots to autonomously explore underground environments.
%
In the context of SubT, teams of researchers developed and tested complex integrated systems which address problems such as localisation and mapping in GPS-denied environments, navigation in adverse terrains, or coordination of heterogeneous multi-robot teams  under communication constraints~\citep{tranzatto2022team,rouvcek2021system,hudson2022heterogeneous,morrell2022nebula,scherer2022resilient}.
%
Numerous exploration algorithms were developed as part of these efforts, a significant portion of which rely on frontier-based methods~\citep{bayer2019autonomous,dang2020graph,williams2020online,dang2019explore}.


The SafeEstMDP-Map algorithm that we present in Chapter~\ref{ch:safe_exp} also uses a notion of frontiers to drive the robot towards unknown areas of the map.
%
However, because it must maintain safety with regards to the unknown process, we also consider possible points which are not at the edge of known space but for which the GP prediction of the unknown process still has high variance---in a sense, these are frontiers in our belief space rather than the map of the physical environment.
%
Exploration approaches for large-scale domains are often hierarchical, with the aim of ensuring thorough exploration at a local level whilst considering when to move to other unexplored areas of the map at a global level~\citep{dang2019explore, dang2020graph,cao2021exploring,kim2021plgrim}.
%
In the context of SubT, where unknown and challenging terrain was a key consideration, many works focus on the \emph{traversability} of edges in the navigation graph.
%
In contrast, we either assume that traversability is either given in the form of a navigation MDP, or that it can be checked by simple ray casting, where an edge is traversable to the robot unless there is a visible obstacle on the way.
%
Moreover,  we do not separate the exploration algorithm between local and global levels.
%
Instead, our focus is on the use of GPs to model an external unknown process, and reasoning about safety with respect to that process.
%
This aspect of our work goes beyond what is considered in the SubT works, where this type of safety was not a focus.
%
We also note that our approach could in principle be integrated with more complex exploration approaches, in order to ensure an extra layer of safety against external processes.



\section{Long-term planning}
\label{sec:relwork_longterm}

A fundamental challenge when planning in long-term settings is computational complexity, as the search space typically grows exponentially with the planning horizon~\cite{kaelbling1998planning,pineau2006anytime}.
%
In this section, we provide a brief overview of existing application areas for long-term robot autonomy.
%
We then discuss some of the key techniques that have been developed to address the challenges of planning in this setting, and planning over long horizons more generally.
%
These techniques inform the design of our planners in Chapters~\ref{ch:LTM1} and~\ref{ch:LTM2}.

\subsection{Long-term autonomy in robotics}
\label{ssec:relwork_long_term_autonomy}

% \note{Brief background on other areas of LTA in  robotics? STRANDS, etc. Not necessarily that helpful for understanding the thesis, but maybe good as further motivation...}

Long-term autonomy is a growing area of robotics research, with the potential to deliver immense value across a breadth of industrial and research applications.
%
Different domains and mission objectives induce particular requirements on robot hardware, software, and algorithmic systems, which must be addressed in order to achieve successful long-term operation.
%
Here, we provide a brief overview of some of the technical challenges that arise in long-term robot autonomy, and some of the existing works that have addressed these challenges.


% We can consider these challenges in two broad categories.
% %
% The first category is the technical challenges, which inform the hardware and algorithmic requirements for successful long-term autonomy. % such as the perception, mapping, and decision making systems. 
% %
% The second category is the domain-specific challenges, the features of the particular application domains that make long-term autonomy particularly difficult.
% %
% Here, we provide a brief overview of the core challenges in each area, and some of the existing works that have addressed them.



The development of autonomous systems for some applications has been driven by  constraints on communication systems, which in some cases makes a certain level of autonomy a necessity.
%
In space robotics, communication delays due to signal propagation times can be on the order of minutes, making real-time teleoperation from Earth impossible.
%
During its first year on Mars, the NASA Perseverance rover autonomously planned or mapped almost 90\% of its \qty{17.7}{\kilo\metre} total distance travelled~\cite{verma2023autonomous}.
%
The software pipeline required to achieve this included an autonomous navigation system~(AutoNav); an automated system for selection of scientifically interesting features to examine based on visual data; and an on-board planner to schedule tasks and ensure efficient usage of the limited available energy~\cite{verma2023autonomous}.
%
Improvements to these planning systems through decades of research have enabled the Perseverance rover to pursue more ambitious scientific objectives than previous Mars rover missions were able to, and thus to make better use of the resources invested into the mission.
%
Missions in marine environments face many similar challenges, since communication through water is limited and unreliable, and maps of these environments (particularly the deep ocean) are also often difficult to obtain.
%
However, the technology in this area is significantly more mature, and there are countless examples in the literature of AUVs being deployed successfully on scientific missions.
%
Ocean gliders, for example, are simple AUVs which have seen great success in ocean monitoring and sampling missions~\cite{testor2019oceangliders}, with their long range and endurance making them particularly well-suited to long-term missions.
%
Propellor-driven long-range AUVs can offer additional mobility and control compared with gliders, and have recently achieved up to \qty{2000}{\kilo\metre} of continuous operation~\cite{phillips2023autosub}.

Terrestrial robots---also known as unmanned ground vehicles~(UGVs)---are also seeing increasing use in long-term missions, in which they often contend with unstructured and dynamic environments.
%
One of the  most prominent application areas for such robots is in agriculture, which can require navigation over challenging terrain and execution of complex tasks.
%
Robots are increasingly being used for tasks such as weeding, planting, harvesting, crop health monitoring, spraying of pesticides, and more~\cite{wakchaure2023application}.
%
Autonomous systems have been able to significantly improve upon the efficiency of traditional farming methods, boosting production and reducing the environmental impact of the agricultural sector.
%
Aerial robots, by contrast, are most acutely constrained by energy, and long-term or perpetual flight remains a significant challenge.
%
Solar power has been used to extend the flight time of UAVs, but such solutions tend to be contingent upon favourable weather conditions and carefully chosen flight paths~\cite{mateja2023energy}.
%
One alternative approach to enabling long-term autonomy for UAVs is demonstrated by \citet{peloquin2016design}, who developed a UAV capable of autonomous landing and takeoff from lakes---between flights, this UAV could float passively on the surface of a lake while recharging its batteries through a solar panel.
%
While this particular approach is rather specific and limited in scope, it is a testament to the research efforts being put towards the challenge of enabling long-term autonomy in aerial robots.
%
UAVs offer incredibly wide-ranging  application potential, from agricultural and industrial monitoring, to wildfire monitoring, border surveillance, and more~\cite{mohsan2022towards}.

Robots have also been deployed in more human-centred environments, where autonomous operation may involve navigation of complex systems and safe operation in the presence of humans.
%
This is exemplified in the problem of autonomous driving, which requires robots to navigate complex road networks alongside other road users, and make real-time decisions based on their surroundings.
%
Autonomous driving systems are becoming increasingly prolific, but as yet few have been able to achieve reliable operation for prolonged periods without human intervention~\cite{chen2024end}.
%
Many similar challenges are faced by service robots, which work for or alongside humans in environments such as offices and care homes~\cite{kunze2018artificial}.
%
These robots additionally will often have to manage complex planning tasks, adapting to ever-changing requirements in complex and dynamic settings~\cite{hawes2017strands, trainum2023robots}.

The focus of this thesis is on addressing the planning challenges of long-term robot autonomy in unstructured outdoor environments, for applications such as ecological monitoring and precision agriculture.
%
The difficulty of planning effectively over long horizons in these settings is compounded by each of the challenges outlined in Section~\ref{sec:challenges}.
%
Our aim is to develop models and planning approaches which address these challenges in meaningful and practical ways, and to demonstrate the effectiveness of these approaches in realistic planning scenarios.


\subsection{Hierarchical planning}
\label{ssec:relwork_hierarchical}

The challenges of long-horizon planning are often addressed through the use of hierarchical planning methods.
%
These methods introduce abstractions or subgoals which reduce the search space of the problem---either by reducing the branching factor, or the length of plans that need to be computed---in order to make larger problems more tractable.
%
% This will typically involve reducing the branching factor, or the length of plans that need to be computed.
%
In the context of sequential decision making under uncertainty, hierarchical planners are often designed with the rationale that constructing detailed plans far into the future is unhelpful, since the evolution of the state cannot be accurately predicted.
%
In such cases, a coarse-grained model may be sufficient for long-horizon planning.
%
We use this principle to guide our planner designs in Chapters \ref{ch:LTM2} and \ref{ch:LTM3}.

The MAXQ model from \citet{dietterich2000hierarchical} is an early example of a hierarchical method in reinforcement learning.
%
This approach works by decomposing an MDP into a hierarchy of smaller MDPs, whose value functions combine additively to form the value function of the original MDP.
%
Whilst originally presented as a model-free RL approach, this work was later used as the basis for a model-based planning algorithm in~\citet{diuk2006hierarchical}.
%
However, despite its successes, the MAXQ approach also has many limitations.
%
Most notably,  the value functions within the hierarchy are computed by backing up values computed from the lowest level upwards  requiring computations over the full state-action space; this is known as a \emph{bottom-up} approach.
%
The MAXQ algorithm also relies on a manual process of task decomposition, which presents a significant barrier to generalisation across different domains.
%
Another canonical approach in  the hierarchical planning literature is the hierarchical task network~(HTN) introduced by \citet{erol1994htn,erol1996complexity}, which has demonstrated success in a variety of complex robot planning tasks~\cite{obst2005using,hayes2016autonomously}.
%
HTNs rely heavily on domain knowledge, working best in structured environments where a clear task decomposition exists.
%
In their original form, they also assume deterministic action outcomes, although later works have extended the approach to non-deterministic domains~\cite{hogg2009learning}.

In this thesis, hierarchical planning is of particular interest as a means of managing the computational challenge of planning over large domains and long horizons.
%
The \emph{options} framework from \citet{sutton1999between} moves us in this direction, generalising the notion  of actions to include closed-loop policies for taking actions over time.
%
An option is an example of a \emph{macro action}, a composite action consisting of a sequence of \emph{primitive} actions.
%
This idea provides a convenient mechanism for MDP planning across multiple timescales, since each macro action can be treated as a single decision-making unit during planning.
%
However, the options framework is still a bottom-up approach, meaning it will tend to become quite slow in problems where precomputed low-level policies are not available---as is the case throughout this thesis.
%
The abstract MDP~(AMDP) introduced by \citet{gopalan2017planning} instead decomposes the original MDP problem into sub-tasks in a top-down manner,  producing a  more efficient planning approach which ``decides what a good subgoal is before planning to achieve it''.
%
\citet{kaelbling2011hierarchical} take a hierarchical approach to combined task and motion planning, by first planning over an abstract representation of the problem, then realising only the first step of that plan with a low-level motion planner before replanning.
% 
We incorporate elements from each of these works in developing our hierarchical planning framework in Chapter~\ref{ch:LTM2}, adapting them to the setting of long-term monitoring of a continuous, GP-modelled environment.


% Several other works have addressed persistent spatiotemporal monitoring with single \cite{binney2013optimizing,baykal2017persistent} and multiple robots \cite{lan2016rapidly,ma2018multi}, but these works do not consider resource management as a component of the planning problem. 



\subsection{Persistent monitoring}
\label{ssec:relwork_persistent_monitoring}

Throughout this thesis, we refer to the problem of \emph{long-term} monitoring, in contrast with \emph{persistent} monitoring, as we do not explicitly consider missions of indefinite length.
%
However, as we shall discuss in Section~\ref{sec:future_work}, bridging this gap would be trivial, requiring as a minimum only minor modifications to our handling of input data for the GP models.
%
The literature on persistent monitoring therefore significantly informs the work in this thesis, so we discuss some of the relevant works here.


Many previous works have addressed persistent monitoring problems in single-robot ~\cite{binney2013optimizing, singh2010modeling, santos2017spatio, sears2022mapping,ma2018data} and multi-robot~\cite{tiwari2016resource, lan2016rapidly, ma2018multi, nguyen2015information,low2008adaptive,kantaros2021sampling,suryan2020learning} settings.
%
These works typically frame environment monitoring in terms of information gain maximisation or uncertainty reduction over GPs, similar to the AIPP problems discussed in Section~\ref{ssec:AIPP}.
%
Persistent monitoring can be tackled hierarchically, as done by \citet{nayak2024data}, who use a multi-armed bandit framework to address the high-level problem of allocating regions to robots.
%
\citet{krause2008near} address the monitoring problem from the perspective of fixed sensor placement, developing a sequential greedy algorithm that maximises mutual information across the environment.
%
Later work by \citet{binney2013optimizing} poses the problem as graph-based IPP over a continuous spatiotemporal environment process, a very similar setting to the one we consider in this thesis.
%
In contrast to our work, however, the mission objective in their work is uncertainty reduction at waypoints in the environment, and they incorporate sampling along graph edges as well as at nodes, something we do not consider in this thesis.
%
\citet{ma2018data} incorporate online learning of GP hyperparameters into their spatiotemporal monitoring algorithm, enabling their environment model to improve over the course of the mission.
%
We follow a similar process for GP hyperparameter learning in Chapter~\ref{ch:LTM1}, specialised to our multi-mission setting to allow the learning to happen during the robot's down-time between missions.
%

This thesis focuses on monitoring problems with the goal of explicit \emph{reward maximisation}, rather than information gain.
%
Whereas information gain objectives focus on learning about the environment, reward maximisation focuses on accumulating high-value samples or observations from it.
%
Several problems in the path planning literature are closely related to this goal.
%
In the \emph{orienteering problem}~\cite{vansteenwegen2011orienteering}, the goal is to find a reward-maximising path that respects a budget constraint (e.g. on energy consumption or time taken).
%
\citet{yu2016correlated} pose a correlated version of the orienteering problem for persistent surveillance tasks, where the utility of observations considers spatial correlations between locations based on proximity.
%
They evaluate their approach in a persistent surveillance task for a UAV, showing that it is effective in small domains for generating effective tours within the constraints of limited travel range.
%
\citet{yu2015anytime} instead consider rewards which are gathered by spending \emph{time} at points of interest, introducing a more explicit trade-off between time spent travelling and time spent sensing.


The infinite horizon in persistent monitoring problems presents a distinct challenge from the general planning problems discussed in Section~\ref{sec:relwork_planning}.
%
Some works have explicitly planned over infinite horizons by finding periodic solutions that approximate the optimal infinite horizon trajectory~\cite{lan2013planning,pinto2020multi}.
%
However, finding such solutions is intractable in general, particularly in the high-uncertainty environments that are the focus of this thesis.
%
More commonly, problems with indefinite horizons are simply addressed using a receding planning horizon, which allow planners to look ahead as far as is necessary (and computationally tractable) to generate effective plans.
%
Receding horizons can take several different forms---for example, planning with a fixed $n$-step lookahead~\cite{marchant2014sequential}, or enforcing a maximum search depth in MCTS~\cite{morere2017sequential}.
%
\citet{jones2015information} combine a receding horizon planner with linear temporal logic~(LTL) constraints, finding a middle ground which allows for planning over finite horizons while providing guarantees over certain aspects of the infinite horizon behaviour.
%
Once again, however, this approach makes highly restrictive assumptions about the domain representation, and is only tractable in small domains.
%
The algorithms we present in Chapters \ref{ch:LTM1} and \ref{ch:LTM2} therefore adopt receding horizon approaches, which afford the greatest flexibility for planning in complex environments.
%
We allow these planning horizons to be guided by practical constraints, such as the battery life of the robot.


\section{Planning under resource constraints}

Mobile robots operating out in the real world are invariably subjected to a variety of practical resource constraints, which may include battery life, on-board memory, or time.
%
In this section, we consider different formulations of resource constraints that have been used in the planning literature, and the techniques used to address them and enable effective deployment in the real world.




\subsection{Constrained path planning}

Some works have addressed resource-constrained planning by extending classical graph-based path planning problems.
%
\citet{asghar2023energy} frame the problem of energy-aware routing for a battery-constrained robot as a variant of the travelling salesperson problem~(TSP), in which a robot must efficiently visit every location in its environment while also recharging its battery at \emph{depots} as needed.
%
We adopt a similar framework of depot-based recharging in Chapter~\ref{ch:LTM2}, which focuses on addressing \challengeref{challenge:resources}.
%
Constrained shortest path~(CSP) problems are also a focal point in the literature on electric vehicle~(EV) routing~\cite{baum2015shortest, pourazarm2017optimal, kucukoglu2021electric}.
%
\citet{baum2015shortest} extend the CSP problem to use realistic battery charging models, an element we introduce into our work in Chapter~\ref{ch:LTM3} to link \challengeref{challenge:resources} and \challengeref{challenge:stochastic}.
%
Different versions of the EV routing problem have been formulated, for example with goals of finding the most energy-efficient~\cite{handler1980dual} or fastest~\cite{storandt2012quick} routes while incorporating the necessary stops at charging stations.
%
In EV routing, similar to our long-term planning setting, planning multi-step routes with charging stops greatly expands the range that the vehicles have access to.


The main limitation shared by these works is that they assume static and fully-known environments, and thus do not have straightforward extensions to the dynamic, partially observable environments we are interested in.
%
However, we shall see in Chapter~\ref{ch:LTM1} that we are able to use precomputed shortest path lengths as a way to prune actions during MCTS.


\subsection{Constrained sequential decision making}


% Our interest in this thesis is in incorporating resource replenishment into a long-horizon reward maximisation problem, enabling a robot to plan towards its mission objectives across many depletion and replenishment cycles.

Resource constraints have also been incorporated into sequential decision making problems as extensions of various MDP models.
%
\emph{Constrained MDPs}~\cite{altman2021constrained} encompass a broad class of problems, which in general involve an agent seeking to maximise some utility function (e.g. information gain) whilst bounding a cost function (e.g. energy consumption).
%
Subsequent work has generalised this notion to constrained POMDPs~\cite{isom2008piecewise}, for which a constrained variant of the POMCP algorithm can be used for planning~\cite{lee2018monte}.
%
The short-horizon planning sub-problems we solve in Chapters~\ref{ch:LTM1} and \ref{ch:LTM2} can be viewed as instances of constrained POMDPs, which we solve using MCTS with action pruning.
%


The standard constrained MDP framework does not incorporate the notion of resource \emph{replenishment}, which we introduce into our work in Chapter~\ref{ch:LTM2} to allow us more flexible longer-horizon planning.
%
This is addressed by the \emph{consumption MDP} introduced in \citet{blahoudek2020qualitative}, which models resource depletion and replenishment---however, their work only addresses the objective of planning a path that will visit goal states infinitely often while avoiding resource exhaustion.
%
Other works have incorporated resource replenishment into variations on the orienteering problem~\cite{wallace2020orienteering,pourazarm2017optimal} in order to achieve long-term autonomy.
%
In Chapter~\ref{ch:LTM2}, we consider a resource-constrained problem in which the robot state is fully observable, and resource consumption is deterministic.
%
This allows us to incorporate resource constraints in a simpler way than the general POMDP setting in order to address \challengeref{challenge:resources}.
%
We also show in Chapter~\ref{ch:LTM3} that this approach can be extended to the stochastic setting to address \challengeref{challenge:stochastic}, under certain assumptions about the form of the resource consumption model.


%\citet{tiwari2016resource} addresses distributed coverage over a GP-modelled environment with resource constraints, where the team objective is to reduce uncertainty over the GP without exceeding a budget constraint. % Maybe worth additn as a mention of constrained planning with a GP model
%


It is worth noting that resource constraints can factor into robot mission planning  in many more ways, depending on both the scenario itself and the modelling assumptions used to represent it.
%
For example, in the context of heterogeneous robot teams, \citet{liu2020monitoring} consider that there might be variable costs associated with each \emph{deployment}, and address the problem of deciding when to deploy.
%
The placement of charging stations can also be optimised to improve mission outcomes~\cite{lam2014electric,kundu2018charging,cui2019electric}, although this is outside the scope of this thesis.


\subsection{Long-term and persistent problems}

Resource constraints have been incorporated into  long-term and persistent planning problems.
%
In long-term robot missions, it is actually \emph{necessary} to consider resource constraints to some extent, since mobile robots have finite battery life.
%
Much of the work in this area to date has focused on persistent surveillance problems, often for multi-robot teams, with mission objectives and constraints formulated in a variety of ways.
%
\citet{aksaray2015distributed} use temporal logic constraints to minimise the time between visits to locations of interest in the environment, while ensuring each agent periodically visits a base station to refuel.
%
This approach allows them to provide formal guarantees over their mission specification, but does not extend easily to complex reward structures or partial observability.
% 
Other works address planning for persistent surveillance with energy-constrained UAVs~\cite{nigam2011control, scherer2017short}, but again these do not generalise beyond coverage objectives.
%
A popular approach to persistent UAV missions involves the use of mobile ground robots as charging stations for the UAVs~\cite{seyedi2019persistent,mathew2015multirobot,lin2022robust}.
%
This approach creates a more complex planning problem (as well as adding to the technical difficulty of deployment), including decisions about where to rendezvous for recharging.
%
However, it also allows for greater flexibility in mission planning, as charging stations can be relocated dynamically to improve monitoring efficiency.

As is the case with long-term planning in general, hierarchical methods can be used to make constrained long-term planning problems more tractable.
%
\citet{eiffert2020hierarchical} present a hierarchical planning framework for robust long-term operation of field robots in unstructured environments, geared towards agricultural applications.
%
Their work focuses on balancing the challenges of long-term, mission-level planning under resource constraints with path planning in highly dynamic environments.
%
This is handled in their hierarchy by separating these components into a low-level dynamic path planner, and a high-level, long-term mission planner.
%
This allows the low-level planner to tackle the fine-grained problem of local path planning, while the high-level planner uses an abstract, graph-based representation of the domain to plan over longer horizons.
%

An alternative approach to resource management in long-term planning is in the work by \citet{tomy2019battery}, which considers the problem of when to charge for a long-life autonomous robot performing a series of time-windowed tasks.
%
Their work demonstrates the advantage of flexible scheduling in a stochastic setting compared with a more rigid, rule-based scheduling approach.
%
Although we do not frame our missions as task scheduling problems, we reach a similar conclusion in  Chapter~\ref{ch:LTM2} in the context of long-term monitoring---we see that in monitoring an uncertain environment, performance improves as the robot learns about its environment and adapts its charging schedule accordingly.


\subsection{Chance-constrained planning}

%
In stochastic settings where future resource consumption cannot be predicted with certainty, it is often  impossible to provide strict guarantees of resource constraint satisfaction---or, where it is possible, doing so would tend to result in overly conservative behaviour.
%
Instead, chance-constrained approaches place a bound on the allowable \emph{probability} of failure.
%
This affords much greater flexibility in planning, allowing the robot to accept a certain level of risk in order to obtain higher rewards.
%
% The chance constraint can be set based on practical considerations, such as by weighing the real-world cost of constraint violations against the expected incremental reward from riskier behaviour. 
%
In Chapter~\ref{ch:LTM3}, our focus is on extending the hierarchical planner from Chapter~\ref{ch:LTM2} to this setting in order to address \challengeref{challenge:stochastic}.


The chance-constrained MDP~(CC-MDP) and chance-constrained POMDP~(CC-POMDP) generalise the constrained MDP and POMDP respectively to the setting of stochastic resource consumption.
%
Chance-constrained planning is a more difficult problem than regular constrained planning, since all actions and outcomes in a policy are now coupled by the chance constraint.
%
\citet{ayton2018vulcan} introduce an MCTS approach for CC-MDPs which overcomes this challenge by decomposing the chance constraint into constraints over individual state histories, allowing them to efficiently find approximately optimal solutions.
%
The more recent ConstrainedZero algorithm~\cite{moss2024constrainedzero} tackles CC-POMDPs using MCTS, applying neural networks to learn the optimal policy and value functions, as well as approximate the failure probability.
%
This algorithm is able to maximise reward while ensuring a specified level of probabilistic constraint.
%
However, as yet these approaches have not been demonstrated to scale to long-horizon planning.
%
In contrast, \citet{ono2015chance} present a dynamic programming approach to chance-constrained planning, demonstrating it as a computationally efficient solution to real-world, safety-critical planning problems.
%
However, this approach assumes a fully observable state, and would not extend to our highly uncertain, partially observable setting.

In the face of uncertain resource consumption, other techniques can be used to mitigate the risk of constraint violations.
%
\citet{mitchell2015multi} incorporate the  useful notion of a \emph{recourse} strategy into their work on persistent surveillance.
%
They frame persistent surveillance as a task planning problem with stochastic task costs, in which a chance constraint is applied to resource consumption.
%
Their recourse behaviour is a recovery mechanism which triggers in the event of unexpected energy expenditure, re-routing the robot to reduce the number of tasks it will try to complete before its next opportunity to recharge at a depot.
%
This allows it to avoid resource exhaustion in emergency situations, providing an additional layer of robustness in the face of uncertain resource consumption.
%
Our stochastic planner in Chapter~\ref{ch:LTM3} follows a similar approach to this, adopting a chance-constrained objective and incorporating a recovery behaviour to avoid constraint violations in case of unexpected resource consumption.
%
In addressing stochastic action outcomes in Chapter~\ref{ch:LTM3}, we relax the requirement of satisfying the chance constraint over the full mission, instead applying it to individual outings of the robot away from depots.
%
This both simplifies the planning problem, and provides a more sensible framework for risk management in a context where missions might go on indefinitely.
%
We are then able to implement an efficient action pruning regime to ensure constraint satisfaction within belief-space MCTS.