\chapter{Hierarchical Planning for Resource-Constrained Long-Term Monitoring}
% \chaptermark{Hierarchical Planning for Resource-Constrained Missions}
\label{ch:LTM2}

\minitoc


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

In Chapter~\ref{ch:LTM1}, we considered the long-term monitoring problem as a sequence of shorter missions.
%
This addressed  the common scenario in which robots rely on human assistance for resource management tasks such as recharging batteries or offloading data.
%
However, as robot technology improves, it is becoming increasingly feasible for robots to manage their resources independently.
%
Given the appropriate infrastructure, robots can dock autonomously to recharge their batteries or offload data.
%
While this does introduce additional requirements to the mission, in both the robot hardware and the infrastructure, it also comes with two key advantages.
%
The first is that autonomous resource management can remove the need for regular human intervention, thereby reducing the running costs of the mission.
%
The second, more interestingly from a planning perspective, is that the flexibility for a robot to manage when and where to recharge its resources can lead to better mission outcomes.
%
Moreover, introducing multiple recharging locations can greatly expand the area that is accessible to a single robot, in much the same way that charging networks extend the moving range of electric vehicles~\cite{lam2014electric}.


\begin{figure}[]
    \centering
    \includegraphics[width=0.8\linewidth]{chapters/chLTM2/figures/wildfire-domain-bare.png}
    \caption[Wildfire monitoring dataset visualisation]{The progression of a wildfire in the Kosciuszko National Park in Australia. Yellow-red markers are wildfire hotspots detected via satellite over a period of 20 days, coloured by time of detection to show the evolution of the fires. Blue waypoints indicate weather stations where a monitoring UAV can recharge its batteries. \correction{Satellite imagery from }\cite{stockli2005blue}.}
    \label{fig:wildfire-domain-bare}
\end{figure}

In this chapter, we therefore turn our attention to \challengeref{challenge:resources}, and consider \emph{continuous} long-term deployments in which the robot must manage its own finite resources.
%
The mission objective is as before: to maximise the cumulative value of observations of an environment process over a long horizon.
%
The robot has a constrained resource, such as battery life or available on-board memory, which depletes steadily while it is active.
%
The robot can spend time at a \emph{depot} to replenish this resource.
%
Figure~\ref{fig:wildfire-domain-bare} depicts an application domain in wildfire monitoring, where an unmanned aerial vehicle~(UAV) can be used to provide real-time observations of areas where the fires are most severe.

% Over the course of the mission, the robot must build a model of the environment process from  local observations, which it can then exploit to focus on areas which are expected to yield higher reward.
% %
% Throughout the mission, the robot must also manage its finite resources in such a way that produces the best mission outcome.

% The long-term setting presents challenges in modelling and adapting to  dynamic environments, as well as using these model to plan over long horizons. 
%
% Resource constraints introduce further complexity, where the robot must manage replenishment of its resources -- such as battery capacity or data storage space -- by visiting 

% Image citation
% https://earthobservatory.nasa.gov/images/86163/exploring-reefs-from-space




% We consider missions motivated by ecological monitoring, in which a robot might be deployed to monitor a large-scale outdoor environment over a period of weeks, months, or even years.
% %
% Such environments are often dynamic over multiple timescales, typically exhibiting some daily cyclic patterns combined with slower (e.g. seasonal) variation. 
%
% Our work takes inspiration from ecological domains and applications, from mapping and monitoring of coral reefs~\cite{flaspohler2019information,mccammon2022adaptive}, to crop monitoring~\cite{dong20174d} and wildfire prevention~\cite{couceiro2019semfire}. % Other crop monitoring citation \cite{fountas2020agricultural}
%
% Figure~\ref{fig:example} shows an example of a domain that could be used for unmanned aerial vehicle~(UAV) mission to monitor coral reef activity, set around the Fijian island of Vanua Levu.



% In this chapter, we pose the monitoring problem as a goal of maximising the cumulative value of observations of some environment feature over a period of weeks or months. 
% 
% Since the robot has limited prior knowledge of this feature, we use a spatiotemporal Gaussian process~(GP) to model it.
%
% This provides a convenient way to construct a model from sparse observational data, which can also be specialised to particular applications to improve model accuracy if domain expertise is available.
%


There are three key challenges when it comes to planning in this setting.
%
First, the robot must build and maintain an accurate probabilistic model of the environment from sparse, noisy, local observational data (\challengeref{challenge:modelling}).
%
This was a focus of Chapter~\ref{ch:LTM1}, where we demonstrated that our spatiotemporal GP model provided an effective modelling tool in this context.
%
Second, the robot must then leverage this model to plan in a long-term manner, balancing short-term reward-seeking with exploration that may benefit later stages of the mission.
%
In Chapter~\ref{ch:LTM1}, we considered planning horizons as long as only a single resource cycle---here, we look to extend this to multiple cycles, enabling effective planning in much larger environments.
%
Finally, the robot must manage its constrained resources, incorporating resource replenishment into its schedule in order to achieve the best overall performance (\challengeref{challenge:resources}).
%
At its most basic level, this final challenge can be handled simply by ensuring that the robot returns to a base periodically to replenish its resources.
%
However, as we shall see in this chapter, there can be significant benefits to a more flexible approach to resource management.
%
%In the wildfire monitoring scenario in Figure~\ref{fig:wildfire-domain-bare}, for example, we will show that an adaptive approach to deciding \emph{when} and \emph{where} to charge can unlock better overall performance. 
%

Our contribution in this chapter is a hierarchical planning framework for long-term robot monitoring of an unknown environment process under resource constraints.
%
This is a direct extension to the work presented in Chapter~\ref{ch:LTM1}.
%
We introduce a more flexible model for resource management, in which the robot must periodically plan to visit depots to replenish  its resources.
%
We then adopt a hierarchical planning approach to enable true long-term planning over multiple resource cycles.
%
In this problem formulation, resource management is a key component of the planning problem---the robot must decide \emph{when} and \emph{where} to replenish resources in order to maximise the reward obtained while active.
%
To the best of our knowledge, this work is the first to consider long-term monitoring of an unknown environment process with resource management integrated into planning, and the first to tackle planning over a GP-modelled process with a hierarchical approach.
%
This combination of elements yields a challenging problem, since the hierarchy introduces the need to extract information from the model at  multiple levels of abstraction, and the resource constraints influence the exploration-exploitation trade-off available to the planning agent.
%
We show that our approach can leverage the GP model to intelligently manage the resource constraints and plan over long horizons, and demonstrate the benefits of doing so through a series of experiments in synthetic domains and a wildfire monitoring application.
%
The work in this chapter first appeared in~\cite{stephens2024hierarchical}, presented at ECAI 2024.



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

