\chapter{Background}
\label{ch:background}

\minitoc


In this chapter, we introduce the key concepts in environment representation, modelling, and planning which underpin the work in this thesis.

\section{Topological maps}
\label{sec:topological_maps}

This thesis addresses high-level decision making for applications in robotics.
%
To support effective planning, we represent the environments occupied by robots as \emph{topological maps}~\cite{kuipers1991robot}.
%
Topological maps represent environments compactly, as a discrete set of locations which are relevant to the planning problem at hand.
%
We plan over  topological maps, generating \emph{actions} which can then be passed to lower-level subsystems to manage navigation and control during execution.

\begin{definition}[Topological map]
    A topological map is a tuple $\tm = \langle \tmnodes, \tmedges \rangle$, where $\tmnodes$ is a finite set of nodes (also known as waypoints, or vertices) representing locations of interest in the environment, and $\tmedges \subseteq \tmnodes \times \tmnodes$ is a set of directed edges representing links between locations that can be traversed by a robot.
\end{definition}



A key component of the work in this thesis is \emph{spatiotemporal modelling}, which involves modelling a feature of the robot's environment as a continuous spatiotemporal process.
%
In particular, we employ  Gaussian processes for this, which are discussed in Section~\ref{sec:gaussian_processes}.
%
To support this, we explicitly associate each topological node $\tmnode \in \tmnodes$ with a location in the robot's physical environment, i.e. $\tmnode = (x, y) \in \mathbb{R}^2$.
%
This allows our planners to consider spatial relationships between the locations represented by topological nodes.
%
For example, if two nodes are close together, then we might expect that the observed values of environment features at those two nodes will be similar.


\begin{figure}
    \centering
    \includegraphics[width=0.8\textwidth]{chapters/chBackground/figures/tm-example.pdf}
    \caption[Topological map example]{An example of a topological map of a vineyard in Surrey, UK. Satellite imagery from \citep{usgs2020}.}
    \label{fig:topo_map_example}
\end{figure}



Figure~\ref{fig:topo_map_example} shows an example of a topological map of a vineyard, such as might be used for agricultural monitoring task.
%
In this example, nodes are placed at key locations across the different plots of land that comprise the vineyard.
%
These nodes are linked by edges, each of which indicates a link between the corresponding locations which can be traversed by a robot.
%
In this case, the edges are bidirectional, meaning that they can be traversed in either direction.


\section{Gaussian processes (GPs)}
\label{sec:gaussian_processes}

\subsection{Model overview}
\label{ssec:gp_overview}

A Gaussian process is a statistical model which defines a distribution over functions.
%
GPs have received significant attention in the machine learning literature, as they provide a flexible and non-parametric framework for modelling complex, unknown distributions from data~\citep{williams2006gaussian}.
%
Importantly for the work in this thesis, GPs provide \emph{probabilistic} predictions---that is, their outputs are probability distributions rather than point estimates.
%
This allows for explicit reasoning about the uncertainty of the model, which is crucial in robotics applications such as ours where the environment is only partially observable.


\begin{definition}[Gaussian process]
    A Gaussian process $\gp$ is a collection of random variables, of which any finite subset are jointly Gaussian distributed.
    %
    The GP is fully specified by its mean function $\gpmean(\gpstate)$ and its kernel function $\gpkernel(\gpstate, \gpstate')$, giving a distribution over functions $\gpobs(\gpstate) \sim \gp(\gpmean(\gpstate), \gpkernel(\gpstate, \gpstate'))$.
    %
    We can let $\gpmean(\gpstate)=0$ without loss of generality.
    %
    Given a dataset of $\gpnumpoints$ noisy observations $\gpdataset = \left\{ (\gpstate_i, \gpobs(\gpstate_i)+\gpobsnoise_i) \right\}_{i=1}^{\gpnumpoints}$ for states $\gpstate_i$, where $\gpobsnoise_i\sim\mathcal{N}(0, \gpvar^2)$ is Gaussian observation noise, GP regression predicts unknown environment feature values at  inputs $\gppointsquery$ based on visited states $\gppointsvisited$.
    %
    The kernel function $\gpkernel$ is parameterised by hyperparameters $\gphypers$.
    %
