\chapter{Long-Term Monitoring with Stochastic Action Durations}
\label{ch:LTM3}

\minitoc


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


Mobile robots operating in natural and unstructured environments interact with those environments in complex ways.
%
Navigation through the environment can be affected by factors including terrain, weather conditions, unexpected obstacles, and even the presence of other agents~\cite{street2020multi}.
%
Likewise,  the charging and discharging curves of a robot's battery are influenced by the ambient temperature in the environment~\cite{johnson2001temperature}, as well as general battery health and the actions being performed by the robot.
%
These complex interactions mean that it is often difficult to accurately predict the outcomes of actions.
%
From a planning perspective, this poses a considerable challenge, as a planner must be able to reason about the consequences of actions in order to make effective decisions.
%
So far,  we have focused on deterministic models of action outcomes, which make the assumption that the outcomes of actions are known with certainty.
%
Stochastic models provide a richer framework for capturing the variability and uncertainty of planning in the real world, allowing for more robust and effective plans to be generated.
%
In this chapter, therefore, we extend the work presented so far to tackle \challengeref{challenge:stochastic}, by incorporating stochastic models of the outcomes of robot actions.

Specifically, we introduce stochasticity into our models of navigation and resource consumption, capturing the variability and incomplete information that is inevitably present in real, unstructured environments.
%
For navigation actions, we describe the duration of each action as a probability distribution, rather than a deterministic value.
%
This allows us to explicitly model the fact that the time taken to traverse a path through the environment may vary in ways that cannot be predicted in advance.
%
For resource replenishment actions, we specify the time spent charging, and model the resulting resource level as a distribution, capturing variability in the charging process.
%
This adds significant complexity to the planning problem, since actions now have uncertain outcomes, in addition to the uncertainty that already in the environment process.
%
The effects of these uncertainties compound over time, making long-horizon planning particularly challenging.
%
The addition of stochastic action durations also compounds the challenge of resource management (\challengeref{challenge:resources}), since it is no longer possible to ensure satisfaction of the resource constraints with certainty.
%
Instead, we move to a chance-constrained approach, where we provide a probabilistic guarantee that the robot battery charge will remain above some minimum threshold with a certain probability.


Our contribution in this chapter is a planning framework for long-horizon mission planning that handles resource constraints in stochastic environments, tackling \challengeref{challenge:resources} and \challengeref{challenge:stochastic} simultaneously.
%
We extend the work from Chapter~\ref{ch:LTM2}, which assumed deterministic action outcomes, and relied on a discrete representation of time and resource levels for planning at the high level.
%
We introduce stochastic models for navigation and battery charging actions, which better represent the challenges of robotics in unstructured outdoor environments.
%
By modelling action durations as exponential distributions with deterministic delays, we are able to enforce a chance constraint over the robot's battery level on each outing away from a base station.
%
We plan at the high level using MCTS in belief space, which handles continuous spaces using progressive widening rather than discretisation, making efficient use of computation time by focusing on promising areas within the search space.
%
We demonstrate that our approach is able to plan effectively in challenging settings, obtaining higher performance than the previous work while producing fewer constraint violations.





% Planning in these settings inevitably involves a significant degree of uncertainty, not only from the processes under observation, but from the dynamics of the robot's interactions with its environment as well.
%

% In this work, we address the problem of long-term monitoring in the ecological setting, in which a robot is deployed over a period of weeks or months to observe some unknown environment feature.
% %
% The robot has a constrained resource, which it can replenish at particular locations in the environment which we refer to as \emph{depots}. 
% %
% We pose  the monitoring problem as a goal of maximising the cumulative value of observations of some unknown environment feature over the course of the mission.
% %
% In the wildfire monitoring case, for example, an unmanned air vehicle~(UAV) might be deployed to identify and track areas where the fires are burning most intensely. 




\subsection{Problem formulation}
\label{sec:LTM3_problem_formulation}

We extend the model from the previous chapter to consider stochasticity in action outcomes.
%
For navigation actions, we model each action as consisting of a fixed minimum duration, as well as an exponentially-distributed stochastic component---we outline this model in full in Section~\ref{ssec:nav_dynamics}.
%
Stochastic durations in turn imply stochastic resource consumption for navigation actions, since an action which takes longer to execute will also consume more resources.
%
We also consider a stochastic model of resource replenishment, where charging for a particular length of time now results in a \emph{distribution} over resource levels, rather than a precisely known outcome.
%
We describe the resource model in Section~\ref{ssec:resource_model}.


Our mission objective, as before, is to maximise the cumulative reward from observations taken of $\processfunction$ up to a mission horizon $\pksmdphorizon$, which corresponds to many days.
%
This is now subject to the chance constraint that on each \emph{outing} where the robot ventures away from a depot, its resource level must remain above a threshold value $\batterythreshold \in [0, 1)$ with probability $\constraintprob$.
%
This threshold is introduced as an additional parameter that can be used to set an allowable level of risk, depending on the context of the mission.
%
We formulate the chance constraint in terms of outings rather than across the entire mission to better accommodate the long-term nature of the planning problem.
%
In a context where missions might span very long periods of time, or even continue indefinitely, it is more intuitive to consider the chance constraint on a per-outing basis, decoupled the constraint from the length of the mission.
%
We assume that in most practical applications, there would be a high cost associated with a robot running out of battery in the field, since this would typically require human intervention to return the robot to a depot.
%
Therefore, the battery threshold acts as a reserve level that can be used when constraint violations do occur, ensuring that complete depletion of the battery will be rare.