Similar to Chapter~\ref{ch:LTM1}, we consider a mobile robot  deployed in a physical environment represented as a topological map $\tm = \langle \tmnodes, \tmedges \rangle$.
%
Now, the robot has some finite resource, which it consumes as it navigates through the environment (for example, battery charge).
%
This resource can be replenished at a set of \emph{depots} $\tmdepots \subseteq \tmnodes$, which we assume to represent a small number of locations within the full topological graph.
%
As in the previous chapter, we consider the navigation and resource dynamics to be \emph{deterministic}, with navigation described by $\tm$.
%
That is, any action taken by the robot will result in a known state transition: the action duration, resulting state, and resource consumption are all known in advance.
%
In Chapter~\ref{ch:LTM3}, we will relax some of these assumptions and consider actions with stochastic outcomes.

While active,  the robot's resource depletes at a constant rate $\ratedischarge$, and while replenishing it increases at a constant rate $\ratecharge$.
%
The continuous resource level $b \in [0,1]$ represents the battery level of the robot, with $b=0$ corresponding to an empty battery, and $b=1$ a full charge.
%
Any non-depot state where $b=0$ is a sink state.
%
As previously, we consider  an \emph{a priori} unknown spatiotemporal mapping $\processfunction:\mathbb{R}^3 \rightarrow \mathbb{R}$, where $\processfunction(x,y,t)$ is the value of an environment feature of interest at location $(x,y)$ and time $t$.
%
The mission goal is to maximise the cumulative reward from observations taken of $\processfunction$ across a long horizon $\pksmdphorizon$ which corresponds to many days.
%
We model this problem as a \emph{\algfull{}}.

\begin{definition}[\algfull{}~(\algshort{})]
    \label{def:LTM_PKSMDP}
    A \algfull{} is  a tuple  $\mainmodelsymbol = \langle \pksmdpstatespace, \pksmdpinitstate, \pksmdpactionspace, \pksmdptransition, \pksmdprewardspace, \pksmdphorizon\rangle$ with $\pksmdpstatespace = \pksmdpstatespaceknown \times \pksmdpstatespaceest$, where $\pksmdpstatespaceknown=\{(x,y,t,b) \in \mathbb{R}^3 \times [0,1] \mid (x,y) \in \tmnodes \textrm{ and } 0 \leq t \leq \pksmdphorizon\}$ is the known state component; $\pksmdpstatespaceest=\mathbb{R}$ is the unknown state component; $\pksmdpinitstate =(x_0,y_0,0,1, \processfunction(x_0,y_0,0))$ is the initial state, with $(x_0,y_0) \in \tmnodes$ being the initial location; $\pksmdpactionspace = \tmedges \cup \{\actioncharge\}$ is the action space; $\pksmdptransition: (\pksmdpstatespaceknown \times \pksmdpstatespaceest) \times \pksmdpactionspace \times \pksmdpstatespaceknown \rightarrow [0, 1]$ is the transition function, which evolves the state according to the topological map and resource dynamics, depending on which action is selected;  $\pksmdprewardspace: \pksmdpstatespace \times \pksmdpactionspace \rightarrow \mathbb{R}$ is a reward function  of the environment process $\processfunction$; and $\pksmdphorizon$ is the mission horizon.
\end{definition}

As in the previous chapter, we take the reward function to be the value of the unknown process, i.e., $\pksmdprewardspace(\pksmdpstateknown, \processfunction(\pksmdpstateknown)) = \processfunction(\pksmdpstateknown)$.



%
%This allows us to intuitively represent the robot's belief over $\processfunction$ using a GP, which progressively incorporates new observations to refine the belief over the course of the missions.
% This  in turn forms the basis of the MCTS planning algorithm presented in the following section.
%


% For the remainder of this paper, based on our motivating setting of ecological monitoring, we consider the missions to be \emph{daily}, such that the multi-mission problem described by $\mathcal{M}^+$ spans $|H|$ consecutive days.
%
%For the remainder of this paper, we assume for notational simplicity that $\processfunction$ models a single state feature only, although the approach can easily generalise to multiple unknown state features given an appropriate reward function. 


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

\subsection{Overview}

The planning problem described above presents challenges through the computational demands of planning under uncertainty at scale, over large maps and long mission horizons, as well as management of the limited resources.
%
In missions such as the UAV wildfire monitoring one depicted in  Figure~\ref{fig:wildfire-domain-bare}, effective exploration and continued monitoring of the environment requires some degree of \emph{long-term} planning---where long-term, in this case,  means spanning many resource depletion cycles.
%
This is necessary because the UAV cannot traverse the whole environment in a single battery charge, so in order to plan at the scale of the full environment, it must plan over multiple resource cycles.
%
Plans must incorporate periodic visits to depots in order to ensure that the UAV's resources do not run out mid-flight, while still serving the overall mission goal.
%
However, as discussed in Section~\ref{ssec:relwork_partial_observability}, planning in belief space over long sequences of actions is extremely challenging, due to the large search space.
%
We therefore take a hierarchical approach to planning, which introduces some abstraction between different components of the problem.
%
Our planner uses a two-level hierarchy, which is summarised in Table~\ref{table:planner_hierarchy}.


\begin{table}
    \centering
    \caption{Division of responsibilities between the high-level and low-level planner.}
    \label{table:planner_hierarchy}
    \begin{tabular}{@{}lcc@{}}
        \toprule
                         & Low-level planner     & High-level planner       \\ \midrule
        Planning horizon & Single resource cycle & Multiple resource cycles \\
        State space      & Full topological map  & Depots only              \\
        Resource-aware   & No                    & Yes                      \\
        Belief-aware     & Yes                   & No                       \\ \bottomrule
    \end{tabular}
