Bayesian Reinforcement Learning for Single-Episode Missions in Partially Unknown Environments
Authors: Matthew Budd
Paul Duckworth
Nick Hawes
Bruno Lacerda
Venue: CoRL 2022 Poster (2022)
Keywords: Planning under Uncertainty
Gaussian Processes
Single-Episode Bayesian Reinforcement Learning

Abstract: We consider planning for mobile robots conducting missions in real-world domains where a priori unknown dynamics affect the robot’s costs and transitions. We study single-episode missions where it is crucial that the robot appropriately trades off exploration and exploitation, such that the learning of the environment dynamics is just enough to effectively complete the mission. Thus, we propose modelling unknown dynamics using Gaussian processes, which provide a principled Bayesian framework for incorporating online observations made by the robot, and using them to predict the dynamics in unexplored areas. We then formulate the problem of mission planning in Markov decision processes under Gaussian process predictions as Bayesian model-based reinforcement learning. This allows us to employ solution techniques that plan more efficiently than previous Gaussian process planning methods are able to. We empirically evaluate the benefits of our formulation in an underwater autonomous vehicle navigation task and robot mission planning in a realistic simulation of a nuclear environment.

Bayesian Reinforcement Learning for Single-Episode Missions in Partially Unknown Environments
Matthew Budd Paul Duckworth
Nick Hawes Bruno Lacerda
Oxford Robotics Institute, University of Oxford
(mbudd, pduckworth, nickh, bruno)@robose ox ac.uk
Abstract: We consider planning for mobile robots conducting missions in real- world domains where a priori unknown dynamics affect the robot's costs and transitions. We study single-episode missions where it is crucial that the robot appropriately trades off exploration and exploitation, such that the learning of the environment dynamics is just enough to effectively complete the mission. Thus, we propose modelling unknown dynamics using Gaussian processes, which provide a principled Bayesian framework for incorporating online observations made by the robot, and using them to predict the dynamics unexplored areas. We then formulate the problem of mission planning in Markov decision processes under Gaussian process predictions as Bayesian model-basee reinforcement learning. This allows us to employ solution techniques that plan more efficiently than previ- ous Gaussian process planning methods are able to. We empirically evaluate the benefits of our formulation in an underwater autonomous vehicle navigation task and robot mission planning in a realistic simulation of nuclear environment.
Planning under Uncertainty, Gaussian Processes, Single-Episode Bayesian Reinforcement Learning
Keywords:
Introduction
Real-worid mobile robots rarely have complete knowledge of their environment dynamics. When operating under uncertainty, they need to be able to incorporate their online observations of uncertain environment features into their plans. In this paper, we consider the single-episode setting where robot must carry out a mission in an environment for which the dynamics are not fully known at deployment time. The mission is specified by goal state(s) that the agent must eventually reach while minimising incurred cost under an environment feature that has a priori unknown dynamics. The robot's information gathering capabilities are limited, as the environment features are only observable at the robot's current state. An example would be Geiger counter-equipped robot minimising its cumulative radiation exposure in an environment with an unknown radiation distribution. In this setting, infeasible to pre-plan for every possible environment that might be encountered. Moreover, even if it were possible to pre-train standard reinforcement learning (RL) agent every possible environment, it would lack the flexibility to adapt the robot's 's behaviour taking into account new observations it can collect during the mission.
To model continuous environment features, we follow previous works [1, 2, 3, 4] and use Gaussian process (GP) [5] to predict unknown dynamics away from the agent's 's current location. GPs are well-suited for modelling spatio-temporal distributions by incorporating online measurements into the posterior distribution, along with a measure of predictive uncertainty. GP prior hyperparameters can be estimated from physical intuition or from small dataset of similar environments. Similarly to [1. 2, 3, 4], our GP maintains belief over the underlying dynamics of the environment. Rather than ensuring safe environment exploration or maximising information collected, we extend these works by formulating unified Bayes-optimal framework for efficient online mission planning.
We therefore pose our task as online, model-based Bayesian RL (BRL) with a GP belief over the transition function. As all environmental uncertainty is then encapsulated within the transition function, we assume that the cost function known given an instance of the environment dynamics. Continuing the previous example, the robot does not need to learn online that it incurs more damage
6th Conference on Robot Learning (CoRI. 2022), Auckland, New Zealand.

---