As in the previous chapter, we model this monitoring problem as a {\algshort{}}~(Definition \ref{def:LTM_PKSMDP}).
%
This time, we consider stochastic action outcomes in the transition dynamics.


\subsection{Navigation dynamics}
\label{ssec:nav_dynamics}


Action durations have been modelled as continuous stochastic processes in previous works using several different distributions, including exponential~\citep{eisentraut2010probabilistic, mansouri2019multi, azevedo2020long}, $\chi^2$~\cite{ziparo2010probabilistic}, phase-type~\cite{street2020multi}, and Gaussian~\cite{cielniak2018discrete}.
%
PTDs, which we introduced in Section~\ref{ssec:PTDs}, can be fit to arbitrary non-negative distributions~\cite{thummler2006novel}.
%
\citet{street2020multi} used them in the context of action duration modelling in robotics, by fitting PTDs to real data in order to construct realistic models for robots navigating under congestion.

Here, we adopt the simpler exponential distribution with a deterministic delay to model action durations.
%
On its own, the exponential distribution is a somewhat unrealistic model, as it offers a non-zero probability that any action will complete arbitrarily quickly.
%
The deterministic delay mitigates this, by enforcing minimum durations for each action.
%
\correction{Since PTDs are essentially mixtures of exponential distributions, formulating action durations in this way allows us to evaluate the planner in a scenario where it can accurately model stochastic action durations.
    %
    Further, the fact that PTDs can be fit to arbitrary non-negative distributions means that our approach remains compatible in principle with other action duration models---albeit at a greater computational cost.}

\begin{definition}[Hybrid action model]
    For a given environment represented as a topological map $\tm = \langle \tmnodes, \tmedges \rangle$, each edge $\tmedge_i \in \tmedges$ has a corresponding hybrid action model $\actionmodel(\tmedge_i) = \langle \actionfixed_i, \actionstochastic_i\rangle$, where $\actionfixed_i$ is a deterministic delay (i.e. minimum duration), and $\actionstochastic_i$ is the rate parameter of an exponential distribution representing the remainder of the action duration.
\end{definition}


This provides a somewhat more realistic model for robot navigation than a pure exponential distribution, while retaining some of the computational benefits of that model.
%
Importantly, the techniques we shall use later in this chapter for enforcing the chance constraint are applicable to general PTD models with deterministic delays, of which the exponential distribution is the simplest case.
%
Thus, our methods could still apply to scenarios where higher-fidelity models are required, at the cost of some extra computation depending on the complexity of the chosen models.
%
It is also worth noting that while we now consider stochasticity in the durations of navigation actions, the outcome of these actions is still known---that is, if the robot executes an action to move from location $\tmnode_i$ to $\tmnode_j$, it is guaranteed to end up at the correct location, and the only uncertainty is over the time of arrival.
%


\subsection{Resource model}
\label{ssec:resource_model}


In the previous chapter, we modelled the robot's resource dynamics using fixed charging and discharging rates, effectively modelling the resource dynamics as a simple linear system.
%
While this simple model might be sufficient in some applications, its scope is somewhat limited.
%
We now introduce a more expressive \emph{resource model}, is able to accurately capture a broader range of resource dynamics.
%
\begin{definition}[Resource model]
    A resource model $\mathcal{B}$ is a tuple $\langle \ratedischargefunc, \ratechargefunc \rangle$, where $\ratedischargefunc:[0, 1]\rightarrow\mathbb{R}$ is a discharging rate function and $\ratechargefunc: [0, 1] \rightarrow \mathbb{R}$ is a charging rate function.
    % where $\ratechargefunc: [0, 1] \rightarrow \mathbb{R}$ and $\ratedischargefunc: [0, 1] \rightarrow \mathbb{R}$ are the charging and discharging functions respectively.
    % %
    Each rate function depends on the current resource level $b \in [0, 1]$.
\end{definition}

%
The rates $\ratechargefunc$ and $\ratedischargefunc$ describe the dynamics of the robot's finite resources while it is \stateactive{} and \statecharging{}, respectively.
%
As previously, any non-depot state where $b=0$ is a sink state.
%
In Section~\ref{sec:LTM3_experiments}, we shall use this resource model to express a realistic model of battery life, the most ubiquitous constrained resource in robotics problems.
%
Importantly, however, the model is not specific to batteries, and could be used to model any resource that is consumed and replenished during a robot mission, such as data storage capacity, thermal coolants, or other consumables.
%
In the case of battery, the charging rate $\ratechargefunc$ specifies a battery charging curve, while the discharging rate $\ratedischargefunc$ specifies the rate at which battery life is consumed while the robot is active.
%
As we shall see in Section~\ref{ssec:LTM3_high_level_planner}, we can also incorporate uncertainty or noise over these rates, to account for stochasticity or unmodelled variability in the charging or discharging processes.