\end{table}


The \emph{high-level planner} is responsible for long-term planning and resource management.
%
It plans over a horizon of multiple resource cycles, using a simplified model of the physical environment which considers \emph{only} depot locations in its state space.
%
Policies generated by the high-level planner specify \emph{high-level actions}.
%
These can either be resource replenishment actions, or navigation actions with depots as destinations, in each case with an associated duration.
%
Resource replenishment actions are primitive, and can be executed directly.
%
Navigation actions are macro actions, specifying a destination depot and an action duration---these are passed down to the \emph{low-level planner}, which plans the specific sequence of actions to take in order to reach the destination in time.


The low-level planner does not need to directly consider resource management, as this is  already captured by the high-level action choice.
%
It plans over a shorter horizon, which is at most the time taken to deplete the robot's resources once, allowing for more fine-grained reasoning about beliefs over the environment feature.
%
Once a high-level action is executed (either directly, or by delegation to the low-level planner), a new high-level plan is generated to get the next action.
%
This process repeats until the mission is completed (i.e., no more valid high-level actions can be executed within the mission horizon).
%
Figure~\ref{fig:architecture} depicts our hierarchical planning architecture, and we describe the components in detail below.


\begin{figure}
    \centering
    \includegraphics[width=0.7\linewidth]{chapters/chLTM2/figures/alg_diagram.pdf}
    \caption[Hierarchical planner architecture]{Hierarchical planner architecture.}
    \label{fig:architecture}
\end{figure}


\subsection{High-level planning: \highlevelmdp{}}
\label{ssec:LTM2_high_level_planner}

The high-level planner builds a simplified representation of the full planning problem, which we refer to as a \emph{\highlevelmdp{}}.
%
The \highlevelmdp{}  considers \emph{only} depot locations, as it is used to plan the sequence of depots that the robot should visit, and not the specific navigation actions required to reach them.
%
It uses a discrete representation of time and the resource level, with step values $\timestep$ and $\batterystep$ respectively.
%
We denote the maximum discrete resource level by $\maxbatterydiscrete = \lfloor 1 / \batterystep\rfloor$.
%
The time step $\timestep$ can be much larger than the timescale of individual navigation actions, since the high-level planner is not responsible for decisions at this timescale.
%
It must, however, be no larger than the minimum amount of time required to fully drain or replenish the robot's resources, i.e. $\max(\ratecharge, \ratedischarge) \timestep \leq \maxbatterydiscrete$.

%
%
% Solving the \highlevelmdp{} generates a policy of \emph{high-level actions}, which are either (a) traversal actions, specifying the depot to move to next and the duration within which to reach it; or (b) resource replenishment actions, specifying a duration over which to execute the action at the current depot.
%
% Resource replenishment actions are primitive and can be executed directly. 
%
% Traversal actions from the high-level planner are treated as constraints for the low-level planner described in the following section, which plans online to execute them over a series of primitive traversal actions.
%
% The \highlevelmdp{} is formalised in Definition~\ref{def:high-level} below.



We now present a formal definition of the \highlevelmdp{}.

\begin{definition}[\highlevelmdp{}]
    For a given \algshort{} $\pksmdp$, planning horizon $\hmdphorizon$, timestep $\timestep$, and resource step $\Delta_b$, the corresponding \highlevelmdp{} is given by $\hmdp = \langle \hmdpstates, \hmdpinitstate, \hmdpactions, \hmdptransitions, \hmdprewards, \hmdphorizon \rangle$, with each component defined as below.
\end{definition}


\paragraph*{State space and planning horizon}
%
$\hmdpstates = \tmdepots \times \hmdptimes \times \hmdpbatteries$ is the discrete state space of the \highlevelmdp{}, where $D$ is the set of depots, $\hmdptimes = [0, \dots, \hmdphorizon]$ is the discrete time up to horizon $\hmdphorizon$, and $\hmdpbatteries = [0, \dots, \maxbatterydiscrete]$ is the discrete resource level.
%
The initial state $\hmdpinitstate \in \hmdpstates$ corresponds to the initial state $\pksmdpinitstate$ in the full PKSMDP.

\paragraph*{Action space}
%
$\hmdpactions$ is the discrete action space of the \highlevelmdp{}, which consists of resource replenishment actions and movement actions.
%
\actionreplenish{} actions are available at any $d \in D$, with durations in the range $[1, \dots, \lfloor1/(\ratecharge\timestep)\rfloor]$.
%
At the start of each mission, the shortest path durations between each pair of depots are precomputed, using the Floyd--Warshall algorithm~\cite{cormen2022introduction} or similar.
%
Then, for each $\{d_1, d_2 \in D \mid \textsc{ShortestPath}(d_1,d_2) \leq 1 / \ratedischarge \}$, two movement actions are defined: a \actiontraverse{} action $a_{\text{tr}}(d_1, d_2)$ has duration equal to the \emph{minimum} number of $\timestep$ timesteps required for the journey, so $\dur{a_{\text{tr}}(d_1, d_2)}=\lceil \textsc{ShortestPath}(d_1,d_2) / \timestep \rceil$; and an \actionexplore{} action $a_{\text{ex}}(d_1, d_2)$ with duration equal to the \emph{maximum} number of such steps within a single battery charge, so $\dur{a_{\text{ex}}(d_1, d_2)} = \lfloor 1/(\ratedischarge\timestep)\rfloor$.


\paragraph*{Transitions}
%
$\hmdptransitions: \hmdpstates \times \hmdpactions \rightarrow \hmdpstates$ is a deterministic transition function which specifies the outcome of taking an action $\hmdpaction \in \hmdpactions$ from state $\hmdpstate \in \hmdpstates$.

