Adaptive Discretization using Voronoi Trees for Continuous POMDPs

Planning in scenarios with non-deterministic action effects and partial observability is an essential, yet challenging problem for autonomous robots. The Partially Observable Markov Decision Process (POMDP) (Kaelbling et al., 1998; Sondik, 1971) is a general principled framework for such planning problems. POMDPs lift the planning problem from the state space to the belief space — that is, the set of all probability distributions over the state space. By doing so, POMDPs enable robots to systematically account for uncertainty caused by stochastic actions and incomplete or noisy observations in computing the optimal strategy. Although computing the optimal strategy exactly is intractable in general (Papadimitriou and Tsitsiklis, 1987), the past two decades have seen a surge of sampling-based POMDP solvers (reviewed in (Kurniawati, 2022)) that trade optimality with approximate optimality for computational tractability, enabling POMDPs to become practical for a variety of realistic robotics problems.

Despite these advances, POMDPs with continuous state, action and observation spaces remain a challenge, particularly for high-dimensional continuous action spaces. Recent solvers for continuous-action POMDPs (Fischer and Tas, 2020; Mern et al., 2021; Seiler et al., 2015; Sunberg and Kochenderfer, 2018) are generally online —that is, planning and execution are interleaved— and exploit Monte Carlo Tree Search (MCTS) to find the best action among a finite representative subset of the action space. MCTS interleaves guided belief space sampling, value estimation and action subset refinement to incrementally improve the possibility that the selected subset of actions contains the best action. They generally use UCB1 (Auer et al., 2002) to guide belief space sampling and Monte Carlo backup for value estimation, but differ in the action subset refinement.

Several approaches use the Progressive Widening strategy (Couëtoux et al., 2011) to continuously add new randomly sampled actions once current actions have been sufficiently explored. Examples include POMCPOW (Sunberg and Kochenderfer, 2018) and IPFT (Fischer and Tas, 2020). More recent algorithms combine Progressive Widening with more informed methods for adding new actions: VOMCPOW (Lim et al., 2021) uses Voronoi Optimistic Optimization (Kim et al., 2020) and BOMCP (Mern et al., 2021) uses Bayesian optimization. All of these solvers use UCT-style simulations and Monte Carlo backups. An early line of work, GPS-ABT (Seiler et al., 2015), takes a different approach: It uses Generalized Pattern Search to iteratively select an action subset that is more likely to contain the best action and add it to the set of candidate actions. GPS-ABT uses UCT-style simulations and Bellman backup (following the implementation of ABT (Hoerger et al., 2018; Klimenko et al., 2014)), though the distinction between Monte Carlo and Bellman backup was not clarified nor explored. All of these solvers have been successful in finding good solutions to POMDPs with continuous action spaces, though for a relatively low ($\leq 4)$ dimension.

To compute good strategies for POMDPs with high-dimensional action spaces, we propose a new MCTS-based online POMDP solver, called Adaptive Discretization using Voronoi Trees (ADVT). ADVT is designed for problems with continuous action spaces, while the state and observation spaces can either be discrete or continuous. ADVT contains three key ideas, as briefly described below.

The first key idea of ADVT is a new data structure for action space discretization, called Voronoi tree. A Voronoi tree represents a hierarchical partition of the action space for a single sampled belief. It follows the structure of a Binary Space Partitioning (BSP) tree, but each partitioning hyper-plane is only implicitly maintained and computed based on the Voronoi diagram of a pair of sampled actions, which results in a partitioning that is much more adaptive to the spatial locations of the sampled actions, compared to state-of-the-art methods (Bubeck et al., 2011; Lim et al., 2021; Mansley et al., 2011; Sunberg and Kochenderfer, 2018; Valko et al., 2013). We additionally maintain estimates of the diameters of the cells in the Voronoi tree. These diameters are used in the other two key ideas, namely, action selection and Voronoi tree refinement, as described in the next two paragraphs. The hierarchical structure of the Voronoi tree allows us to estimate the diameters with an efficient sampling-based algorithm that scales well to high-dimensional action spaces. Section 5 provides a more detailed description on the computational and representational advantages of the Voronoi tree.