% We now focus specifically on battery life as the constrained resource, and introduce a more realistic and expressive resource model for this case, where the charging rate can vary depending on the current resource level.
% %
% For example, the robot's battery might charge faster when it is low, compared with when it is almost full.




% Concretely, while active, the robot's resouce level decreases according to a discharging function $\ratedischargefunc$, and while replenishing it increases at a rate specified by function $\ratechargefunc$.
% %
% The battery's state of charge~(SoC) is denoted by the resource level $b \in [0,1]$, which represents its available energy as a fraction of the full charge capacity.
%
% Any non-depot state where $b=0$ is a sink state
%
% The charging rate $\ratechargefunc$ and discharging rate $\ratedischargefunc$ are then functions of the SoC.
%
% We refer to this description of the battery dynamics as a \emph{battery model}, denoted $\mathcal{B}$.



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

\subsection{Overview}
\label{ssec:LTM3_alg_overview}

We now extend the planning approach from the previous chapter to the stochastic setting.
%
In doing so, we introduce a new high-level planner which addresses the limitations discussed in Section~\ref{sec:LTM2_discussion}.
%
We also modify the action pruning mechanism from the low-level planner to consider the chance constraint.
%
We describe each of these components in detail in the following sections.


\subsection{High-level planning}
\label{ssec:LTM3_high_level_planner}

In Section~\ref{ssec:LTM2_high_level_planner}, we introduced the \highlevelmdp{} as the high-level model for our hierarchical planning framework.
%
One of the key features of this model is that it represents the high-level planning problem in a \emph{discrete} state space, even though the full  problem is continuous.
%
Discretisation of the time and battery life state factors introduces a degree of slack into the planning process, since the continuous values are conservatively rounded to the nearest discrete level.
%
This slack results in a less precise representation of the true state space, and therefore worse planner performance.
%
However, we showed that this approach could be effective in practice nonetheless, and indeed became more effective as the discretisation became finer---at the cost, of course, of increased computation time (Section~\ref{ssec:expt_planning_step}).
%
This approach also assumes a fixed belief representation while planning, as each \highlevelmdp{} is constructed by sampling from the current GP model.
%
This is not a major limitation in the deterministic setting, since the UCB heuristic was still able to encourage optimistic exploration of the state space, and each high-level plan was only ever executed for one step before replanning.
%
\correction{However, as we move to the stochastic setting, the discretisation-based and approach becomes more limiting, since actions can no longer necessarily be guaranteed to complete within any fixed number of timesteps---particularly in cases of action duration distributions with long tails.}
% 
We therefore introduce a new high-level planning model for this setting.

In particular, we now formulate the high-level planning problem as a \emph{high-level PKSMDP}, which captures navigation between depots as well as management of the constrained resource.
%
Unlike the \highlevelmdp{}, this model is continuous in both time and resource level, and provides a framework for the improved, belief-space planning approach which we describe below.

\begin{definition}[High-level PKSMDP{}]
    \sloppy
    For a given \algshort{} $\pksmdp$, navigation model $\actionmodel$, and resource model $\mathcal{B}$, threshold $\batterythreshold$ and probabilistic bound $\constraintprob$, we define a corresponding high-level PKSMDP $\hpksmdp = \langle \hpksmdpstatespace, \hpksmdpinitstate, \hpksmdpactionspace, \hpksmdptransition, \hpksmdprewardspace, \hpksmdphorizon \rangle$.
    %
    The known state space is $\hpksmdpstatespaceknown = \tmdepots \times T \times B$, where $\tmdepots$ is the set of depots, $T \in [0, \hpksmdphorizon]$ is the time, and $B \in [0, 1]$ is the resource level; and $\hpksmdpinitstate$ is the initial state; the unknown component $\hpksmdpstatespaceest$ represents the value of the unknown process, as in the full LTM-PKSMDP.
    %
    $\hpksmdptransition: \hpksmdpstatespace \times \hpksmdpactionspace \times \hpksmdpstatespaceest \rightarrow [0,1]$ is the stochastic transition function, which specifies the outcomes of \actionreplenish{} actions based on the resource model $\actionmodel$, and \actionnavigate{} actions based on the navigation dynamics $\mathcal{B}$.
    %
    $\hpksmdprewardspace: \hpksmdpstatespace \times \hpksmdprewardspace \rightarrow \mathbb{R}$ is the reward function, which is described below, and $\hpksmdphorizon$ is the planning horizon.
\end{definition}


The action space $\hpksmdpactionspace$ consists of \actionreplenish{} actions, which specify a duration, and \actionnavigate{} actions which specify a destination depot as well as a duration in which to reach it while satisfying the probabilistic constraints $(\batterythreshold, \constraintprob)$.
%
\actionreplenish{} actions can be specified for any duration from any (depot) state.
%
\actionnavigate{} actions must only specify destinations that can be reached from the current location with probability $\constraintprob$ within the specified duration, without resources dropping below $\batterythreshold$.
%
Our method for generating actions that satisfy these properties is described in Section~\ref{ssec:checking_reachability}.
%
The reward function $\hpksmdprewardspace$ estimates the reward that would be obtained for executing a \actionnavigate{} action $\hpksmdpaction\in \hpksmdpactionspace$; the reward for all \actionreplenish{} actions is zero.
%