\paragraph*{Rewards}
$\hmdprewards: \hmdpstates \times \hmdpactions \rightarrow \mathbb{R}$ is a reward function.
%
To build the \highlevelmdp{}, we need to estimate the reward that the robot will obtain for each navigation action, since the true reward values are not known in advance.
%
We do this by using a constrained random walk algorithm to generate a set of candidate paths for each action \correction{in a computationally efficient way}.
%
The rewards over these paths are then estimated using the current GP model of the environment.
%
Our approach is summarised in Algorithm~\ref{alg:high-level-rewards}.
%
This algorithm generates $n$ paths from depot $d_1$ to $d_2$ by starting at $d_1$ and iteratively selecting a random valid successor---defined here as a state from which $d_2$ could still be reached before the action duration had elapsed, if the shortest path were followed (Lines~\ref{line:valid-actions}-\ref{line:select-random-action}).
%
The reward at each step is evaluated as the UCB of the GP posterior~(Line~\ref{line:ucb-reward}) at the time of the \highlevelmdp{} construction, where this GP is \emph{not} updated during the evaluation process.
%
By using the UCB reward, as in Chapter~\ref{ch:LTM1}, we encourage exploration in areas where the model has high uncertainty.
%
%The reward for the MDP is taken to be the \emph{maximum} over the $n$ paths~(Line~\ref{line:reward_max}), since we expect the low-level planner to generally be able to find a path at least as good as any random walk paths.
We take the reward for the MDP to be the \emph{maximum} over the $n$ paths~(Line~\ref{line:reward_max}), again in order to encourage exploratory behaviour.
%
This method provides an approximation to the true value of different paths through the \algshort{}, which can be computed quickly for a large number of paths while remaining sufficiently informative to guide exploration at a high level.

% In this work, we use deterministic transitions in the \highlevelmdp{}.
% %
% However, future work could extend this to more sophisticated models; for example, by directly incorporating outcomes of past actions into probabilistic high-level actions.  