The second key idea of ADVT is the use of a cell-diameter-aware upper-confidence bound on the values of actions to guide action selection during planning. This bound represents an upper-confidence bound on the values of all actions within a cell, based on the estimated value of the corresponding sampled action and the diameter of the cell. Our bound is a generalization of a bound that was developed for Lipschitz continuum-arm bandit problems  (Wang et al., 2020). It is motivated by the observation that in many continuous action POMDPs for robotics problems, the distance between two actions can often be used as an indication of how similar their values are. Using this observation, ADVT assumes that the action value for a belief is Lipschitz continuous in the action space, which in turn allows us to derive the upper bound. The upper bound helps ADVT to exploit local information (i.e., the estimated value of the representative action of a cell and the cell diameter) with respect to the action value function and bias its search towards the most promising regions of the action space.

The third key idea is a diameter-aware cell refinement rule. We use the estimated diameters of the cells to help ADVT decide if a cell needs further refinement: a larger cell will be split into smaller ones after a small number of simulations, while a smaller will require more simulations before it is split. This helps ADVT to avoid an unnecessarily small partitioning of non-promising regions in the action space.

To further support ADVT in efficiently finding approximately optimal actions, we use a stochastic version of the Bellman backup (Klimenko et al., 2014) rather than the typical Monte-Carlo backup to estimate the values of sampled actions. Stochastic Bellman backups help ADVT to backpropagate the value of good actions deep in the search tree, instead of averaging them out. This strategy of estimating the action values is particularly helpful for problems with sparse rewards.

Aside from continuous action spaces, continuous observation spaces pose an additional challenge for MCTS-based online POMDP solvers. Recent approaches such as POMCPOW and VOMCPOW apply Progressive Widening in the observation space in conjunction with an explicit representation of the sampled beliefs via a set of weighted particles. Due to its simplicity, we adopt POMCPOW’s strategy to handle continuous observation spaces. This enables ADVT to scale to problems with continuous state, action and observation spaces.

Experimental results on a variety of benchmark problems with increasing dimension (up to 12-D) of the action space and problems with continuous observation spaces indicate that ADVT substantially outperforms state-of-the-art methods (Lim et al., 2021; Sunberg and Kochenderfer, 2018). Our C++ implementation of ADVT is available at https://github.com/hoergems/ADVT.

This paper extends our previous work (Hoerger et al., 2022) in three ways: First is the extension of ADVT to handle continuous observation spaces. Experimental results on an additional POMDP benchmark problem demonstrate the effectiveness of ADVT in handling purely continuous POMDP problems. Second is a substantially expanded discussion on the technical concepts of ADVT. And third is an extended ablation study in which we investigate the effectiveness of stochastic Bellman backups when applied to two baseline solvers POMCPOW and VOMCPOW.

A POMDP provides a general mathematical framework for sequential decision making under uncertainty. Formally, it is an 8-tuple $\langle\mathcal{S},\mathcal{A},\mathcal{O},T,Z,R,b_{0},\gamma\rangle$. The robot is initially in a hidden state $s_{0}\in\mathcal{S}$. This uncertainty is represented by an initial belief $b_{0}\in\mathcal{B}$, which is a probability distribution on the state space $\mathcal{S}$, where $\mathcal{B}$ is the set of all possible beliefs. At each step $t\geq 0$, the robot executes an action $a_{t}\in\mathcal{A}$ according to some policy $\pi$. It transitions to a next state $s_{t+1}\in\mathcal{S}$ according to the transition model $T(s_{t},a_{t},s_{t+1})=p(s_{t+1}|s_{t},a_{t})$. For discrete state spaces, $T(s_{t},a_{t},s_{t+1})$ represents a probability mass function, whereas for continuous state spaces, it represents a probability density function. The robot does not know the state $s_{t+1}$ exactly, but perceives an observation $o_{t}\in\mathcal{O}$ according to the observation model $Z(s_{t+1},a_{t},o_{t})=p(o_{t}|s_{t+1},a_{t})$. $Z(s_{t+1},a_{t},o_{t})$ represents a probability mass function for discrete observation spaces, or a probability density function for continuous observation spaces respectively. In addition, it receives an immediate reward $r_{t}=R(s_{t},a_{t})\in\operatorname{\mathbb{R}}$. The robot’s goal is to find a policy $\pi$ that maximizes the expected total discounted reward or the policy value