We plan over the high-level PKSMDP using MCTS in belief space, as described by Algorithm~\ref{alg:belief_space_mcts}, with a few modifications to adapt this approach to the high-level planning problem.
%
In the in-tree selection phase (the $\textsc{SelectNode}$ method), rewards are estimated using the  method from Algorithm~\ref{alg:high-level-rewards}, which simulates a sequence of random walks and takes the highest reward obtained from these as its approximation of the true reward.
%
The same method is used in the random rollout phase (the $\textsc{PerformRollout}$ method).
%
This makes each trial of the high-level MCTS routine somewhat computationally demanding, but since the high-level PKSMDP is much smaller than the full PKSMDP, fewer trials are required to obtain reasonable planning performance, as we shall see in Section~\ref{sec:LTM3_experiments}.
%
Since charging actions now have stochastic outcomes, we now also use progressive widening over the outcomes of these actions when generating new child nodes (Line~\ref{line:generate_belief_child}), to ensure that the tree remains balanced during planning.
%
Rewards for navigation actions are estimated by sampling from the GP, whereas outcomes of resource replenishment actions are sampled from the resource model.


\subsection{Low-level planning}

As in the previous chapter, the job of the low-level planner is to execute actions generated by the high-level planner, which it receives in the form of constraints---a target depot $\LLtargetdepot$, and a deadline $\LLdeadline$ by which to reach it.
%
With the introduction of stochastic action durations, however, the low-level planner can no longer \emph{guarantee} reaching the depot before the deadline, as it could in the deterministic case.
%
Instead, it must select actions which probabilistically guarantee that depot $\LLtargetdepot$ will be reached before time $\LLdeadline$ with probability $\constraintprob$, without the resource level dropping below $\batterythreshold$.
%
In the following section, we describe our method for filtering out actions that do not satisfy this constraint.


\subsection{Checking reachability}
\label{ssec:checking_reachability}

For an action $\pksmdpaction \in \pksmdpactionspace$ to be considered feasible by the low-level planner, we need to ensure that \emph{if} action $\pksmdpaction$ were executed, then it would be possible for the robot to return to a depot in time with resource level $b \geq \batterythreshold$ with probability $\constraintprob$.
%
This is the stochastic analogue to the deterministic reachability check used previously in Algorithm~\ref{alg:belief_space_mcts} (Line~\ref{line:check_reach_det}).
%
Exact computation of stochastic shortest paths over continuous distributions is extremely challenging~\cite{frank1969shortest}.
%
We therefore use an approximation for the shortest path, over which we check the probabilistic reachability condition.

For the topological graph $\tm$ with stochastic edge models, we construct a \emph{determinised} graph $\tmdet$, in which the cost $\pksmdpcostfunc(\tmedge)$ of each edge is simply equal to its expected value in the probabilistic model:
%
\begin{equation}
    \pksmdpcostfunc(\tmedge_i) = \mathbb{E} \left[\actionmodel(\tmedge_i) \right] = \actionfixed_i + 1/\actionstochastic_i.
\end{equation}
%
%
We then introduce a stochastic version of the \textsc{GetAvailableActions} method used previously (Algorithm~\ref{alg:high-level-rewards}, Line~\ref{line:get_available_actions}), which filters available actions based on whether it will be possible to reach the target depot after executing them.
%
The new method is outlined in Algorithm~\ref{alg:stochastic_durations}.
%
For each action $\pksmdpaction \in \pksmdpactionspace$ available in state $\pksmdpstate$, we generate the \emph{chain} of actions corresponding to the shortest path onwards to the target depot (Line~\ref{line:action_chain}), computed in the determinised graph.
%
Each action in this chain consists of a deterministic component $\actionfixed_i$ and an exponentially-distributed stochastic component $\actionstochastic_i$.
%
The minimum duration for the chain of actions to execute is simply the sum of the deterministic components.
%
The stochastic components  $(\actionstochastic_1, \dots, \actionstochastic_n)$ then form a special case of the phase-type distribution known as the \emph{hypoexponential} distribution.
%
We can compute its CDF (Equation~\ref{eq:PTD_distribution_functions}), which we invert to obtain the duration required to complete the action chain with probability $\constraintprob$ (Line~\ref{line:prob_duration_expr}).