\begin{algorithm}[]
    \algsize
    \caption{{\sc Computing \highlevelmdp{} Rewards}}
    \label{alg:high-level-rewards}
    \textbf{Input}: \algshort{} $\pksmdp$, GP model $\gp$,  depots $d_1, d_2 \in \tmdepots$, initial time $t_\mathrm{init}$, deadline $\LLdeadline$, number of trials $n$. \\
    \textbf{Output}: Reward value $r \in \mathbb{R}$
    \begin{algorithmic}[1] %[1] enables line numbers
        \Procedure{EstimateReward}{$\pksmdp, \gp, d_1, d_2, t_\mathrm{init}, \LLdeadline, n$}
        \For{$j \in \{1, \dots, n\}$}
        \State $r_j \gets 0$
        \State $s \gets \LLtargetdepot, t$ (initial state)
        % \State $t \gets t_\mathrm{init}$ (current time)
        % \State $\text{loc} \gets d_1$ (current location)
        \While{true}
        \State $A_v \gets \textsc{GetAvailableActions}(\pksmdp, \pksmdpstate,  d_2, \LLdeadline)$ \label{line:valid-actions}
        \If {$A_v = \emptyset$}
        \State \textbf{break}
        \EndIf
        \State $\pksmdpaction \gets \textsc{RandomChoice}(A_v)$ \label{line:select-random-action}
        \State $\pksmdpstate \gets \textsc{GetActionOutcome}(\pksmdpstate, \pksmdpaction)$
        \State $r_j \gets r_j + \textsc{UCB}(\gp, \pksmdpstate)$ \label{line:ucb-reward}
        \EndWhile
        \EndFor
        \State \textbf{return} $\max_j(r_j)$ \label{line:reward_max}
        \EndProcedure

        \item[]

        \Procedure{GetAvailableActions}{$\pksmdp, \mctsnodeb, \LLtargetdepot, \LLdeadline$} \label{line:get_available_actions}
        \State $\pksmdpavailableactions \gets \emptyset$
        \For{$\pksmdpaction \gets \textsc{GetEnabledActions}(\pksmdp, \pksmdpstate)$}
        \State $\pksmdpstate' \gets \pksmdptransition(\pksmdpstate, \pksmdpaction)$
        \If{$t(\pksmdpstate) + \dur{\pksmdpaction} + \textsc{ShortestPath}(\tm, \pksmdpstate', \LLtargetdepot) \leq \LLdeadline$} \label{line:check_reach_det}
        \State $\pksmdpavailableactions \gets \pksmdpavailableactions \cup \{\pksmdpaction\}$
        \EndIf
        \EndFor
        \State \Return $\pksmdpavailableactions$
        \EndProcedure

    \end{algorithmic}
\end{algorithm}

% \paragraph*{} % Paragraph break
%
The \highlevelmdp{} can be solved using standard MDP solution techniques to obtain a high-level policy.
%
The action specified by the policy for the current state is then passed as a constraint to the low-level planner, specifying a target depot $\LLtargetdepot \in D$ and the deadline $\LLdeadline$ by which it must be reached.
%
We assume that the low-level planner makes use of all of the available time for each high-level action.
%
Once this action is executed, a new \highlevelmdp{} is created and solved again for the next action, until the full mission is completed.

\subsection{Low-level planning: belief-based MCTS}
\label{sec:low-level-planner}

The low-level planner is a modified version of the planner from Chapter~\ref{ch:LTM1}, which includes additional inputs representing the high-level action constraints.
%
In effect, it solves a simplified version of the full  planning problem represented by the \algshort{}, in which the planning horizon is much shorter and resource management is not explicitly considered.
%
The low-level planning algorithm is summarised in Algorithm~\ref{alg:low-level-planner}, with the changes from the general planner in Algorithm~\ref{alg:belief_space_mcts} highlighted.

The key change from the previous planner is that during the selection and rollout phases, an additional filtering step ensures that any selected actions will be feasible given the high-level action constraints.
%
Each high-level navigation action specifies a target depot $\LLtargetdepot$ and a deadline $\LLdeadline$.
% 
The modified \textsc{GetAvailableActions} method (called on Line~\ref{line:get_available_actions}) returns only the available actions which, once executed, would still leave the robot with enough time to reach depot $\LLtargetdepot$ before time $\LLdeadline$.
%
This ensures that the low-level plan will satisfy the resource constraint encoded in the high-level action.
%
In the case of \actiontraverse{} actions, $\LLtargetdepot$ is a tight deadline, so the path followed will be approximately a shortest path.
%
\actionexplore{} actions, on the other hand, give the low-level planner more time to explore while still reaching $\LLtargetdepot$ before the deadline.


\begin{algorithm}[]
    % {
    \algsize
    \captionof{algorithm}{{\sc Low-Level Planning}}
    \label{alg:low-level-planner}
    % \begin{multicols}{2}
    \textbf{Input}: \algshort{} $\pksmdp = \langle \pksmdpstatespace, \pksmdpinitstate, \pksmdpactionspace, \pksmdptransition, \pksmdprewardspace, \pksmdphorizon\rangle$, current GP model $\gp$ (dataset $\gpdataset$, hyperparameters $\gphypers$, kernel $\gpkernel(\gpstate, \gpstate')$), \alghighlight{target depot $\LLtargetdepot$, deadline $\LLdeadline$}.\\
    \textbf{Output}: Updated state and dataset.
    \begin{algorithmic}[1]
        \Procedure{ExecuteHighLevelAction}{$\pksmdp, \gp, \LLtargetdepot, \LLdeadline$}
        \While{$t \leq \LLdeadline$}
        \State $\pksmdpaction \gets \textsc{GetNextAction}(\pksmdp, \gp, \LLtargetdepot, \LLdeadline)$ \label{line:low-level-MCTS-select-action}
        \State $\pksmdpstate', \gpobs' \gets \textsc{ExecuteAction}(\pksmdpaction)$ \label{line:low_level_execute_action}
        \State $\gpdataset \gets \gpdataset \cup \{(\pksmdpstate', \gpobs')\}$ \label{line:low_level_dataset_update}
        \State $\vec{s} \gets \text{new state } \vec{s}'$
        \EndWhile
        % \STATE $\vec{\theta} \gets \textsc{OptimiseHyperparameters}(G, \vec{\theta})$ \label{line:gp_opt}
        \State \textbf{return} $\pksmdpstate$, $\gpdataset$
        \EndProcedure
        \item[]

        % MCTS action selection 
        \Procedure{GetNextAction}{$\pksmdp$, $\gp$, \alghighlight{$\LLtargetdepot$, $\LLdeadline$}}
        \State $\mctsnodeb_\mathrm{root} \gets \textsc{InitialiseTree}(\mainmodelsymbol, \gp)$
        \For{$i \gets 1$ to $N_\mathrm{trials}$}
        \State \alghighlight{$\mctsnodeb_\mathrm{leaf}, r_\mathrm{tree} \gets \textsc{SelectNode}(\mainmodelsymbol, \gp, \mctsnodeb_\mathrm{root}, \LLtargetdepot, \LLdeadline)$}
        \State \alghighlight{$r_\mathrm{rollout} \gets \textsc{PerformRollout}(\mctsnodeb_\mathrm{leaf}, \LLtargetdepot, \LLdeadline)$}
        \State $r_\mathrm{total} \gets r_\mathrm{tree} + r_\mathrm{rollout}$
        \State $\textsc{Backpropagate}(\mctsnodeb_\mathrm{leaf}, r_\mathrm{total})$
        \EndFor
        % \STATE $\vec{\theta} \gets \textsc{OptimiseHyperparameters}(G, \vec{\theta})$ \label{line:gp_opt}
        \State \Return $\textsc{BestChild}(\mctsnodeb_\mathrm{root})$
        \EndProcedure
        \item[]

        \Procedure{SelectNode}{$\pksmdp, \gp, \mctsnodeb_\mathrm{root}, \alghighlight{\LLtargetdepot, \LLdeadline}$}
        \State $\mctsnodeb \gets \mctsnodeb_\mathrm{root}$
        \State $r_\mathrm{tree} \gets 0$
        \While{$\mathrm{depth}(\mctsnodeb) < d_\mathrm{max}$}
        \State \alghighlight{$\pksmdpavailableactions \gets \textsc{GetAvailableActions}(\pksmdp, \mctsnodeb, \LLtargetdepot, \LLdeadline)$} \Comment{See Algorithm~\ref{alg:high-level-rewards}.}\label{line:get_available_actions}
        \State $n_\mathrm{child}^{BA} \gets \textsc{SelectActionPUCT}(n^v, \pksmdpavailableactions)$ \label{line:cnst_select_action_PUCT}
        \If{$\mctsnodeba_\mathrm{child} = \varnothing$}
        \State \Return $\mctsnodeb, r_\mathrm{tree}$
        \EndIf
        % Progressive widening belief step
        \State $\mctsnodeb_\mathrm{child}, r_\mathrm{child} \gets \textsc{GenerateBeliefChild}(\mctsnodeba _\mathrm{child})$
        \State $\mctsnodeb \gets \mctsnodeb_\mathrm{child}$
        \State $r_\mathrm{tree} \gets r_\mathrm{tree} + r_\mathrm{child}$
        \EndWhile
        \State \Return $\mctsnodeb, r_\mathrm{tree}$
        \EndProcedure
        \item[]

        \Procedure{PerformRollout}{$\mctsnodeb, \alghighlight{\LLtargetdepot, \LLdeadline}$}
        \State $s \gets s(\mctsnodeb)$
        \While{$t(s) \leq \LLtargetdepot$}
        \State \alghighlight{$\pksmdpavailableactions \gets \textsc{GetAvailableActions}(s, \LLtargetdepot, \LLdeadline)$}
        \State $a \gets \textsc{RandomChoice}(\pksmdpavailableactions)$
        \EndWhile
        \State \Return $A$
        \EndProcedure
        % \item[]

        % \alghighlight{
        % }
    \end{algorithmic}
    % \end{multicols}
    % }
\end{algorithm}


During the rollout phase of MCTS,  reward at each step is evaluated as the UCB of the GP model from the corresponding leaf node, as in Chapter~\ref{ch:LTM1}.
%
The UCB reward is used again to encourage exploration, since the full mission extends beyond the horizon of the low-level plan.
%
This hierarchical approach gives the flexibility needed to intelligently tackle the long-term monitoring problem.
%
In the early stages of a mission, uncertainty across the map is high, so the high-level planner will generate policies that guide the robot to explore it---the low-level planner is short-sighted, and so cannot do this on its own.
%
Later, as the GP model improves, the high-level planner will generate actions more focused on reward-gathering in high-reward areas of the map, which are then executed by the low-level planner.


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

We now present a series of experiments to explore the capabilities of our planner.
%
We first test the planner's  scheduling and long-term planning abilities in synthetic gridworld domains.
%
Then, in Section~\ref{ssec:experiments_wildfire}, we deploy the planner in a realistic simulation of a wildfire monitoring scenario.

\subsection{Planner configurations}

In order to assess the effectiveness of our planning approach, we present a series of experiments comparing it to two other planner configurations.
%
We refer to the full hierarchical planning system described in Section~\ref{sec:LTM2_algorithm} as the \algmain{} planner.
%
The \algfixed{} planner  removes the flexible scheduling component of the full planner, using a restricted version of the \algshort{} with $\timestep=\qty{12}{\hour}$; this puts the robot on a fixed schedule, where it is \stateactive{} for 12 hours starting from the same time every day, and then \statecharging{} for 12 hours.
%
The high-level planning horizon $\hmdphorizon$ for this configuration may still span multiple days.
%
The final configuration, \algbasic{}, implements the planner from Chapter~\ref{ch:LTM1}.
%
The \algbasic{} planner operates on the same schedule as the \algfixed{} planner, but uses only the low-level planner each day, thus removing the hierarchical component entirely.
%
In this configuration, since there is no high-level planner, the low-level planner's actions are instead constrained only to ensure that the robot concludes each \stateactive{} period at a depot.
%
This is done by pruning any action that would make it impossible for the robot to reach a depot before its resources ran out.


In all experiments, we use the robot's battery charge as the constrained resource, letting $b = 1$ represent a charge capacity that can support 12 hours of activity, and $\ratecharge = \ratedischarge = 1$ unit per hour---that is, the robot's battery supports 12 hours of continuous activity, and charges at the same (constant) rate at which it discharges.
%
Each algorithm uses a GP with a product spatiotemporal kernel, as described in Section~\ref{ssec:spatiotemporal_gp_modelling}.
%$ an RBF spatial kernel, and a product RBF and periodic temporal kernel with a fixed period of $\qty{24}{\hour}$.


\subsection{Experimental domains}
\label{ssec:LTM2_domains}

\subsubsection{Synthetic domains}

% We demonstrate our planning approach on a series of domains based on ecological monitoring. 
%
Each synthetic domain is an $n \times n$  gridworld, where the unknown feature $\processfunction$ is composed of a set of Gaussian point sources.
%
These may oscillate in amplitude throughout the day and drift slowly around the map, as in the \textsc{Moving} domains of the previous chapter.
%
They are designed to reflect general behaviours that can be seen across a variety of ecological domains.
%
The shorter-term movements represent changes that might be seen in tracking a herd of animals, for example, or observing local weather patterns.
%
The longer-term drift is intended to capture slower changes, such as seasonal patterns.

\subsubsection{Wildfire monitoring domain}

Our wildfire monitoring problem instance uses fire hotspot data from the MODIS dataset~\cite{NASAmodis6} of the NASA Fire Information for Resource Management System (FIRMS) database.
%
This dataset provides information about fire hotspots identified by satellite imagery in the mid-infrared range at a spatial resolution of \qty{1}{\km}.
%
The temporal resolution of the data is somewhat limited, however, and we  discuss in Section~\ref{ssec:experiments_wildfire} how this might affect the observed results.

\begin{figure}
    \centering
    \includegraphics[width=0.8\linewidth]{chapters/chLTM2/figures/wildfire-domain-tm.png}
    \caption[UAV wildfire monitoring problem domain]{Problem domain for UAV wildfire monitoring in Kosciuszko National Park, Australia. The topological map is shown, with blue waypoints representing depots (weather stations). Wildfire hotspots from the NASA FIRMS database are shown faintly in yellow/red. \correction{Satellite imagery from }\cite{stockli2005blue}.}
    \label{fig:wildfire_domain_full}
\end{figure}



We simulate the wildfire by sampling the location and brightness of hotspots in Kosciuszko National Park in Australia from the MODIS dataset, between December 2019 and January 2020.
%
These points are used to train a GP model with an RBF kernel, which simulates the ``ground truth'' of the environment process in our experiments.
%
The robot is able to sample noisy observations from this simulated model during exploration.
%
This process is required to convert the raw data into a form that can be sampled over continuous space and time.
%
Figure~\ref{fig:wildfire_domain_gp} shows snapspots of our ground truth GP model on different days of the mission, revealing the general evolution of the wildfires over time.

We designate local weather stations as depots for battery charging, based on the assumption that a real-world deployment of a UAV for wildfire monitoring would aim to make use of as much existing infrastructure as possible in order to reduce setup and maintenance costs.
%
The UAV is given a top speed of \qty{4}{\km\per\hour} and battery life of \qty{12}{\hour}, akin to that of a solar-powered surveillance drone such as the SolarXOne made by XSun~\cite{solarxone}.
%
Waypoints are then generated using Poisson disk sampling~\cite{wang2024poisson} within areas of the environment that are accessible based on its topography.
%
This gives the map shown in Figure~\ref{fig:wildfire_domain_full}, which spans approximately \qtyproduct{110 x 90}{\km}.
%
The UAV is deployed on a 20-day mission, with rewards corresponding to observed hotspot brightness---that is, the mission objective is to provide real-time situational awareness of areas where the wildfires are most severe.
%

\begin{figure}
    \centering
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_2.pdf}
        \caption{Day 2.}
        \label{sfig:wildfire_env_gp:1}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_4.pdf}
        \caption{Day 4.}
        \label{sfig:wildfire_env_gp:2}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_6.pdf}
        \caption{Day 6.}
        \label{sfig:wildfire_env_gp:3}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_8.pdf}
        \caption{Day 8.}
        \label{sfig:wildfire_env_gp:4}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_10.pdf}
        \caption{Day 10.}
        \label{sfig:wildfire_env_gp:5}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_12.pdf}
        \caption{Day 12.}
        \label{sfig:wildfire_env_gp:6}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_14.pdf}
        \caption{Day 14.}
        \label{sfig:wildfire_env_gp:7}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_16.pdf}
        \caption{Day 16.}
        \label{sfig:wildfire_env_gp:8}
    \end{subfigure}
    \begin{subfigure}[b]{0.32\linewidth}
        \centering
        \includegraphics[width=1.0\textwidth]{chapters/chLTM2/figures/heatmap_env_wildfire_18.pdf}
        \caption{Day 18.}
        \label{sfig:wildfire_env_gp:9}
    \end{subfigure}
    \caption[Wildfire domain ground truth GP model snapshots]{Snapshots of wildfire domain ground truth GP model, shown at the same time across different days. Yellow regions represent the highest wildfire intensity on a per-day basis. }   \label{fig:wildfire_domain_gp}