\end{definition}


The GP kernel function  captures information about the structure of the process $\processfunction$ being modelled by the GP.
%
Given hyperparameter priors $\gppriors(\gphypers)$, the values of $\gphypers$ can be learned by maximising the log marginal likelihood of the model given the dataset.
%
Alternatively, the values of $\gphypers$ can simply be set manually.
%
The choice of kernel function is a key design decision in GP applications, as it can be used to encode domain knowledge about $\processfunction$, which can in turn dramatically improve model accuracy.
%
To illustrate this, Figure~\ref{fig:gp_example} compares the predictions of GPs with two different kernels fit to the same dataset, which is sampled from an underlying periodic function.
%
The first uses a radial basis function~(RBF) kernel, which simply treats nearby states in the input space as similar.
%
The second uses a periodic kernel, which uses a periodic distance function to reflect periodicity expected in the data.
%
We see that if the kernel function is well-chosen, it can allow the GP predictions to generalise better across the input space, thereby producing more informative predictions.


\begin{figure}
    \centering
    \begin{subfigure}[b]{0.48\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chBackground/figures/gp_example_rbf.pdf}
        \caption{RBF kernel.}
        \label{sfig:gp_example_rbf}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.48\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chBackground/figures/gp_example_periodic.pdf}
        \caption{Periodic kernel.}
        \label{sfig:gp_example_periodic}
    \end{subfigure}
    \caption[Comparison of different GP kernels]{GPs with different kernels fit to the  same data. The curves show the GP posterior mean, and the shaded regions show 1--3 standard deviations of divergence from the mean.}
    \label{fig:gp_example}
\end{figure}



\subsection{Computational complexity}
\label{ssec:gp_complexity}

One of the primary limitations of GP models is their computational complexity.
%
For a GP with $\gpsize$ data points, the size of the kernel matrix is $\gpsize \times \gpsize$.
% 
Obtaining the predictive distribution at a new input point requires inverting this matrix, and as such exact GP inference has naive time complexity of $\bigO{\gpsize^3}$ and storage demand $\bigO{\gpsize^2}$~\cite{hensman2013gaussian}.
%
Techniques exist to speed up GP inference under certain conditions, which we discuss in Section~\ref{sec:relwork_GPs}.

\section{Markov decision processes (MDPs)}
\label{sec:MDPs}

The MDP~\cite{bellman1957markovian} is a mathematical framework for modelling decision making under uncertainty.
%
MDPs capture sequential interactions between a decision making agent and its environment, where the agent selects actions which in turn affect its state within that environment, in order to maximise some notion of reward.
%
MDPs are ubiquitous in robotics, and have been used in the literature to model a wide range of planning problems, including safe exploration~\cite{moldovan2012safe, turchetta2016safe,budd2020markov}, shared human-robot autonomy~\cite{fern2014decision, feng2016synthesis, costen2022shared}, informative path planning~\cite{singh2009nonmyopic, binney2012branch,lim2016adaptive},  and multi-robot coordination~\cite{street2020multi,claes2017decentralised,faruq2018simultaneous}.
%
Throughout this thesis, MDPs will be used as the underlying model of robots as decision making agents, and the environments in which they operate.
%
The following sections outline the key concepts and notation of MDPs, focusing on particular variants which are relevant to the work in this thesis.


\subsection{Finite horizon MDPs}

The finite horizon MDP is the basic model that forms the foundation of other, more specialised MDP models used throughout this thesis.
%
Variations on this model will be introduced in later chapters as needed.


\begin{definition}[Finite horizon MDP]
    \label{def:MDP}
    \sloppy % Allow a line break in the equation 
    A finite horizon MDP is a tuple  $\mdp = \langle \mdpstatespace, \mdpinitstate, \mdpactionspace, \mdptransition,  \mdprewardspace, \mdphorizon\rangle$, where $\mdpstatespace$ is a finite set of states,  $\mdpinitstate \in \mdpstatespace$ is the initial state; $\mdpactionspace$ is a finite set of actions; $\mdptransition: \mdpstatespace \times \mdpactionspace \times \mdpstatespace \rightarrow [0,1]$ is the transition function; $\mdprewardspace: \mdpstatespace \times \mdpactionspace \rightarrow \mathbb{R}$ is the reward function; and $\mdphorizon \in \mathbb{N}^+$ is the time horizon.