\begin{algorithm}[]
    \algsize
    \caption{{\sc Checking Available Actions with Stochastic Durations }}
    \label{alg:stochastic_durations}
    \textbf{Input}: \algshort{} $\pksmdp$, determinised graph $\tmdet$, current state $\pksmdpstate$, probabilistic bound $\constraintprob$, battery threshold $\batterythreshold$, target depot $\LLtargetdepot$, deadline $\LLdeadline$. \\
    \textbf{Output}: Reward value $r \in \mathbb{R}$
    \begin{algorithmic}[1] %[1] enables line numbers
        \Procedure{GetAvailableActionsStochastic}{$\pksmdp, \tmdet, \pksmdpstate, \constraintprob, \batterythreshold, \LLtargetdepot, \LLdeadline$}
        \State $\pksmdpavailableactions \gets \emptyset$
        \For{$\pksmdpaction \gets \textsc{GetEnabledActions}(\pksmdp, \pksmdpstate)$}
        \State $\pksmdpstate' \gets \pksmdptransition(\pksmdpstate, \pksmdpaction)$
        \State $\actionchain \gets a \cup \textsc{ShortestPath}(\tmdet, \pksmdpstate', \LLtargetdepot)$ \label{line:action_chain}
        \If{$t(\pksmdpstate) + \textsc{ProbDuration}({\actionchain, \constraintprob})  \leq \LLdeadline$} \label{line:check_reach_det}
        \State $\pksmdpavailableactions \gets \pksmdpavailableactions \cup \{\pksmdpaction\}$
        \EndIf
        \EndFor
        \If{$\pksmdpavailableactions = \emptyset$}
        \State $\pksmdpavailableactions \gets \textsc{GetFallbackAction}(\pksmdp, \pksmdpstate, \LLtargetdepot, \LLdeadline)$ \label{line:fallback_action}
        \EndIf
        \State \Return $\pksmdpavailableactions$
        \EndProcedure
        \item[]

        \Procedure{ProbDuration}{$\actionchain, \constraintprob$}
        \State $\ptd \gets \textsc{GetActionChainPTD}(\actionchain$)
            \State \Return  $\textsc{MinDuration}(\actionchain) + F^{-1}_\ptd (\constraintprob)$ \label{line:prob_duration_expr}
        \EndProcedure

    \end{algorithmic}
\end{algorithm}


Figure~\ref{fig:stochastic_action_model} provides a visual representation of these action chains, and example distribution functions for the time taken to complete action chains of different lengths.
%
We use the same approach of computing the duration of shortest path action chains when generating \actionnavigate{} actions for the high-level planner, in order to ensure that they are always feasible within the probabilistic constraint.
%
This ensures that the inputs received by the low-level planner are always valid.
%
In each case, the shortest path durations can be precomputed, since $\tm$ (and hence $\tmdet$) is known in advance.


\begin{figure}[]
    \centering
    \begin{subfigure}[b]{\linewidth}
        \centering
        \includegraphics[width=0.8\linewidth]{chapters/chLTM3/figures/PTD_chain.pdf}
        \caption{A chain of $n$ actions to reach the absorbing state $\mdpstate_n$.}
        \label{sfig:action_chain}
    \end{subfigure}
    \hspace{1cm}
    \begin{subfigure}[b]{\linewidth}
        \centering
        \includegraphics[width=0.7\linewidth]{chapters/chLTM3/figures/hybrid_action_chain.pdf}
        \caption{PDFs for the durations to complete chains of $n$ actions. Each action has a minimum duration $\actionfixed_i = \qty{1}{\second}$, and an exponentially-distributed component with expected duration $1/\actionstochastic_i = \qty{1}{\second}$.}
        \label{sfig:action_chain_graph}
    \end{subfigure}
    \caption[Stochastic action chain model]{Model for a chain of actions with stochastic durations.}
    \label{fig:stochastic_action_model}
\end{figure}

As an additional safety layer for the stochastic setting, we also incorporate a \emph{recourse strategy}, taking inspiration from the work by \citet{mitchell2015multi} on multi-robot persistent coverage.
%
In our case, the recourse strategy is a fallback policy which triggers in the event that no actions are available which satisfy the probabilistic constraint (Line~\ref{line:fallback_action}).
%
This policy simply navigates the robot along the shortest path to the nearest depot, where this path is calculated over $\tmdet$.
%
The effect of this is that when an action takes longer than expected and the robot is at risk of violating the resource constraint, it will abandon its current high-level action and prioritise reaching a depot to recharge.
%
This helps to reduce the number of constraint violations, ensuring that the robot can safely continue its mission even in the event of  unexpected delays.





%


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


We now evaluate the performance of our planner over a series of simulated experiments.
%
As a baseline, we compare to the Depot-MDP planner from Chapter~\ref{ch:LTM2}.
%
This planner does not consider stochasticity in the action durations or resource dynamics.
%
Thus, we adapt it to plan in this setting by using expected values for action durations and resource consumption.


For the experiments presented in this chapter, we adopt a piecewise linear battery model, as described below in Section~\ref{ssec:piecewise_linear_model}, wherein a full charge supports 12 hours of activity.
%
Similar to the previous chapter, we define a small high-level action set $\hpksmdpactionspace$ in order to narrow the scope of the planning problem.
%
In principle, however, the planner described in this chapter could use full the continuous space of action durations using progressive widening.
%
This action space consists of two types of \actionnavigate{} actions: the \actiontraverse{} action, which uses the shortest duration valid under the chance constraint to reach its destination, and the \actionexplore{} action which allocates the full available duration based on the current battery level.
%
For \actionreplenish{} actions, we define three actions which charge the battery up to 50, 80, and 100 percent respectively, representing the boundary points of the piecewise linear charging model.
%
In all experiments, we set the chance constraint of the stochastic planner to $\constraintprob = 0.99$.

\subsection{Battery charging model}
\label{ssec:piecewise_linear_model}

Following \citet{fu2019targeted}, we adopt a  piecewise linear model for battery charging, as shown in Figure~\ref{fig:battery_charging_model}.
%
\correction{This model provides a reasonably good approximation to the typical charging curve for an electric vehicle~(EV) or other lithium-ion battery device}~\cite{hoimoja2012ultrafast}.
%
The key feature of these charging curves is that they increase quickly and (approximately) linearly up to a state of charge~(SoC) of around 80\%, after which the charging rate slows down significantly.
%
\correction{Thus, while more complex non-linear battery models might be able to capture some additional nuances of real-world charging behaviour, the piecewise linear model provides a good balance between accuracy and computational efficiency for our purposes.}
%
In the case shown in Figure~\ref{fig:battery_charging_model}, the battery takes 6 hours on average to charge from empty up to 80\%, and a further 6 hours to reach 100\%.
%
A consequence of this charging behaviour is that EVs are typically operated mostly within the 20--80\% SoC range, as this is where their charging characteristics are most efficient~\cite{jin2022development}.
%
To account for any variability in the charging rate, we also include Gaussian noise over the final SoC value, which accumulates proportionally to the duration of the charging action, as shown in Figure~\ref{fig:battery_charging_model}.

We model the robot's battery discharging as a constant rate over time, so the amount of battery life consumed by a navigation action is directly proportional to the duration of that action.
%
Note that, since action durations are stochastic, this implies that battery consumption per-action is also stochastic.
%
Whilst we have selected a simple model of battery discharging here for illustrative purposes, our framework is more general and can capture  more complex discharging models.
%
For example, the discharge rate $\ratedischargefunc$ could be dependent on the type of action being executed, or be specified individually per action (e.g. if navigating on more challenging terrain draws more power), but for simplicity we use a fixed value here.


\begin{figure}[]
    \centering
    \includegraphics[width=0.6\linewidth]{chapters/chLTM3/figures/battery_charging_model.pdf}
    \caption[Piecewise linear battery charging model]{A piecewise linear model for battery charging. The curve shows the expected state of charge over time when starting from an empty battery, and the shaded area represents one standard deviation to either side.}
    \label{fig:battery_charging_model}
\end{figure}




\subsection{Planner horizon}
\label{ssec:LTM3_expts_horizon}

We first examine the performance of the planner across different planning horizons, in order to gauge its overall capability in the stochastic setting.
%
In this experiment, we adapt the $20 \times 20$ grid map domain from Section~\ref{ssec:LTM2_expts_horizon}.
%
We transform the domain replacing the fixed cost $\pksmdpcostfunc(\tmedge)$ of each edge with a stochastic model $\actionmodel(\tmedge)$ with the same \emph{expected} cost.
%
We randomly set the stochastic component to represent \qtyrange{20}{40}{\percent} of the total cost.
%
This variation in the amount of stochasticity is an important element, since it creates a richer and more realistic problem, where planners can consider trade-offs between paths with different levels of uncertainty over outcomes.
%
We use 250 MCTS trials for both the high- and low-level planners, and run each planner configuration 20 times---results are presented in Figure~\ref{fig:horizon_experiment_stochastic} and Table~\ref{tab:LTM3_horizon_expt}.


\begin{figure}[]
    \centering
    \includegraphics[width=0.75\linewidth]{chapters/chLTM3/figures/horizon_test_boxplot_stochastic.pdf}
    \caption[Planner performance with different planning horizons]{Cumulative reward obtained by each planner across different high-level planning horizons. Each configuration was run for 20 trials. \correction{We see that the stochastic planner outperforms the baseline at shorter planner horizons, and that the performance of \emph{both} planners deteriorates once the planning horizon becomes too long. This reflects the fact that in stochastic environments, there may not always be any benefit to longer planning horizons.}}
    \label{fig:horizon_experiment_stochastic}
\end{figure}

\begin{table}[]
    \centering
    \caption{Planner performance data in a stochastic environment with different planning horizons.}
    \label{tab:LTM3_horizon_expt}
    \begin{tabular}{@{}ccccc@{}}
        \toprule
        Planner                              & \begin{tabular}[c]{@{}c@{}}Planner\\horizon (days)\end{tabular} & \begin{tabular}[c]{@{}c@{}}Average\\ reward\end{tabular} & \begin{tabular}[c]{@{}c@{}}Computation time\\per step (s)\end{tabular} & \begin{tabular}[c]{@{}c@{}}Constraint \\ violations\end{tabular} \\ \midrule
        \multirow{4}{*}{\textsc{Stochastic}} & 1                                                               & 24.56                                                    & 15.8                                                                   & 1                                                                \\
                                             & 2                                                               & 25.67                                                    & 25.9                                                                   & 4                                                                \\
                                             & 5                                                               & 17.59                                                    & 47.6                                                                   & 6                                                                \\
                                             & 10                                                              & 16.22                                                    & 67.9                                                                   & 3                                                                \\ \midrule
        \multirow{4}{*}{\textsc{Baseline}}   & 1                                                               & 19.39                                                    & 6.7                                                                    & 18                                                               \\
                                             & 2                                                               & 15.50                                                    & 10.3                                                                   & 27                                                               \\
                                             & 5                                                               & 16.29                                                    & 15.3                                                                   & 14                                                               \\
                                             & 10                                                              & 16.09                                                    & 25.8                                                                   & 25                                                               \\ \bottomrule
    \end{tabular}
\end{table}


A first observation is that, compared with the deterministic domain results from the previous chapter (Figure~\ref{fig:LTM2_horizon_test}), we no longer observe a clear trend of increasing performance as the planner horizon increases.
%
This is likely because with the additional uncertainty introduced by the stochastic dynamics, there is no longer such a clear benefit to planning further ahead.
%
While it is possible that a larger number of MCTS trials (and experiment trials) might reveal some advantage of longer planning horizons, this would also come with a significant computation cost, and it is likely that any such advantage would be marginal.
%
We shall revisit this idea briefly in Section~\ref{sec:LTM3_discussion}.
%
%
Comparing the two algorithms, we see that the stochastic planner outperforms the baseline in terms of cumulative reward for planner horizons of 1--2 days.
%
For longer horizons, however, the two algorithms achieve similar rewards on average, with similar variability in performance.
%
However, the crucial difference is that the stochastic planner is able to achieve this performance with a much lower rate of constraint violations, as shown in Table~\ref{tab:LTM3_horizon_expt}.
%
On average, the baseline violates the constraints 6 times more frequently, indicating that the stochastic planner does provide a significant advantage even in the longer horizon cases, by obtaining a comparable reward to the baseline while planning much more cautiously and avoiding constraint violations.
%
The stochastic planner also requires 2--3 times more computation time per step, due to the increased computational overhead of computing action duration distributions.
% 
However, as shown in Table~\ref{tab:LTM3_horizon_expt}, planning times still remain within a feasible range for the experimental timescales we consider for long-term robot missions, where actions would typically be no shorter than 10 minutes.

\subsection{Environment stochasticity}
\label{ssec:LTM3_expts_stochasticity}

We now examine the performance of our stochastic planner across environments with different levels of uncertainty over action durations.
%
We refer to this uncertainty as the \emph{level of stochasticity} in the environment.
%
Similar to Section~\ref{ssec:LTM3_expts_horizon}, we use a $20 \times 20$ grid map with a randomly generated environment process consisting of moving point sources.
%
Here, we use a planning horizon of 2 days.
%
We vary the level of stochasticity in the environment, quantified by the average proportion of the expected cost of each edge that is stochastic.
%
For example, an environment stochasticity value of 0\% corresponds to the deterministic case, whereas 20\% means that on average across the environment, 20\% of the cost of each edge comes from the exponentially-distributed stochastic component.
%
In each (non-deterministic) case, we randomly sample the stochastic component for each edge uniformly from a range of $\pm$\qty{10}{\percent} around the average value.
%
This ensures that there is some variation in the level of stochasticity in different regions of the environment, allowing the planner to strategically trade off between paths with different levels of risk.
%
For example, a more risk-averse planner might prefer lower-uncertainty paths, whereas a risk-seeking one might attempt traversing high-uncertainty paths in order to obtain higher rewards.
%
The results of this experiment are shown in Figure~\ref{fig:stochasticity_experiment} and Table~\ref{table:stochasticity_expt}.

We see in Figure~\ref{fig:stochasticity_experiment} that the performance of the baseline planner degrades as the level of stochasticity in the environment increases.
%
This is as expected, since it only considers \emph{expected} action durations when planning, resulting in policies that fail to effectively adapt online to the stochastic dynamics.
%
Even in the deterministic environment, however, we see that the stochastic planner performs significantly better than the baseline.
%
In this scenario, the chance constraint reduces to a hard constraint, so the difference in performance is due to the high-level planner architectures---the baseline plans at the high level using the Depot-MDP introduced in Chapter~\ref{ch:LTM2}, whereas the stochastic planner uses MCTS over the high-level PKSMDP as described in Section~\ref{ssec:LTM3_high_level_planner}.
%
We see in Table~\ref{table:stochasticity_expt} that the MCTS approach achieves this performance advantage with no additional computational cost, since the advantage comes instead from focusing computation on the more relevant and promising areas of the search space.
%
Further, as the level of stochasticity increases, the average reward obtained by the stochastic planner actually \emph{increases}.
%
This is perhaps a little counterintuitive, since these environments are in a sense more challenging, and should require more cautious planning in order to satisfy the chance constraint.
%
However, it is possible that the higher reward is obtained because the planner is able to leverage the uncertainty over action durations to execute riskier behaviours, which can be exploited to obtain higher rewards in instances when actions execute faster than expected.

\begin{figure}
    \centering
    \includegraphics[width=0.75\linewidth]{chapters/chLTM3/figures/stochasticity_boxplot.pdf}
    \caption[Planner performance with different environment stochasticity levels]{Cumulative reward obtained by each planner for different levels of environment stochasticity. Each configuration was run for 10 trials. \correction{The stochastic planner consistently outperforms the baseline, most strongly in environments with higher stochasticity. As expected, planner performance in stochastic domains also shows higher variance than the deterministic domain results from previous chapters.}}
    \label{fig:stochasticity_experiment}
\end{figure}

% Please add the following required packages to your document preamble:
% \usepackage{multirow}
\begin{table}
    \centering
    \caption[Planner performance with different levels of environment stochasticity]{Planner performance data at different levels of environment stochasticity.}
    \label{table:stochasticity_expt}
    \begin{tabular}{ccccc}
        \hline
        Planner                              & \begin{tabular}[c]{@{}c@{}}Environment\\ stochasticity\end{tabular} & \begin{tabular}[c]{@{}c@{}}Average\\ reward\end{tabular} & \begin{tabular}[c]{@{}c@{}}Computation time\\ per step (s)\end{tabular} & \begin{tabular}[c]{@{}c@{}}Constraint \\ violations\end{tabular} \\ \hline
        \multirow{4}{*}{\textsc{Stochastic}} & 0.0                                                                 & 347.07                                                   & 7.78                                                                    & 0                                                                \\
                                             & 0.2                                                                 & 241.82                                                   & 25.85                                                                   & 0                                                                \\
                                             & 0.4                                                                 & 288.12                                                   & 25.91                                                                   & 1                                                                \\
                                             & 0.6                                                                 & 373.98                                                   & 24.89                                                                   & 1                                                                \\ \hline
        \multirow{4}{*}{\textsc{Baseline}}   & 0.0                                                                 & 230.52                                                   & 7.50                                                                    & 0                                                                \\
                                             & 0.2                                                                 & 191.41                                                   & 8.00                                                                    & 6                                                                \\
                                             & 0.4                                                                 & 201.89                                                   & 8.16                                                                    & 24                                                               \\
                                             & 0.6                                                                 & 185.42                                                   & 8.66                                                                    & 43                                                               \\ \hline
    \end{tabular}
\end{table}


Table~\ref{table:stochasticity_expt} also validates the ability of our planning approach to satisfy a chance constraint while maintaining high performance.
%
We see that even in the most challenging environment, the stochastic planner incurs very few constraint violations.
%
By contrast, the number of violations incurred by the baseline planner escalates rapidly as the level of stochasticity increases, since it does not explicitly account for uncertainty over action durations while planning.
%
The results show that the computation time per step of the stochastic planner remains within feasible bounds.
%
The computation time also remains similar for all three levels of stochasticity considered, since the reachability calculations have the same computational demand for any non-zero level of stochasticity.
%
However, it is possible that in some environments, more MCTS trials would be required in order to obtain reasonable planning performance.
%
In such cases, then, the computation time required to achieve good planning performance would indeed increase with the level of stochasticity.

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

In this chapter, we have extended the planning approach from Chapter~\ref{ch:LTM2} to address \challengeref{challenge:stochastic} by considering uncertainty over action durations and resource dynamics.
%
The experiments in Section~\ref{ssec:LTM3_expts_horizon} demonstrate that our planner is able to achieve performance comparable to the baseline from the previous chapter while enforcing a chance constraint over the resource level.
%
The previous approach relied on action pruning based on shortest path costs, which can be computed efficiently using algorithms such as Floyd--Warshall.
%
This approach does not extend directly to the stochastic setting, so we use a deterministic approximation (Section~\ref{ssec:checking_reachability}) to the shortest path to enable action pruning.
%
By doing so, we are able to ensure satisfaction of the chance constraint without the need for computationally prohibitive stochastic shortest path algorithms.
%
The results in Section~\ref{ssec:LTM3_expts_horizon} show that both the baseline planner and the stochastic planner struggle to plan effectively over long horizons, with performance degrading as the planning horizon increases.
%
This could likely be mitigated to a degree by increasing the number of MCTS trials, at the cost of additional computation.
%
However, planning over long horizons is fundamentally challenging when the outcomes of actions are uncertain, so it might also be  the case that longer planning horizons would not provide a significant benefit even in the limit of infinite computation.
%

We have also seen that the importance of explicitly considering stochasticity in environment dynamics is highly dependent on the level of stochasticity present.
%
The results in Section~\ref{ssec:LTM3_expts_stochasticity} show the stochastic planner outperforming the baseline in all environment configurations.
%
In the case of deterministic dynamics (i.e., when the environment stochasticity is 0), the performance gap is explained by the new high-level planner architecture.
%
Better performance is achieved by discretising the state space on-the-fly using MCTS with progressive widening, compared with the fixed discretisation used in the previous chapter.
%
In the stochastic environments, we see that the gap in performance between the planners is notably smaller when the level of stochasticity is low, and grows significantly as the variance in action durations increases.
%
This is consistent with intuition, indicating that in certain, relatively predictable, environments, good planning performance might be achieved with a deterministic model.
%
In such a case, a small level of uncertainty could be managed by simply using a deterministic model with slightly conservative action durations.
%
However, as the level of uncertainty increases, such approaches would either introduce significant inefficiencies into planning, or result in a high rate of constraint violations---we observe the latter in the results in Table~\ref{table:stochasticity_expt}.


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

In this chapter, we have extended the planner architecture from Chapter~\ref{ch:LTM2} to address \challengeref{challenge:stochastic}, by incorporating stochastic models of action durations and battery charging.
%
We model action durations using exponential distributions with deterministic delays, and integrate a realistic piecewise linear model of battery charging into our planner.
%
We further improve upon the high-level planning approach from the previous chapter, using MCTS to better handle planning over continuous spaces with uncertain action outcomes.
%
Our experiments demonstrate that our planner is able to achieve good performance while enforcing a chance constraint over the robot's resource level, even in environments with high degrees of stochasticity.
%