\end{figure}




\subsection{Scheduling of active hours}
\label{ssec:LTM2_expts_scheduling}

This experiment is designed to demonstrate the ability of the \algmain{} planner to schedule battery charging based on the reward-gathering objective.
%
If more reward is available at particular times of day, the planner should learn to schedule the robot's active hours to coincide with these times, and perform charging when the available reward is lower.
%
The domain is a small grid with a single depot, over which the value of $\processfunction$ is spatially uniform but varies temporally.
%
Therefore, in this context, it is only the timing of the robot's active hours that affects the reward obtained, rather than the location of the robot.
%
The value of $\processfunction$ oscillates in amplitude throughout each day, with a peak that is initially in the morning, but shifts towards the evening over the 25-day mission.
%
The \algshort{} planner uses a timestep $\timestep=\qty{1}{\hour}$, and is compared to four instances of \algfixed{} planners, each with different scheduled start times which are equally spaced throughout the day.

We see in Figure~\ref{fig:timing_test_rewards} that none of the \algfixed{} planners are able to perform as well as the \algmain{} planner---flexible scheduling of resource replenishment is essential for good performance in this domain.
%
Figure~\ref{fig:timing_test_robot_state} shows the behaviour of the flexible planner, which learns to shift the robot's active hours over the course of the mission to track the times with higher rewards.
%
As expected, this tracking is not perfect, as the planner continues performing some exploratory actions throughout the mission.