\end{definition}
%
% An optimal deterministic policy for $\mathcal{M}$ is a function $\pi:S \rightarrow A$ which maximises the sum of rewards up to horizon $H$.
In general, an agent's behaviour in an MDP is defined by a \emph{policy}.
%
A deterministic policy is a mapping $\mdppolicy: \mdpstatespace \times \{0, \dots, \mdphorizon\} \rightarrow \mdpactionspace$, where $\mdppolicy(\mdpstate_j, j) = \mdpaction$ specifies the action $\mdpaction$ to be executed at timestep $j$ from state  $\mdpstate_j$.
%
We denote the set of all such policies by $\mdppolicyset$.
%
% We let $\mdpstate_j$ denote the state at step $j$ of policy execution.
%
% Since we consider time $t$ as a component of the state, we let $\mdpstate_t$ denote the state at time $t$.
%
The standard MDP planning objective is to find a policy $\mdpoptimalpolicy$ which maximises the expected sum of rewards  up to the planning horizon $\mdphorizon$:
%
% Thus, if we let $N^{\mdphorizon}_{\mdppolicy}$ denote the number of steps taken by policy $\mdppolicy$ up to horizon $\mdphorizon$, the optimal policy is given by
%
\begin{equation}
    \label{eq:mdp_optimal_policy}
    \mdpoptimalpolicy = \argmax{\mdppolicy} \mathbb{E}^\mdppolicy\left[ \sum_{j=0}^{\mdphorizon-1} \mdprewardspace(\mdpstate_j, \mdppolicy(\mdpstate_j, j)) \right].
\end{equation}
%
MDPs and their variants can equivalently be formulated with a \emph{cost function} $\mdpcostfunc: \mdpstatespace \times \mdpactionspace \rightarrow \mathbb{R}$ in the place of the reward function.
%
In this case, the planning objective is to find a cost-minimising policy.

\subsection{Partially observable MDPs (POMDPs)}

POMDPs~\cite{kaelbling1998planning} extend the standard MDP framework to the case where the agent does not have full observability over its environment.
%
In robotics, partial observability often arises from robots' imperfect sensing capabilities, which prevent them from knowing with certainty their own location or pose within the environment.
%
This leads to the problem of \emph{state estimation}, which is a key area of robotics research~\cite{thrun2002probabilistic,barfoot2024state}.
%
In this thesis, however, we assume that robots have perfect observability over their \emph{internal} state (e.g. position, clock time, battery level), while the state of the environment can be observed only through noisy local measurements.


\begin{definition}[Partially observable MDP (POMDP)]
    \label{def:POMDP}
    A POMDP is a tuple $\pomdp = \langle \pomdpstatespace, \pomdpinitstate, \pomdpactionspace, \pomdptransition, \pomdprewardspace, \pomdpobservationspace, \pomdpobservationmodel, \pomdphorizon \rangle$, where $\pomdpstatespace$ is a finite set of states; $\pomdpinitstate$ is the initial state; $\pomdpactionspace$ is a finite set of actions;  $\pomdptransition: \pomdpstatespace \times \pomdpactionspace \times \pomdpstatespace \rightarrow [0,1]$ is the transition function; $\pomdprewardspace: \pomdpstatespace \times \pomdpactionspace \rightarrow \mathbb{R}$ is the reward function; $\pomdpobservationspace$ is the observation space; $\pomdpobservationmodel: \pomdpstatespace \times \pomdpactionspace \times \pomdpstatespace \rightarrow [0,1]$ is the observation model; and $\pomdphorizon \in \mathbb{R}^+$ is the time horizon.
\end{definition}