where the discount factor $0<\gamma<1$ ensures that $V_{\pi}(b)$ is finite and well-defined.

The robot’s decision space is the set $\Pi$ of policies defined as mappings from beliefs to actions. The POMDP solution is then the optimal policy, denoted as $\pi^{*}$ and defined as

In designing solvers, it is often convenient to work with the action value or $Q$-value

where $R(b,a)=\int_{s\in\mathcal{S}}b(s)R(s,a)\mathrm{d}{s}$ is the expected reward of executing action $a$ at belief $b$, while $b_{a}^{o}=\tau(b,a,o)$ is the updated robot’s belief estimate after it performs action ${a\in\mathcal{A}}$ while at belief $b$, and subsequently perceives observation $o\in\mathcal{O}$. The optimal value function is then

A more elaborate explanation is available in (Kaelbling et al., 1998).

Belief trees are convenient data structures to find good approximations to the optimal solutions via sampling-based approaches, which has been shown to significantly improve the scalability of POMDP solving (Kurniawati, 2022). Each node in a belief tree represents a sampled belief. It has outgoing edges labelled by actions, and each action edge is followed by outgoing edges labelled by observations which lead to updated belief nodes. Naïvely, bottom-up dynamic programming can be applied to a truncated belief tree to obtain a near-optimal policy, but many scalable POMDP solvers use more sophisticated sampling strategies to construct a compact belief tree, from which a close-to-optimal policy can be computed efficiently. ADVT uses such a sampling-based approach and belief tree representation too.

Various efficient sampling-based offline and online POMDP solvers have been developed for increasingly complex discrete and continuous POMDPs in the last two decades. Offline solvers (e.g., Bai et al. 2014; Kurniawati et al. 2011, 2008; Pineau et al. 2003; Smith and Simmons 2005) compute an approximately optimal policy for all beliefs first before deploying it for execution. In contrast, online solvers (e.g., Kurniawati and Yadav 2013; Silver and Veness 2010; Ye et al. 2017) aim to further scale to larger and more complex problems by interleaving planning and execution, and focusing on computing an optimal action for only the current belief during planning. For scalability purposes, ADVT follows the online solving approach.

Some online solvers have been designed for continuous POMDPs. In addition to the general solvers discussed in Section 1, some solvers (Agha-Mohammadi et al., 2011; Sun et al., 2015; Van Den Berg et al., 2011, 2012) restrict beliefs to be Gaussian and use Linear-Quadratic-Gaussian (LQG) control (Lindquist, 1973) to compute the best action. This strategy generally performs well in high-dimensional action spaces. However, they tend to perform poorly in problems with large uncertainties (Hoerger et al., 2020).

Last but not least, hierarchical rectangular partitions have been commonly used to discretize action spaces when solving continuous action bandits and MDPs (the fully observed version of POMDPs), such as HOO (Bubeck et al., 2011) and HOOT (Mansley et al., 2011). However, the partitions used in these algorithms are typically predefined, which are less adaptive than Voronoi-based partitions constructed dynamically during the search. On the other hand, Voronoi partitions have been proposed in VOOT (Kim et al., 2020) and VOMCPOW (Lim et al., 2021). However, their partitions are based on the Voronoi diagram of all sampled actions, which makes the computation of cell diameters and sampling relatively complex in high-dimensional action spaces. ADVT is computationally efficient, just like hierarchical rectangular partitions, and yet adaptive, just like the Voronoi partitions, getting the best of both worlds.

In this paper, we consider a POMDP $\mathcal{P}=\langle\mathcal{S},\mathcal{A},\mathcal{O},T,Z,R,b_{0},\gamma\rangle$, where the action space $\mathcal{A}$ is continuous and embedded in a bounded metric space with distance function $d$. Typically, we define the metric space to be a $D$-dimensional bounded Euclidean space, though ADVT can also be used with other types of bounded metric spaces. We further consider the state space $\mathcal{S}$ and observation space $\mathcal{O}$ to be either discrete or continuous.