\begin{figure}[]
    \centering
    \begin{subfigure}[b]{0.7\linewidth}
        \centering
        \includegraphics[width=\linewidth]{chapters/chLTM2/figures/timing_test_rewards.pdf}
        \caption{Reward accumulated by the \algshort{} planner and four fixed-schedule planners with different starting times (10 trials each).}
        \label{fig:timing_test_rewards}
    \end{subfigure}
    \figvspace
    \begin{subfigure}[b]{0.7\linewidth}
        \centering
        \includegraphics[width=\linewidth]{chapters/chLTM2/figures/timing_test_robot_state.pdf}
        \caption{The robot state at each hour of the mission during one run of the \algshort{} planner.}
        \label{fig:timing_test_robot_state}
    \end{subfigure}
    \caption[Flexible scheduling experiment results]{Results from the active hours scheduling test domain, \correction{demonstrating that the} \algshort{} \correction{planner is able to adaptively schedule the robot's active hours to capitalise on available reward}.}
    \label{fig:LTM2_timing_test}
\end{figure}





\subsection{High-level planning horizon}
\label{ssec:LTM2_expts_horizon}

In this experiment, we examine the effect that the high-level planning horizon $\hmdphorizon$ can have on performance.
%
In principle, a longer horizon should enhance the planner's capabilities, since it allows for decision-making based on a longer view of the future.
%
However, in practice, the larger search space associated with a longer planning horizon can actually make it harder to find good solutions---particularly in problems with high uncertainty.
%
Thus, in general, the choice of planning horizon will depend on the specific problem at hand, as well as the planning time and computational resources available.

The domain for this experiment, shown in Figure~\ref{sfig:horizon_test_domain}, is a $20\times20$ grid map containing a chain of depots, spaced such that the robot takes multiple resource cycles to traverse it from end-to-end.
%
We would expect sparse placement of depots to be common in practice, since installation and maintenance of many depots would be costly, and as such they would likely be placed in the minimal way required to grant the robot coverage of the environment.
%
Here, the unknown function $\processfunction$ has a high-value peak that drifts across the map from left to right over the course of a 50-day mission, as might be seen in monitoring herds of wild animals~\cite{owen2020movement} or tracking the drift of seaweed farms~\cite{stenius2022system}.
%
We ran MCTS with 250 trials.
% The \algmain{} planners used a high-level planning step of $\timestep=\qty{6}{\hour}$. 


We see in Figure~\ref{fig:LTM2_horizon_test} that in order to perform well in this domain, the longer-horizon planning of the \algmain{} is required, and configurations with shorter planning horizons acquire lower total rewards.
%
This also validates our approach to estimating rewards in the \highlevelmdp{}, showing that even without planning in belief space at the high level, our hierarchical approach has significant benefits over the non-hierarchical \algbasic{} baseline.
%
The \algfixed{} planner was tested with a horizon of 5 days, and the \algmain{} planner with the same horizon achieves on average 7\% higher reward, reflecting the benefits of flexible scheduling in overall performance.
%
The average computation time for the $H = \qty{10}{\day}$ configuration was \qty{14.0}{\second} per step.



\begin{figure}
    \centering
    \begin{subfigure}[b]{0.7\linewidth}
        \centering
        \includegraphics[width=\linewidth]{chapters/chLTM2/figures/horizon_test_domain.pdf}
        \caption{Gridmap of the domain. Orange lines link depots that can be reached within a single high-level planner timestep.}
        \label{sfig:horizon_test_domain}
    \end{subfigure}
    \figvspace
    \begin{subfigure}[b]{0.7\linewidth}
        \centering
        \includegraphics[width=\linewidth]{chapters/chLTM2/figures/horizon_test_boxplot.pdf}
        \caption{Cumulative reward with different high-level planning horizons in days (30 trials each). \correction{Performance increases as the planning horizon increases, since this domain requires a long-horizon view in order to find an effective policy.}}
        \label{sfig:horizon_test_results}
    \end{subfigure}
    \caption[Planner horizon experiment results]{Experiment results with different planning horizons. The \algmain{} planner used a high-level timestep of $\timestep=\qty{6}{\hour}$.
    }
    \label{fig:LTM2_horizon_test}
\end{figure}

\subsection{High-level planning step}
\label{ssec:expt_planning_step}

This experiment tests the effect of the high-level planning timestep $\timestep$ for the \algmain{} planner.
%
Here we used a larger $40 \times 40$ grid world containing several randomly-generated high-interest areas which each shift slowly around the map, and ran MCTS with 250 trials.
%
We see in Figure~\ref{fig:increment_test} that, as expected, planning with higher temporal resolution generally results in better performance.
%
This does come with some additional computational demand, since the \highlevelmdp{} grows  with the number of high-level actions that can be executed within its horizon.
%
However, for this configuration we found that the overall impact on computation time from decreasing the timestep  was negligible, and all configurations took a similar computation time of approximately \qty{30}{\second} per step.
%
This indicates that the computational load of planning was dominated by the low-level planner.

\begin{figure}[]
    \centering
    \includegraphics[width=0.75\linewidth]{chapters/chLTM2/figures/increment_test_boxplot.pdf}
    \caption[Planner discretisation step experiment results]{Cumulative reward with different high-level planning discretisation steps in hours (40 trials each). The \algmain{} and \algfixed{} planners used a horizon $H=\qty{5}{days}$. \correction{Performance generally improves as the discretisation becomes finer, at the cost of increased computation.}}
    \label{fig:increment_test}
\end{figure}

\subsection{UAV wildfire monitoring}
\label{ssec:experiments_wildfire}

We now demonstrate a practical application of our approach to the large-scale UAV wildfire monitoring scenario described in Section~\ref{ssec:LTM2_domains}.
%
For each experiment, we ran MCTS with 500 trials, and used a high-level planner timestep of $\timestep = \qty{4}{\hour}$.
%
The results from this domain are shown in Figure~\ref{fig:wildfire_domain_results}.

For the longest planning horizon of $H = \qty{10}{\day}$, our planner required an average computation time of \qty{94.4}{\second} per step, which is low enough to allow for online planning in a domain of this scale.
%
We see that our hierarchical planning approach provides a clear benefit over the \algbasic{} planner, which tends to get trapped in local minima and fails to usefully monitor the large environment.
%
The \algfixed{} planner is also outperformed by the \algmain{} planner with the same horizon, indicating that flexible scheduling can provide a significant advantage in this domain.
%
This is as expected, since wildfires typically burn more intensely during the heat of the day---it should be the case that appropriate selection of active hours allows for more total reward to be accumulated.

It is also worth noting that the realism of our simulator is limited somewhat by the low temporal resolution of the MODIS satellite data.
%
Hotspots can only be detected when the satellite passes overhead, and in this dataset each location typically only receives 1--5 satellite flyovers per day.
%
This limits the amount of temporal variation from the true wildfires that could be captured by our ground truth GP model, and it is likely that with better ground truth data, the daily variations would be accentuated even more.
%
Nonetheless, this experiment demonstrates that our planner can produce effective  monitoring behaviour in a practical application.
%
It enables a robot to autonomously provide  situational awareness in a dynamic and time-critical setting, without relying on prior knowledge about the behaviour of the environment feature of interest.

\begin{figure}[]
    \centering
    \includegraphics[width=0.75\linewidth]{chapters/chLTM2/figures/horizon_test_boxplot_wildfire.pdf}
    \caption[UAV wildfire monitoring results]{Cumulative reward obtained by different planner configurations on the wildfire domain (10 trials each). \correction{Planner performance improves as the planning horizon grows, and the} \algmain{} \correction{planner outperforms the} \algfixed{} \correction{planner with the same horizon, indicating some benefit of flexible scheduling in this domain.}}
    \label{fig:wildfire_domain_results}
\end{figure}


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

The multi-depot planning problem presented in this chapter opens up a richer planning space than the single-depot, fixed-schedule framework of the previous chapter.
%
This is demonstrated in the synthetic domain experiments, where we see that our planner is able to adapt its active hours to improve its mission outcomes.
%
Our planner is also able to benefit (albeit marginally) from a planning horizon of up to 10 days, achieving meaningful long-term planning even with a highly uncertain model.
%
These behaviours are enabled by the high-level Depot-MDP model, which enables long-horizon planning over a simplified, abstract representation of the full state space.

However, the Depot-MDP model is somewhat rigid, and would likely struggle to scale to very large domains.
%
Its primary limitation on this front is that the computationally demanding reward estimation process (Algorithm~\ref{alg:high-level-rewards}) is always performed over the full state space of the Depot-MDP---that is, rewards are estimated through GP inference over the entire map, even areas far from the robot's current location which are likely irrelevant to the immediate decision making.
%
While this might be addressed by pruning the Depot-MDP to restrict its range, such an approach might inadvertently remove promising paths from consideration.
%
Another key limitation of the Depot-MDP model is its use of discrete timesteps, which is suboptimal in the continuous-time problem settings we consider.
%
In the deterministic-action setting considered in this chapter, this is not a major issue, but in a more realistic setting with stochastic action durations, the discrete-time assumption could lead to significantly greater loss to planning efficiency.
%
In the next chapter, we will design a new, MCTS-based high-level planner which addresses each of these limtations.



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

We have presented a hierarchical planning approach for long-term robot monitoring in a GP-modelled unknown environment subject to resource constraints.
%
Our work considers a setting in which the robot is able to autonomously recharge its resources at depots, enabling monitoring missions that span much larger areas than can be covered in a single battery cycle.
%
We  achieve effective long-horizon planning under uncertainty by separating high-level path planning and resource management from low-level action selection.
%
Our planner is able to effectively fulfil monitoring mission objectives while replenishing resources as needed, balancing exploration and exploitation in a sensible manner.
%
We demonstrated through a series of experiments that our planner is able to effectively fulfil its monitoring objective while replenishing resources as needed, and showed that it is able to perform well compared to relevant baselines in a wildfire monitoring application.
%
% Potential avenues for future work include generalisation to uncertain action durations or stochastic battery models, as well as the addition of mobile depots.
%
% Our high-level model could also be extended to scale better to a broader range of timescales, by planning in smaller steps for the near future and larger steps farther out. 