Compared with the standard MDP, the POMDP additionally includes the observation space $\pomdpobservationspace$ and the observation model $\pomdpobservationmodel$.
%
After executing an action, the agent receives an observation $o \in \pomdpobservationspace$ according to the observation model $\pomdpobservationmodel$.
%
Since the agent no longer has direct access to the true state of the environment, it must instead maintain a \emph{belief} over this state based on the observations received.
%
Thus, unlike in the MDP, where a policy can map directly from state to action, POMDP policies map from beliefs (or equivalently, histories) to actions.

While the work in this thesis does not explicitly formulate planning problems as POMDPs, we do consider models with partial observability.
%
As such, the algorithms we develop are informed significantly by the literature on POMDP planning, which we discuss in Section~\ref{sec:relwork_planning}.


\subsection{Partially known state MDPs (PKSMDPs)}
\label{ssec:bkg_PKSMDP}

This thesis addresses robot planning problems which are concerned with \emph{environment processes} that are unknown \emph{a priori}.
%
We consider robots operating within bounded environments $\environment \subset \mathbb{R}^n$, within which they are able to navigate and take local observations of these processes using on-board sensors.
%
These processes represent environment phenomena which vary spatially throughout the environment, and may also vary temporally, such as radiation levels in a nuclear inspection scenario, or acoustic bioactivity markers in coral reef monitoring.
%
The data from local observations can be used to build a model of the environmental processes, which in turn enables inferences about unvisited states for the purpose of planning.




\begin{definition}[Unknown processes]
    \label{def:unknown_process}
    Unknown processes in an environment $\environment$ are defined as a function $\processfunction: \environment \rightarrow \processobsspace$, where $\processobsspace = \mathbb{R}^m$ is the observation space of $\processfunction$, with  $m$ being the number of modelled unknown processes.
    %
    A robot can observe noisy sensor measurement $\processobs: \environment \rightarrow \processobsspace$ of the form:
    %
    \begin{equation}
        \processobs(\environmentstate) = \processfunction(\environmentstate) + \processnoise,
    \end{equation}
    %
    where $\processnoise=[\processnoise_1, \hdots, \processnoise_m]$ is an $m$-dimensional vector of Gaussian observation noise, i.e. $\epsilon_j \sim \mathcal{N}(0, \sigma^2_j)$ for all $j \in \{1, \hdots, m\}$.

\end{definition}

Throughout this thesis, we will address the case where $m=1$, i.e. that of a single unknown process.
%
However, the methods proposed can generalise fairly straightforwardly to  more than one unknown process.
%
Multiple correlated processes could be modelled using a multi-output GP~\citep{osborne2008towards}, or independent processes could be modelled simply using multiple single-output GPs.
%
The former assumes non-independent process dynamics, where learning about one process could improve predictions of another.
%
The reward function could then be reformulated as a scalar function of multiple variables, in order to retain a single-objective problem---we do not address multi-objective planning in this thesis.

We also consider some components of the state, such as location and time, to be known.
%
In order to clearly separate the known robot dynamics from the unknown  behaviour of the environment, we represent the system as a partially known state MDP~(PKSMDP), a model introduced by~\citet{budd2020markov,budd2023bayesian} and formalised by \citet{stephens2024auro}.

\begin{definition}[Partially known state MDP (PKSMDP)]
    \label{def:PKSMDP}
    A  PKSMDP is a tuple  $\pksmdp = \langle \pksmdpstatespace, \pksmdpinitstate, \pksmdpactionspace, \pksmdptransition,  \pksmdprewardspace, \pksmdphorizon\rangle$, where $\pksmdpstatespace = \pksmdpstatespaceknown \times \pksmdpstatespaceest$ is  a factored state space consisting of a known component $\pksmdpstatespaceknown$ and an unknown component $\pksmdpstatespaceest$;  $\pksmdptransition: (\pksmdpstatespaceknown \times \pksmdpstatespaceest) \times \pksmdpactionspace \times \pksmdpstatespaceknown \rightarrow [0, 1]$ is the transition function; and $\pksmdpinitstate$, $\pksmdpactionspace$, $\pksmdprewardspace$, and $\pksmdphorizon$ are as in a standard MDP (Definition~\ref{def:MDP}).
\end{definition}