from higher levels of radiation. Our problem statement also assumes discrete state space (except for unknown environment dynamies, which are continuous) and full observability of the current state.
The BRL formulation provides several advantages. First, it is known to optimally trade off exploration and exploitation [6], which is crucial in the single-mission setting we address: over-exploration may hinder mission performance or increase the risk of failure. Second, it allows us to intuitively encode the agent's transition function and local observability limitations, and reflects the existence of fixed (but a priori unknown) true underlying environment dynamics; third, it enables the use of efficient Monte- Carlo planning approaches developed for BRL.
Our contributions are to 1. formulate goal-driven planning in unknown environments as model-based BRL; 2. adapt the Bayes-adaptive Monte- Carlo planning (BAMCP) algorithm [6] for our GP-based goal-driven BRI. problem formulation; and 3. use this formulation and algorithm to improve on previous GP planning approaches, both in expressibility and computational efficiency. In particular, we exploit techniques that allow us to efficiently sample possible environment dynamics from the GP use during planning. To the best of our knowledge, we are the first to apply BRL with GP belief' models to goal-driven planning in partially unknown environments.
2 Related Work
Non-myopic gpeision-making with an unknown transition function requires reasoning over possible observation (i.e. function evaluation) sequences. This task has been investigated from the perspective of several fields, including sequential Bayesian optimisation (BO) of unknown functions. An example BO objective could be to stay within computational evaluation budget while improving a GP model of the unknown function. Some recent methods are able to pose multiple-step
bok-ahead in GPs as single joint optimisation problem [7]. However, focus physical systems such as mobile robots which are required to physically move and observe any queried location: observations cannot freely specified locations. This implies reachability, observability and cost
be made in parallel limitations that are not usually considered when using BO.
Considering some of these aspects, recent literature [8, 3] performs non-myopic "informative path planning" for environmental monitoring. Similar to our approach, these methods perform Monte- Carlo tree search (MCTS) [9] in belief space with GP belief. However, they assume robot actions have deterministic outcomes, and do not consider the case where the unknown environment features affect robot transition dynamics,
we do. This recent literature uses partially observable Markov decision process (POMDP) [10] problem formulation, and plan with MCTS trees of com- putationally expensive Gerrepreeedted beliefs due to their BO objective. Our Bayes-adaptive MDP (BAMDP) [1 1] formulation more appropriately represents the existence of fixed but a priori unknown environment dynamics. In the context of goal- goal-based planning objective, the two formulations and solution methods are equivalent, as we demonstrate in this paper. However, we use model- BRL techniques root sample the GP environment belief. This avoids computationally expensive belief updates, enabling the construction of larger MCTS trees within the same computational budget.
Monte-Carlo tree search in GP-modelled unknown environments has also been carried out in [12], where the environment features affect only transition durations in a semi-MDP. A model-based BRL method with a Gaussian process dynamical model (GPDM) belief representation was presented in [13]. Their method must make restrictive maximum likelihood transition/observatinn assumptions for tractability, due to their unfocused Monte-Cand Caato planning algorithm. Alternatively, some RL techniques such as Gaussian Process temporal difference [14] use GPs to directly model an MDP value function. We argue that GP modelling the real-world environmental phenomena, rather than the value function, lets us provide physically principled and interpretable prior knowledge.
3 Preliminaries
Markoy Decision Processes. We consider stochastic shortest path (SSP) MDP problems [15], as
they are well-suited for specifying single episode goal-driven missions. An SSP MDP is defined as tuple M = (S. 80, A, A,T.C. C, G), where S a finite set of states; 80 E S is the initial state; A is finite set of actions; T S x A x S
[0. 1] is probabilistic transition function T(s, a, 8') = p(s' 8, a): C: A - Rezo is a cost function; and G C S a set of absorbing, zero-cost goal states. A history à of MDP M is state-action sequence s000s1aj
a,-18; such that T( a, 3(41) 0

---

for all E {O....,t ...,,,-1 1}. We denote the set of all histories of M as H.M A stationary, deterministic policy a mapping π
A that defines the action to take each state. A policy is proper in a state 8 if it reaches a goal state 8g E G when starting from with probability 1. In an SSP MDP there must exist a policy that is proper all states, and all improper policies must incur infinite cost. Under these assumptions, there exists cost-optimal proper policy [16].
Bayesian RL. In BRL, an agent uses Bayesian inference maintain a posterior distribution, or belief. over the true dynamics of the underlying model given some prior distribution. For an MDP, either or both of the transition function T and cost function C' could a priori unknown. We focus on the case where only T is unknown. C' can be assumed to be known in our setting, as it represents the known effect of a given instance of environment dynamics on the robot. For example, the time cost of travelling against given water current vectors can be calculated given the value of the vectors and the vehicle's s known dynamics. Given a history h = 5000s1 [1 4t-18t 8t, it is possible to generate the posterior belief over the transition function T given h. This can be carried out with successive applications of Bayes' rule p(T h2) x p(h; (T) from the initial history ha = So up to the full history h4 = h. This allows for the definition of a Bayes-adaptive MDP (BAMDP) [11], which achieves Bayes optimality by adding histories to its state representation. and encoding uncertainty over T in its transition function. Let (S, so, A, T, C, G) be an MDP with a prior belief ((T) over the true transition function T. The corresponding BAMDP is an MDP M = (St st A. A C G+). where S+
S H H.M 5o (so,ho); C+ ((s, h), a) C(s,a); G ((s,h) E 8 E G}; and
T ((s, a, has')) = J T(s, s' (p((T h)dT.
(1)
Although the state-history pairs in St are redundant because the current state can be extracted from the history, T : x H. + A. The optimal policy π minimises the expected cumulative cost to reach G+, given the prior over T. This policy is stationary in St but is history-dependent in the original MDP. T considers the posterior p(T h)) and adapts its action selection to account for the conditional distribution of T given the observed h.
the hs notation for clarity in [6]. A policy in BAMDP is a mapping
Gaussian Processes. A GP is a collection of random variables, any finite number of which have joint Gaussian distribution [5]. A GP regression is of the form o(s) ~ (m(m(s), k(s, s')), giving a probability distribution over functions fully specified by the mean mns) and kernel k(s, s functions. We can let m(s) = 0 without loss of generality. Given dataset of noisy observations D= [s,, ((;)) + + for locations 8; and where G ~ N(O, o?) is Gaussian observation noise, GP regression predicts unknown environment feature values at all inputs s.. The kernel function k is parameterised by hyperparameters O. Given hyperparameter priors (0). their values are commonly optimised by maximising the log marginal likelihood for the model given the dataset. The resulting Gaussian posterior, conditioned on the observations o = [o(s1) + e1...., .(8n) + +.]]" is a multivariate normal
s.. ~ N(W,, E.), where μ. (KK, + I) l, and Σ, = K.. K. (K, "
The positive semi-definite kernel matrix K,, = [kt(s, s')...'e.... K. = [k(s,, , 8') sE), sES. K., = [R(ss, s'),.." and I R is the identity matrix. We can sample functions from the GP posterior at finite set of m points, incurring O(1n m)) computational cost.
4 Approach
4.1 Problem Formulation
In order to clearly separate known system transition dynamics from the unknown environment dynamics, we represent the unknown environment and its effect on the agent as an MDP with Unknown Feature Values (U-MDP) [4].
Let SA be a set of state features with discrete, known values (e.g. pose of a robot in a grid map) and S. a set of state features with unknown values in R (e.g. the water current vector at pose). Let o: Sk - S, be an a priori unknown mapping that specifies the values o(*R) E S. observed at locations s& Sg. An SSP U-MDP is tuple M (So, 88 A T O Go) where: S S2 x Sc;
3

---

s6 is the initial state si = (Sk.u. ((5k,0)): A is finite set of actions; T is the U-MDP transition function To: (Sx x Se) x A x Sy - [0. 1]. As the state of the U-MDP is uniquely defined by the value of the known state feature(s) sk E Sg. the transition function of the U-MDP only represents the change in the known state feature(s); C S x A + Ry0 is the cost function; and Go C Sy. is the set of goal states, defined only across known value state features as o(sg) is not known for all Sg E G The problem addressed in this paper is formalised as an SSP U-MDP. The objective is to find a policy that minimises the expected cost to a reach state o(sk) E S such that sg E GO.
4.2 From U-MDPs to GP-BAMDPss
For notational simplicity, in the following we assume a single state feature with unknown values. The approach presented below can easily be extended to cases with more than one unknown value state feature, either using a multi-output GP [17] or multiple single-output GPs. The former assumes non-independent feature dynamics, where learning about one could improve predictions of another.
To estimate the unknown mapping o, we propose that the agent maintains GP model created by adding a new observation of o at each timestep. Specifically, after observing history h = (8k.0. 86,0 $c,0))o(SE,I- Sc,1 )a1 (#E,t, 8e,t), we define D,, = {(8R,,, Se,²) E {o......3) .}). Then, the GP model is denoted as GPP, and the GP posterior over o(sE) is given by pSp (sc 8k: Dr). We assume that observations of o have negligible noise, which corresponds to full observability of the current state. Finally, note that by modelling unknown environment features with a GP we are implicitly making regularity and Lipschitz continuity modelling assumptions the environment feature functions [5].
We now formulate SSP U-MDP as BAMDP with GP belief over the transition function.
Proposition 1. Let M (50, 88, A To, Co GD) be U-MDP. The GP-BAMDP for M is BAMDP M rates the GP posterion. Formally. for s = (sk. s' = -s)e, E S" a E A: and h = (sk.0, 8,,0))00(a. (c.))))..00-1115... T ((s,h), a,', (ss,)))sss))))
"00 Ao, T .Co+, , where the transition function incorpo-
E H.M for (8K,1,8e)) = (8k,
((ss, 8h) (p 66 Dn).
(2)
Proof. We start by noting that the integral in Equation (1) is the product of two components. The first component is a specific possible transition function. As the single unknown component of T is the mapping o, the value of T (s, a, ss) given knowledge of is defined according to the U-MDP transition function, ensuring that the unknown state feature dynamics are consistent with o:
(($ se), a, (s'2, s')) o) = T (( se), a, ) = o(s{)],
(3)
where I[]] is the indicator function. The second component is the posterior distribution over possible transition functions given history h, which in our case is the GP posterior poP:
p(o(s)) | h) 0 (o(s)) s/6- Da)-
As the unknown state feature dynamics are deterministic given o, the integral over T from Equation (1) only has value when the indicator function in Equation (3) 1. This leads to Equation (2), where all
uncertainty in T is captured in the GP posterior over o, and 7 represents the combination of the U-MDP transition function and the GP belief over the values of the unknown state features.
L
4.3 Solving U-MDPs with BAMCP
Having framed the U-MDP mission planning problem as a BAMDP, we can exploit MCTS planning frameworks that were developed in this context. Specifically, we base our algorithm on BAMCP [6]. This algorithm plans in belief space', but builds search trees of aeciio-obsservatio histories rather than of belief states. The search tree consists of alternating state and action nodes and is constructed over the course of Monte-Carke trials starting from the root node and sampling action outcomes from a generative model. BAMCP adapts the concept of root sampling from POMCP [18), where for each MCTS trial a transition function I' is sampled from the root belief node and used throughout the trial. Actions are chosen inside the search tree using free policy, most commonly UCT [9]. New lea nodes' values are estimated heuristically by continuing the trial trajectory from the leaf node using rollout policy.
GP-BAMCP.
TTee distribution over the transition function T in the case of BAMCP.

---

Parent node
Past actual history
Algorithm GP-BAMCP: PLAN
gP Do
MCTS - tree policy
1: procedure PLAN(GPDs history h, start state Se), goal state set G*)
02
Sample s' = (sk. s/a)
2: repeat
according to T IPD,
Child node
3:
ò sample from GPD
4:
T((sK, Se), (s
s())
ha1s'
gP DP s1,)
([sk,, Se), (5 s'd)
5:
SIMULATE( Sk: Se), h GO)
Trollout
6:
until TIMEOUT(
7:
return arg min, (h),a)
Figure 1: Example BAMDP MCTS search-tree, with search nodes as ellipses. Green shows search node generation/contents with root sampling ap- proach, and blue shows full belief planning.
8:
end procedure
Our online MCTS planning algorithm, modified version of BAMCP for GP beliefs, is described Algorithm To simplify the presentation, we assume that the rollout policy is able to reach the goal set with probability 1. Our algorithm replaces BAMCP's depth d and reward I parameters with the goal set G and costs C, respectively, to reflect the SSP mission setting of our work. In our root sampling of T is performed by sampling from the current GP posterior, as described in lines and 4. Concretely, we take a sample GPD, where ô Sy - Se is a possible mapping from known states to values of the unknown state features. Sampling â from the root belief node corresponds to sampling a possible environment that is consistent with the current GP environment model, i.e. trained only real-world observations. Finally, in line 7, the agent greedily selects single real-world action by running MCTS trials up to computational budget.
Treatment of continuous Se. Equation (2) represents a BAMDP with both discrete (known value) and continuous (unknown value) state features, and therefore also combination of discrete transition function, 7 and continuous transition function given by the GP belief over o. This presents challenges for MCTS methods, since the probability is O. To enable generalisation between histories and allow the search tree to reach depths greater than 1. our algorithm aggregates similar outcomes in se into the same child search node. Each search node has an associated "mean" value Se, where all outcomes I|s" Se < é will be associated with that node. When two MCTS trials sample s (sk, s.) and s' (sk, sy,) from the same start state and action, if l|s sell1 and ||s' sell1 < the two histories will be associated with the same child node. Note that this only associates histories nodes and does not discretise the computation of reward or transition probabilities. The c parameter therefore controls the search-tres branching factor, similarly to in [12] and the two branching factor parameters progressive widening MCTS [19].
transitioning the same state twice
4.4 Theoretical Analysis
Equivalence to Partially Observable MDP Belief Planning Methods. Figure depicts an ex- ample MCTS search-tree mid-mission. Several real actions have been taken in the environment, corresponding to the history h in the root node. When carrying out BAMCP root sampling. a new leaf node is added the MCTS tree by appending the parent node history with new state. This new state 8 ~ T(8, a, +) is sampled from the MDP transition function which was itself sampled from the root for this MCTS simulation, in lines 3 and in Algorithm 1. This depicted in green in Figure 1.
Several previous approaches [8, 3] that integrate GPs and MDPs for decision- decision-making in uncertain environments use partially observable MDP (POMDP) [10]. We call these POMDP belief MCTS approaches, These methods incorporate a GP environment belief into the POMDP state, and use MCTS plan in belief space. Here, new belief state leaf nodes generated using a belief update from the parent node. Belief update this context is carried out by sampling hypothesised data point ő pSP (- Sk, Pparens) from the parent node GP belief posterior and augmenting the child belief node's 's GP dataset with this new point: D Pparent U {(5k Ø)}. This is shown in blue in Figure 1,
5

---

10km
Rad level Goal state
fre;
Gual state
Cust 45888
Cost 17072
Cost 97311
Cost 30258
5km
5
0km
5km
10km
(a) Example radiation domain visualisation, with robot trajectory generated by SP-SSP-BAMCE (red) and by GP belief MCTS (green) algorithms.
(h) Example occan domain visualisation, with an AUV trajectory generated by ---SS---AMCC (red) and by GP belief MCTS (green) algorithms.
Figure Experiment domains. Randomly selected multi-goal problem instances are shown.
where the GP in the child node can be explicitly generated by a belief update from the parent node GP. GP belief updates require adding single new data point to the model, the complexity of which can be reduced from O(N*) to ( where N the number of data and sample points [17]. Even with this reduction, the belief update is still computationally expensive as the dataset of real and hypothesised observations grows. Furthermore, the belief updates are required sequentially, once per MCTS simulation to generate new leaf node. This greatly slows the MCTS procedure.
In contrast, our method does not explicitly generate these hypothesised GPs and plans only using histories. The child node in Figure still represents the same belief as the GP shown in blue, but only contains the history obtained using a root sampled transition function. We prove the history-Gi GP equivalence, and hence the validity of root sampling in our setting, by showing that the probability of generating history from the BAMDP is the same for root sampling as it is for maintaining and updating full GP belief at each belief node.
Proposition Let Phu (he++) be the probability of a history hetr the BAMDP, starting at history he under policy n, when carrying out individual GP belief updates at every stage; and Phu (heer) be the probability of hetr when carrying out GP root sampling. Then, Phu (he+r) = Phi (fx+4) ) for all policies and all histories he+t-
The proof given in the appendix and is direct adaptation of Lemma in [20], accounting for the GP posterior over the transition function, and applies to a general stochastic policy и M. x A - [0, 1].
Once any real observations have been added to the root node GP, number of root samples to plan with at little additional computational cost. This means we can run more trials with the same computational budget, thus building larger MCTS search tree, as demonstrate in Section 5. Finally, we note that, due to the BO setting of [8, 3J, where the objective is directly related the uncertainty in the function being predicted by the GP. is not enough to ensure the same distribution over histories. Thus, they must maintain full GP beliefs in their search nodes.
draw arbitrary
Experiments
Domains Description. We experimentally evaluate the proposed method in simulated domains.
Radiation domain: a robot must navigate to a goal location (single-goal variant), or one of three goal locations (multi-goal variant), in a 20m x 20m reactor room with unknown distribution of radiation level, while minimising its cumulative exposure. The GP model is log-warped [21] to constrain the predictions to be strictly positive and better model order-of- magnitude variation

---

in radiation level caused by 1/r² "solid angle" radiation physics. Goal locations and radiation distributions are randomly generated and described in full in the appendix. The map (Figure 2a) is discretised into an 8-connected grid with side length 1.0m. The robot pose therefore comprises the known value U-MDP state features: Sg is a finite set of (r, y) locations {ar. y) S Sg.. The radiation level is a single unknown value state feature S. I2 where rad_eap E S. is the level at location. The reactor room world is from [22] and is used with Gazebo [23] and ROS [24].
2) Ocean currents domain: an autonomous underwater vehicle (AUV) must navigate underwater to one of set of two to three goal locations (multi-gon) goal variant) or single goal location (single-gond variant) across a 10km x 10km map. under the influence of currents. These are drawn from a real-world ocean current dataset and modelled online by a multi-output coregionalised GP [25]. The AUV is simulated by a kinematics, guidance, navigation and control (GNC) model of a small AUV. The robot pose comprises the known value U-MDP state features: St is finite set of (a, y) locations {z, y} S Sz on a 18 x 20 hexagonal grid of states, giving approximately 500m spacing between states. An example state grid with ground-truth currents shown in Figure 2b. The unknown value state features Se 2² represent the current and y velocities {Ua, Uyy E Se. The cost function encodes the expected traversal time between states given the AUV's water-relative velocity and the current vector values. Additional domain details and parameters are given in the appendix.
Algorithms. Our online BAMCP variant as described in Algorithm I is evaluated against two other GP belief planning algorithm baselines. The performance of sampling-based methods is dependent on the assigned compute budget to select each action, therefore we vary compute budget in each experiment. The GP mean belief MCTS algorithm represents a full GP belief planning approach that makes maximum likelihood assumptions. This is similar to [13], but with GP rather than GPDM model and replacing the Monte Carlo action selection search with MCTS due to the complexity of the search problem. The GP belief MCTS algorithm represents the other full GP belief planning approaches [8, 3] which plan with GP beliefs inside the MCTS search tree, but sample a fixed environment dynamics instance for the MCTS rollout. This avoids carrying out belief updates during the rollout, leading to a speed up in MCTS trials per second. For all algorithms the rollout policy is to choose the action that minimises the travel distance from the next state to the closest goal state.
Results. The plots in Figure 3 are from multiple randomly generated problem instances: 10 for the currents domain, and 5 for the radiation domain. Each algorithn/MCTS time budget combination is given 25 repeats. Values are normalised by the expected minimum achievable cost for the corresponding randomly generated problem, calculated using an exact method and full knowledge of the environment. Due to stochasticity in the simulated robot and environment, it is possible for some runs to achieve costs below this value. Experiments are run on a 3.20GHz i7 / 64GB RAM machine.
In the ocean currents domain, Figures 3a and 3b, GP-SSP-BAMCE significantly outperforms the other algorithms. It is capable of achieving close to optimal cost with only second of computation budget. Given an increased computational budget, each algorithm achieves lower cost-to-goal mean and variance. At lower computational budgets, the GP belief MCTS algorithm consistently outperforms the GP mean belief MCTS algorithm, which must carry out belief update for each step it takes towards a goal state during a rollout. The 1000ms/ / GP mean belief MCTS combination is not shown, as the algorithm is not capable of building a meaningful plan within that time limit.
also significantly outperforms the baselines in the radiation domain, shown in Figures 3c and 3d. In this case, note that the increase in cost-to-goal with additional computation time is caused by the robot spending more time planning while being exposed to radiation, while the normalisation denominator is kept constant. For all methods additional computation time increases plan quality, but this can be offset by the additional stationary time spent planning. The 3000ms time budget case corresponds to the robot spending ~ 50% of its runtime planning rather than moving.
As a summary, GP-SSP-BAMCP's higher performance is due to its ability to carry out far more MCTS trials than the two full belief planning methods. On average across all sampled problem scenarios, GP-SSP-BAMCP carries out ~ 100x more MCTS trials per second than GP mean belief MCTS, and ~ 40x more than GP belief MCTS.
7

---

Relative cost to goal
104
GP mean. MOTS
GP belief MCTS
Relative cost to
10"
10
1000
3000
5000
1000
3000
5000
MCTS time budget per action (ms)
MCTS time budget action (ms)
(a) Single-goal AUV time goal results.
(b) Multi-goal AUV time cost to goal results.
Reeatiive cost goal
10a
Relative cost to goal
10a
10a
10a
100
10
500
1000
2000
3000
1000
2000
3000
MCTS time budget per action (ms)
MCTS time budget per action (ms)
(c) Single-goo goal radiation exposure cost to goal results.
Multi goal radiation exposure cost goal results.
Figure 3: Single- and multi-goal experiment results. Plots consist of 25 simulated experiments for each algorithn/MCTS time budget combination each randomly generated problem instance for that domain.
Conclusion
We have proposed unified Bayesian RI. framework for single-mission robot planning in GP- modelled unknown environments, and demonstrated that we are able to plan more effectively in representative real-world environments than previous approaches are able to. One potential avenue for future work is to apply progressive widening [19] or function approximation [20] techniques our BAMCP search tree, determine whether these produce better plans given the continuous GP-BAMDP state-space. Relaxing the assumption of negligible measurement noise would require introducing partial observability alongside transition function uncertainty. The reformulation would transform the BAMDP into more complex This would allow us address settings with very high localisation uncertainty and sensor noise.
POMDP [26] with continuous GP belief.
Limitations. As with any method using exact GP regression, there is limit to the size of environ- ment that can practically be modelled. Although root sampling limits the computational cost of GP planning, exact GP regression scales with O( + m))) where n is the number of data points and m is the number of sample points. In future work we aim to replace exact GP predictions with approximate GP posterior sampling [27] to reduce the GP computational burden and improve scalability.
As our evaluation is in simulation there may exist a sim-to-real transfer gap when using the method with a real robot. This concern should be partly alleviated by our use of realistic Gazebo [23] simulation and use of real-world currents data with a complex kinematic AUV simulation. The proposed method is also a higher-level planning approach, meaning that the gap should be less wide than with low-level control methods, which are more sensitive small sim-to-real changes.
Finally, for some environments or problem settings there less inherent value in carrying out online planning. For example, with only single goal state and few feasible routes that state, the best approach for the radiation domain may be to navigate as quickly as possible to that state without incurring the radiation exposure costs of stopping plan.

---

Acknowledgments
This work received EPSRC funding via the "From Sensing to Collaboration" programme grant [EP/V000748/1). Matthew Budd was supported by an Amazon Web Services Lighthouse scholarship. Paul Duckworth was supported by the Cancer Research UK Radnet Oxford Centre grant (CRUK A28736).
References
[1] M. Turchetta, F. Berkenkamp, and A. Krause. Safe exploration in finite Markov decision processes with Gaussian processes. Advances in Neural Information Processing Systems (NeurIPS). 29, 2016.
[2] A. Wachi, Y. Sui, Yue, and M. Ono. Safe exploration and optimization of constrained MDPs using Gaussian processes. In AAAI Conference on Artificial Intelligence, volume 32, 2018.
[3] G. Flaspohler, V. Preston, A. P. M. Michel, Y. Girdhar, and N. Roy. Information-guided robotic maximum seek-and-sample partially observable continuous environments. IEEE Robotics and Automation Letters (IEEE RA-L), 4(4), 2019.
[4] M. Budd, B. Lacerda, P. Duckworth, A. West, B. Lennox, and N. Hawes. Markov decision processes with unknown state feature values for safe exploration using gaussian processes. In 2020 NEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 7344-7350. IEEE, 2020.
[5] C. Rasmussen and Williams. Gaussian Processes for Muchine Learning. MIT Press, 2006.
[6] A. Guez, D. Silver, and P. Dayan. Scalable and efficient Bayes-adaptive reinforcement learning based on Monte-Carlo tree search. Journal of Artificial Intelligence Research (JAIR), 48, 2013.
[7] S. Jiang, D. Jiang, M. Balandat, B. Karrer, J. Gardner, and R. Garnett. Efficient nonmyopic Bayesian optimization via one-shot multi-step trees. Advances Neural Information Processing Systems (NeurIPS), 33, 2020.
[8] P. Morere, R. Marchant, and F. Ramos. Sequential Bayesian optimization POMDP for environment monitoring with UAVs. IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2017.
[9] L. Koesis and C. Szepesvári. Bandit based Monte-Cas planning. In European Conference Machine Learning (ECML), pages 282-293. Springer, 2006.
[10] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra. Planning and acting partially observable stochastic domains. Artificial intelligence, 101(1-2):99-134, 1998.
[11] M. O. Duff. Optimal learning: Computational procedures for Bayes-adaptive Markov decision processes. PhD thesis, Dept. of Computer Science, University of Massachusetts Amherst, 2003.
[12] P. Duckworth, B. Lacerda, and N. Hawes. Time-bounded mission planning in time-varying domains with semi-MDPs and Gaussian processes. Conference on Robot Learning (CoRL). Journal of Machine Learning Research, 2021.
[13] P. Dallaire, C. Besse, S. Ross, and B. Bhaib Bayesian reinforcement learning in continuous POMDPs with Gaussian processes. In 2009 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 2604-22222 2609. IEEE, 2009.
[14] Y. Engel, S. Mannor, and R. Meir. Reinforcement learning with Gaussian processes. In Proceedings of the 22nd International Conference on Machine Learning (ICML), pages 201- 208, 2005.
[15] D. P. Bertsekas and J. N. Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3), 1991.
[16] Mausam and A. Kolobov. Planning with Markov decision processes: An Al perspective, Morgan & Claypool Publishers, 2012.

---

[17] M. A. Osborne, J. Roberts, A. Rogers, S. D. Ramchurn, and N. R. Jennings. Towards real-time information processing of sensor network data using computationally efficient multi-output Gaussian processes. In International Conference on Information Processing in Sensor Networks (ISPN). IEEE, 2008.
[18] D. Silver and J. Veness. Monte-Carlo planning in large POMDPs. Advances in Neural Information Processing Systems (NeurIPS), 23, 2010.
[19] A. Couêtoux, J.-B. Hoock, N. Sokolovska, O. Teytaud, and N. Bonnard. Continuous upper confidence trees. In International Conference on Learning and Intelligent Oplimization, pages 433-445. Springer, 2011.
[20] A. Guez, N. Heess, D. Silver, and P. Dayan. Bayes-adaptive simulation-basee search with value function approximation. Advances in Neural Information Processing Systems (NeurIPS), 27, 2014.
[21] E. Snelson, Z. Ghahramani, and C. Rasmussen. Warped Gaussian processes. Advances in Neural Information Processing Systems (NeurIPS), 16, 2003.
[22] T. Wright, A. West, M. Licata, N. Hawes, and B. Lennox. Simulating ionising radiation in Gazebo for robotic nuclear inspection challenges. Robotics, 10(3):86, 2021.
[23] N. Koenig and A. Howard. Design and use paradigms for Gazebo, an open-source multi-robot simulator. In 2004 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), volume 3, pages 144.2154, IEEE, 2004.
[24] M. Quigley, K. Conley, B. Gerkey, J. Faust, T. Foote, J. Leibs, R. Wheeler, A. Y. Ng, et al. ROS: an open- robot operating system. In ICRA workshop on open source software, volume 2009.
[25] C. Williams, E. V. Bonilla, and K. M. Chai. Multi-task Gaussian process prediction. Advances Neural Information Processing Systems (NeurIPS), 20, 2007.
[26] S. Katt, F. A. Oliehoek, and C. Amato. Learning in POMDPs with Monte Carlo tree search. In International Conference Machine Learning (ICML), pages 1819-1827. PMLR, 2017.
[27] Wilson, V. Borovitskiy, A. Terenin, P. Mostowsky, and M. Deisenroth. Efficiently sampling functions from Gaussian process posteriors. In International Conference on Machine Learning (ICML). PMLR, 2020.
10


Reviews:
[{"review_id": "zMsOcogbRan", "reviewer": "Reviewer_T74h", "summary": "The article proposed RL based planning algorithm for unknown environment with dynamics which could affect the cost of a planned trajectory. The proposed method was compared to two baseline approaches and demonstrated advantages through simulations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe comparisons with two major approaches as baseline is great, which reveals the strength of the proposed approach. \n\n\nWeaknesses:\nThe experiments part seems a bit tricky, while the total number of runs in each setup is relatively small number (10), given this is in simulation. Also the baseline approach which seems not to benefit much when more time budget is allowed. Normally if the budget increase, the performance of each method should also improve to some extent.\nThe multi goal/target setup is interesting, however maybe also introduce a single goal/target version to allow the audience see the full picture.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "I understand the proposed approach may outperform the baseline according to the experiments (in simulation), however I am not sure if the baseline approach were setup correctly so even the results looks good, I am not sure if we are seeing the full picture.", "technical_quality": "Fair: Significant additional evidence required to support the claims.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "4: The reviewer is confident but not absolutely certain that the evaluation is correct"}, "extra_text": {"issues": "Could you double check on the experiments and especially on the baselines. The performance should (at least slightly) increase when more budget/planning time allowed. \nAlso consider adding a single target environment to enhance the comparisons."}}, {"review_id": "qiK1gZvduxU", "reviewer": "Reviewer_n5QS", "summary": "The authors propose a GP-based goal-driven BRL problem formulation for goal-driven planning in partially unknown environments. They formulate goal-driven planning in unknown environments as model-based  BRL with clear expressibility and computational efficiency.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Paper is well written and technically sound. Motivation of the paper is solid.\n- The belief update in the theoretical analysis in section 4.4 is clearly explained but I have few questions. I like the figure 1.  \n\nWeakness:\n- Refer to my questions in Issues sections. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "Technically sound paper with incremental research. ", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "4: The reviewer is confident but not absolutely certain that the evaluation is correct"}, "extra_text": {"issues": "I have few questions on theoretical analysis from U-MDPs to GP-BAMDPs\n\n- I couldn't find the reward function in the paper. Can you add them in the rebuttal? \n- Can you explain how the reward is back-propagated up the tree, and the branch’s visited counters are increased? \n- Is the transition function assumed to be deterministic here and independent from the objective function ?\n- I was not clear on how the observation function O is sampled along trajectories? Can you elucidate it further? "}}, {"review_id": "Hb8Q-qli86", "reviewer": "Reviewer_8W33", "summary": "This paper studies a robot motion planning in a partially known environment.  A motivating application is that of an underwater robot where the location of the robot is known but the ocean currents are not.  The unknown ocean currents affect the robot dynamics.  This problem is formalized as a Markov Decision Process with a partially unknown transition function.  The authors utilize Gaussian Processes to model the belief over the unknown state.  They then adapt the Bayes-Adaptive Monte Carlo planning (BAMCP) to their problem in which there are GP beliefs.  They utilize an existing technique called “root sampling”, which avoids GP updates during rollouts.  The authors extend the technical result in [19] to show that the distribution of rollouts is, in some sense, still correct.\n\nThe results are applied to two robotics problems, a radiation domain where a robot navigates between rooms with different radiation levels, and an underwater currents domain.\n", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The simulation environment and results are quite interesting.  I appreciated that two different domains were shown.  The results compared to the two baselines are impressive.\n\n- The main contribution is the extension of root sampling to GPs.  While this follows the development from [19], but it is a nice result that the method is applicable in this setting.\n\nWeaknesses:\n- The abstract and introduction overstate the generality of what is studied in the paper.  I recommend the introduction clearly sets the problem of a discrete state space, uncertainty only in the transition function and not cost, and with full observability of the current state.  These assumptions should be clearly laid out early in the paper.\n\n- The notation and use of acronyms is quite heavy in places, making the paper a hard read.  I do not have a concrete suggestion for improving this as I believe much of the notation follows from [19], but it was something I struggled with in reading the paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "The main contribution is to apply the results in [19] to GP beliefs over a scalar unknown quantity.  On the technical side, the extension of the results from [19] is a good contribution but does appear to follow in a straightforward manner from Lemma 1 in [19].  The simulation results are a strong point, with two interesting scenarios for testing the proposed approach.  I have some concerns about the practical applicability of the proposed approach as it requires perfect localization and that the robot remains on the gridded set of states.  However, I would like to see the paper accepted as I think the paper does have significant strengths.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "4: The reviewer is confident but not absolutely certain that the evaluation is correct"}, "extra_text": {"issues": "- In the introduction, lines 27-30, I found this discussion of RL a bit misleading as I don’t think anyone would think of training an RL agent on every possible environment.  It feels like a bit of a straw man argument.\n\n- Lines 41-42 it is stated that BRL is known to optimally trade off exploration and exploitation.  A reference for this should be included.\n\n- Root sampling is stated as a contribution in lines 50-51, but the concept has not yet been introduced at this point..  \n\n- In Section 4.2 the authors mention that the unknown state is considered scalar for notational simplicity.  It would be good to clarify that more than one unknown state feature is considered in the experiments.\n\n- Line 98, the second half of the sentence appears to be repeated in the following sentence.\n\n- Line 154, there is a discussion of implicitly making regularity and Lipschitz assumptions.  This requires some expansion as it is not clear what function must be Lipschitz continuous.\n\n- Would it make sense to put equation (2) in a claim or lemma environment and then move the derivation to a proof? \n\n- Line 277, typo “stoasticity”\n\n- In the limitations there is a discussion of sim-to-real transfer.  Is imperfect localization going to be the biggest hurdle here?  This is a strong assumption and I’m unsure how it would be handled in a real implementation (say for an underwater vehicle).  \n"}}, {"review_id": "2StIgSLGGwJ", "reviewer": "Reviewer_95C2", "summary": "This paper extended the existing Bayesian reinforcement learning approaches to the usage of Gaussian process belief by introducing GP model to the MDP with Unknown Feature Values. The proposed method GP-BAMCP was evaluated in two simulation tasks wiith unknown environmental features and demonstrated lower cost to goal compared with MCTS based approaches.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper addressed on an interesting topic and successfully attracted the reviewer from the attached video. The structure of the paper is overall good.\n\nWeaknesses:\nThe reviewer believes the approach was not detailed enough. The current paper mainly focused on introducing the MDP with GP belief but did not explained how to solve it using RL. From Algorithm 1,  the reviewer see the planning of GP-BAMCP will minimize the Q function, but there is no information about this Q function. The reviewer wish to see how the approximatied Q function and the GP model affected each other during the learning process and how the related policy and value function were built.\n\nThe experimetal result is also limited in the current version. It is difficult to know the learning capability of the proposed method without learning curve. The comparsiosn to MCTS based approaches is also not enough since both two simulation tasks are not that challenging and should be solved by many baseline RL approach even without neither Bayesian view nor GP model.  The author should clearly explain why other methods were not compared.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "My recommendation is weak reject due to the weakness listed above.", "technical_quality": "Fair: Significant additional evidence required to support the claims.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Relevant but unlikely to deploy to hardware in near future", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "2: Unsure, difficult to assess.", "issues": "1. the proposed method should be detailed in the form of an RL approach. The current paper mainly focused on MDP.\n2. experiment should be exteneded with more analysis and additional comparsions.", "reviewer_expertise": "4: The reviewer is confident but not absolutely certain that the evaluation is correct"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)