ADVT assumes that the $Q$-value function is Lipschitz continuous in the action space; that is, for any belief $b\in\mathcal{B}$, there exists a Lipschitz constant $L_{b}$ such that for any actions $a,a^{\prime}\in\mathcal{A}$, we have $\left|Q(b,a)-Q(b,a^{\prime})\right|\leq L_{b}\ d(a,a^{\prime})$. Since generally we do not know a tight Lipschitz constant, in the implementation, ADVT uses the same Lipschitz constant $L$ for all beliefs in $\mathcal{B}$, as discussed in Section 4.1.

ADVT is an anytime online solver for POMDPs. It interleaves belief space sampling and action space sampling to find the best action to perform from the current belief $b\in\mathcal{B}$. The sampled beliefs are maintained in a belief tree, denoted as $\mathcal{T}$, while the sampled actions $\mathcal{A}(b)$ for a belief $b$ are maintained in a Voronoi tree, denoted as $\mathcal{H}(b)$, which is adaptively refined. The Voronoi trees form part of the belief tree in ADVT: they determine the sampled action branches for the belief nodes.

Algorithm 1 presents the overall algorithm of ADVT, with details in the sections below. At each planning step, ADVT follows the MCTS approach of constructing a belief tree by sampling a set of episodes (line 7 in Algorithm 1), starting from the current belief. Details on the belief-tree construction are provided in Section 4. After sampling an episode, the estimated action values $\widehat{Q}(b,a)$ along the sequence of actions selected by the episode are updated using a backup operation (line 10 in Algorithm 1). In addition, ADVT refines the Voronoi tree $\mathcal{H}(b)$ as needed for each belief visited by the episode (line 12 in Algorithm 1), as discussed in Section 5. Once a planning budget is exceeded, ADVT selects an action $a^{*}$ from the current belief acoording to

executes $a^{*}$ in the environment to obtain an observation $o\in\mathcal{O}$, updates the current belief to $b^{\prime}=\tau(b,a^{*},o)$ (line 15-17 in Algorithm 1), and proceeds planning from the updated belief. This process repeats until the robot enters a terminal state or a maximum number of planning steps has been exceeded.

The belief tree $\mathcal{T}$ is a tree whose nodes represent beliefs and the edges are associated with action–observation pairs $(a,o)$, where $a\in\mathcal{A}$ and $o\in\mathcal{O}$. A node $b^{\prime}$ is a child of node $b$ via edge $(a,o$) if and only if $b^{\prime}=\tau(b,a,o)$.

To construct the belief tree $\mathcal{T}$, ADVT interleaves the iterative select-expand-simulate-backup operations used in many MCTS algorithms with adaptive discretization. We assume that we have access to a generative model $G:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}\times\mathcal{O}\times\mathbb{R}$ that simulates the dynamics, observation and reward models. In particular, for a given state $s\in\mathcal{S}$ and action $a\in\mathcal{A}$, we have that $(s^{\prime},o,r)=G(s,a)$, where $(s^{\prime},o)$ is distributed according to $p(s^{\prime},o|s,a)=T(s,a,s^{\prime})Z(s^{\prime},a,o)$, and $r=R(s,a)$. At each iteration, we first select a path starting from the root by sampling an episode $s_{0},a_{0},o_{0},r_{0},s_{1},a_{1},o_{1},r_{1},\ldots$ as follows: We first set the current node $b$ as the root node, and sample $s_{0}$ from $b$. At each step $i\geq 0$, we choose an action $a_{i}\in\mathcal{A}(b)$ for $b$ using an action selection strategy (discussed in Section 4.1) , execute $a_{i}$ from state $s_{i}$ via the generative model $G$ to obtain a next state $s^{\prime}$, an observation $o$ and the immediate reward $r_{i}$. For problems with discrete observation spaces, we set the episode’s next state $s_{i+1}$ and observation $o_{i}$ to $s_{i+1}=s^{\prime}$ and $o_{i}=o$ respectively. For problems with continuous observation spaces, we select $s_{i+1}$ and $o_{i}$ according to an observation sampling strategy, as discussed in Section 4.3. Finally, we update $b$ to $b$’s child node via $(a_{i},o_{i})$. The process terminates when encountering a terminal state or when the child node does not exist; in the latter case, the tree is expanded by adding a new node, and a rollout policy is simulated to provide an estimated value for the new node. In either case, backup operations are performed to update the estimated values for all actions selected by the episode. In addition, new actions are added to $\mathcal{A}(b)$ by refining the associated Voronoi tree $\mathcal{H}(b)$ as needed for each encountered belief. Algorithm 2 presents the pseudo-code for constructing $\mathcal{T}$, while the backup operation and refinement of $\mathcal{H}(b)$ are discussed in Section 4.2 and Section 5, respectively.