The definition of a PKSMDP is similar to that of an MDP, with the exception of the factored state space.
%
In this thesis, the known component $\pksmdpstatespaceknown$ is used to capture the robot's internal  state (e.g. its location or resource level), while the unknown component $\pksmdpstatespaceest$ represents an environment process, which is defined by an underlying (unknown) function $\processfunction:\pksmdpstatespaceknown \rightarrow \pksmdpstatespaceest$.
%
We assume $\processfunction$ to be continuous.
%
% Typically, $\processfunction$ will not depend on internal components of the robot state in $S_k$, such as its resource level.
%
Because $\processfunction$ is unknown but the value of $\processfunction(\pksmdpstateknown)$ is uniquely defined, the transition function of the PKSMDP is not a complete transition function, in the sense that it only maps to known state components.
%
$\pksmdptransition((\pksmdpstateknown,\pksmdpstateest), \pksmdpaction, \pksmdpstateknown')$ is the probability of moving to $\pksmdpstateknown'$ given that $\pksmdpaction$ was executed in state~$\pksmdpstateknown$ and the value of the environment process was $\pksmdpstateest$.
%
%
This formulation allows for transition dynamics that depend on the unknown state component $\pksmdpstatespaceest$, such as in the case of an underwater robot operating in the presence of unknown currents.
%
Furthermore, the reward function $\pksmdprewardspace$ depends on the full state $\pksmdpstatespace$, and thus considers the unknown state component.

We can also consider PKSMDPs with deterministic transitions, where we instead have $\pksmdptransition: (\pksmdpstatespaceknown \times \pksmdpstatespaceest) \times \pksmdpactionspace \rightarrow \pksmdpstatespaceknown$.
%
In Chapters \ref{ch:LTM1} and \ref{ch:LTM2} we make use of this determinstic formulation, before extending to a stochastic setting in Chapter~\ref{ch:LTM3}.


\section{Monte Carlo tree search (MCTS)}
\label{sec:MCTS}

MDPs with finite state and action spaces can in principle be solved optimally using dynamic programming methods~\cite{bellman1956dynamic}.
%
However, optimal solution techniques do not scale to large problems or continuous state spaces, so in practice heuristics or sampling-based methods are often used.
%
In this thesis, we use MCTS~\cite{kocsis2006bandit} to plan in belief space over long horizons.

\subsection{Fundamentals}

MCTS methods incrementally build a search tree $\mctstree$ over a series of Monte Carlo simulations, which we refer to as \emph{trials}.
%
In non-deterministic settings, the tree is composed alternately of two types of nodes: \emph{decision nodes} $\mctsnode(\mctsstate)$, which represent states, and \emph{chance nodes} $\mctsnode(\mctsstate, \mctsaction)$, which represent action choices with stochastic outcomes.
%
Each node stores a count $\mctscount(\mctsstate)$ or $\mctscount(\mctsstate, \mctsaction)$ of the number of times it has been visited during simulation, as well as a state-value estimate $\mctsstatevalue(\mctsstate)$ for decision nodes and an action-value estimate $\mctsvalue(\mctsstate, \mctsaction)$ for chance nodes.
%
The tree is initialised with a single decision node, the root node, representing the current state of the system.
%
Each trial then consists of four stages: \emph{selection}, \emph{expansion}, \emph{simulation}, and \emph{backpropagation}.
%
The algorithm summarised visually in Figure~\ref{fig:mcts_explanation}.


\begin{figure}
    \centering
    \begin{subfigure}[b]{0.4\linewidth} % 0.48 for max width
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chBackground/figures/MCTS-1.pdf}
        \caption{Selection.}
        \label{sfig:MCTS-selection}
    \end{subfigure}
    % \hfill
    \begin{subfigure}[b]{0.4\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chBackground/figures/MCTS-2.pdf}
        \caption{Expansion.}
        \label{sfig:MCTS-expansion}
    \end{subfigure}
    % \hfill
    \begin{subfigure}[b]{0.4\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chBackground/figures/MCTS-3.pdf}
        \caption{Rollout.}
        \label{sfig:MCTS-rollout}
    \end{subfigure}
    % \hfill
    \begin{subfigure}[b]{0.4\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chBackground/figures/MCTS-4.pdf}
        \caption{Backpropagation.}
        \label{sfig:MCTS-backprop}
    \end{subfigure}
    \caption[MCTS algorithm illustration]{An illustration of the four phases of an MCTS trial. Blue circles are decision nodes, orange squares are chance nodes.}
    \label{fig:mcts_explanation}