For each belief node $b$ in the belief tree, its Voronoi tree $\mathcal{H}(b)$ is a BSP tree for $\mathcal{A}$. Each node in $\mathcal{H}(b)$ consists of a pair $(a,P)$ with $P\subseteq\mathcal{A}$ and $a\in P$ the representative action of $P$, and each non-leaf node is partitioned into two child nodes. The partition of each cell in a Voronoi tree is a Voronoi diagram for two actions sampled from the cell.

To construct $\mathcal{H}(b)$, ADVT first samples an action $a_{0}$ uniformly at random from the action space $\mathcal{A}$, and sets the pair $(a_{0},\mathcal{A})$ as the root of $\mathcal{H}(b)$. When ADVT decides to expand a leaf node $(a,P)$, it first samples an action $a^{\prime}$ uniformly at random from $P\subseteq\mathcal{A}$. ADVT then implicitly constructs the Voronoi diagram between $a$ and $a^{\prime}$ within the cell $P$, splitting it into two regions: One is $P_{1}$, representing the set of all actions $a^{\prime\prime}\in P$ for which the distance $d(a^{\prime\prime},a)\leq d(a^{\prime\prime},a^{\prime})$, and the other is $P_{2}=P\backslash P_{1}$. The nodes $(a,P_{1})$ and $(a^{\prime},P_{2})$ are then inserted as children of $(a,P)$ in $\mathcal{H}(b)$. The leaf nodes of $\mathcal{H}(b)$ form the partition of the action space $\mathcal{A}$ used by belief $b$, while the finite action subset $\mathcal{A}(b)\subset\mathcal{A}$ used to find the best action from $b$ is the set of actions associated with the leaves of $\mathcal{H}(b)$. Figure 1 illustrates the relationship between a belief, the Voronoi tree $\mathcal{H}(b)$ and the partition of $\mathcal{A}$.

Voronoi trees have a number of representational and computational advantages compared to existing partitioning methods, such as hierarchical rectangular partitions (Bubeck et al., 2011; Mansley et al., 2011) or Voronoi diagrams (Kim et al., 2020; Lim et al., 2021). In contrast to hierarchical rectangular partitions, Voronoi trees are much more adaptive to the spatial locations of sampled actions, since the geometries of the cells are induced by the sampled actions. Furthermore, in contrast to Voronoi diagrams, the hierarchical structure of Voronoi trees allows us to derive efficient algorithms for estimating the diameters of the cells (discussed in Section 5.2) and sampling new actions from a cell (detailed in Section 5.3). For Voronoi diagrams the diameter computation can be prohibitively expensive in the context of online POMDP planning, since each sampled action results in a re-partitioning of the action space; thus, the diameters of the cells have to be re-computed from scratch. Voronoi tress combinine a hierarchical representation of the partition with an implicit construction of the cells via sampled actions, thereby achieving both adaptivity and computational efficiency.

The next section describes how ADVT decides which node of $\mathcal{H}(b)$ to expand.

We evaluated ADVT on 5 robotics tasks, formulated as continuous-action POMDPs. The following section provides details regarding the tasks, while Table 1 summarizes the state, action and observation spaces for each problem scenario.