\end{figure}



In the selection phase, actions are chosen according to a \emph{search policy}, and states are sampled from the transition model to traverse down the tree until a state is reached which is not in $\mctstree$.
%
We use the Polynomial Upper Confidence Tree~(PUCT) policy~\cite{auger2013continuous} as our search policy, which balances the average value of an action across previous trials with an exploration term that favours less-simulated actions:
%
\begin{equation}
    \label{eq:puct}
    \mctspuctvalue(\mctsstate, \mctsaction)
    =
    \mctsaveragevalue(\mctsstate, \mctsaction) + C\sqrt{\frac{\mctscount(\mctsstate)^\mctsparampuct}{\mctscount(\mctsstate, \mctsaction)}},
\end{equation}
%
where $\mctsaveragevalue(\mctsstate, \mctsaction)$ is the average reward obtained by choosing action $\mctsaction$ from state $\mctsstate$ in previous trials; $\mctscount(\mctsstate)$ is the number of times that node $\mctsstate$ has been visited; $\mctscount(\mctsstate, \mctsaction)$ is the number of times that action $\mctsaction$ has been selected from node $\mctsstate$; $C$ is a constant that affects the exploration-exploitation balance; and $\mctsparampuct$ is a depth-dependent parameter as per \citet{auger2013continuous}.
%
\correction{This approach guides exploration during MCTS towards more promising actions, resulting in fewer wasted simulations and thus more efficient planning.}



%
A new node is then added to $\mctstree$ (expansion).
%
If this node is not a terminal state, its value is estimated by simulating forwards up to a horizon $\mctshorizon$ (or, until a terminal state is reached) using a \emph{rollout policy} (simulation).
%
In many MCTS implementations, a random rollout policy is used, which simply samples actions uniformly at random.
%
The value of the new node estimated by the rollout is then backpropagated up the tree, updating the statistics of all nodes visited during the trial.
%
Finally, once trials are completed---either after a fixed number of iterations, or when a time limit is reached---an action is selected based on the statistics of the root node.
%




\subsection{Progressive widening}
\label{ssec:progwiden}

In problems involving continuous state, action, or observation spaces, the standard MCTS algorithm will produce a shallow tree of only one layer, since the outcome of any action will be unique and so the simulation step will never visit the same node twice~\cite{sunberg2018online}.
%
The \emph{progressive widening} approach from \citet{couetoux2011continuous} solves this problem by limiting the number of children of each node based on their visit counts, thereby ensuring that the tree remains balanced.

In this thesis, we consider discrete action spaces, but continuous state and observation spaces.
%
As such, actions are guaranteed to have unique outcomes each time they are executed, so we use progressive widening during the MCTS trials to limit the width of the tree.
%
We parameterise our progressive widening approach by a depth-dependent parameter $\alpha_d$ as per \citet{auger2013continuous}.
%
During the selection phase at node $\mctsnode(\mctsstate, \mctsaction)$, if  $\left\lfloor \mctscount(\mctsstate, \mctsaction)^{\alpha_d} \right\rfloor = \left\lfloor (\mctscount(\mctsstate, \mctsaction) - 1)^{\alpha_d} \right\rfloor$, then the successor state $s'$ is randomly sampled from the existing children of $\mctsnode(\mctsstate, \mctsaction)$; otherwise, a new node is generated by sampling from the relevant transition and observation models.


\section{Modelling stochastic processes}

Temporal uncertainty is an important consideration for planning in many robotics applications.
%
In Chapter~\ref{ch:LTM3}, we tackle the challenge of managing uncertainty over action durations in the context of planning for long-term robot monitoring missions.
%
Here, we introduce some of the tools used to model stochastic action durations.

\subsection{Continuous-time Markov chains (CTMCs)}

CTMCs~\cite{norris1998markov} are stochastic processes in which continuous-time transitions between states are governed by exponential distributions.

\begin{definition}[Continuous-time Markov chain (CTMC)]
    \label{def:CTMC}
    A CTMC is a tuple $\ctmc = \langle \ctmcstates, \ctmcinitstate, \ctmcrates \rangle$, where $\ctmcstates$ is a finite set of states, $\ctmcinitstate: \ctmcstates \rightarrow [0,1]$ is the initial state distribution, $\ctmcrates: \ctmcstates \times \ctmcstates \rightarrow \mathbb{R}_{\geq 0}$ is the rate transition function.
\end{definition}

For a given pair of states $\ctmcstate_i$ and $\ctmcstate_j$, $\ctmcrates(\ctmcstate_i,\ctmcstate_j)$ is the rate parameter for the exponential distribution describing the transition between those states.
%
The probability that the transition takes place within time $t$ is then given by $1 - e^{-\ctmcrates(\ctmcstate_i,\ctmcstate_j)t}$.
%

\subsection{Phase-type distributions (PTDs)}
\label{ssec:PTDs}

\emph{Phase-type distributions} describe the time taken for a CTMC to reach an absorbing state.
%
\begin{definition}[Phase-type distribution (PTD)]
    \label{def:PTD}
    % 
    A phase-type distribution is a tuple $\mathcal{P} = \langle S, \mathit{init}, \delta_E, s^a \rangle$, where $S$, $\mathit{init}$, and $\delta_E$ are as in a CTMC, and $s^a\in S$ is the single absorbing state, with $\mathit{init}(s^a) = 0$.
\end{definition}
%
We refer to the non-absorbing states in the PTD as \emph{transient states}.
%
The PTD can be represented in matrix form $\ptd = \langle \ptdinitialdist, \ptdtransitions  \rangle$, where $\ptdinitialdist$ is a vector containing the initial state probabilities, and $\ptdtransitions$ is a transition matrix between transient states, given by
%
\begin{equation}
    \ptdtransitions =\begin{cases}
        \delta(s,s')                   & \text{if $s\neq s'$ and $s,s' \neq s^a$} \\
        \sum_{s''\neq s} \delta(s,s'') & \text{if $s=s'$ and  $s \neq s^a$}.      \\
    \end{cases}
\end{equation}


The probability density function and cumulative density function for a continuous PTD are given respectively by:
%
\begin{equation}
    \label{eq:PTD_distribution_functions}
    f(x) = \ptdinitialdist e^{\ptdtransitions x}\ptdabsrates,
    \qquad
    F(x) = 1 - \ptdinitialdist e^{\ptdtransitions x}\vec{1},
\end{equation}
%
where $\vec{1}$ is a vector of ones, and $\ptdabsrates = - \ptdtransitions\vec{1}$ captures the transition rates to the absorbing state $s^f$.
%
In Chapter~\ref{ch:LTM3}, we use PTDs to model the time taken for a robot to complete sequences of actions with stochastic durations.

% A chain of $n$ events governed by exponentially-distributed transitions $(\lambda_1, \dots, \lambda_n)$ form a special case of the phase-type distribution known as the \emph{hypoexponential} distribution.
% %
% In this case, considering only the stochastic component of action durations, we have

% \begin{equation}
%     \begin{split}
%         {\ptdtransitions}_\mathrm{chain}  & =
%         \begin{bmatrix}
%             -\lambda_1 & \lambda_1  & \dots  & 0              & 0             \\
%             0          & -\lambda_2 & \dots  & 0              & 0             \\
%             \vdots     & \vdots     & \ddots & \vdots         & \vdots        \\
%             0          & 0          & \dots  & -\lambda_{n-1} & \lambda_{n-1} \\
%             0          & 0          & \dots  & 0              & -\lambda_n
%         \end{bmatrix} \\
%         \ptdinitialdist_\mathrm{chain} & =
%         \begin{bmatrix}
%             1 & \dots & \dots & \dots & 0
%         \end{bmatrix}^T.
%     \end{split}
% \end{equation}