Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions
Muhammad Suhail Saleem, Rishi Veerapaneni, Maxim Likhachev · 2025
Read Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions by Muhammad Suhail Saleem, Rishi Veerapaneni, Maxim Likhachev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00285.txt.
Introduction
Muhammad Suhail Saleem, Rishi Veerapaneni, and Maxim Likhachev tackle slow planning for robots that must act with partial knowledge, in a paper from 2025. Solvers for such tasks work with beliefs, which are odds over what state the world is in.
Working out how a belief changes after an act can be very costly when it needs physics checks or ray casts. The authors put off those costly steps and lean on value guesses instead, in lazy forms of two known solvers. Tests on touch based pose tasks and rough ground travel showed much faster plans with little loss in quality.
Catalog record
| CREATOR | Muhammad Suhail Saleem, Rishi Veerapaneni, Maxim Likhachev |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-00285
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions Muhammad Suhail Saleem, Rishi Veerapaneni, Maxim Likhachev Abstract Heuristic search solvers like RTDP-Bel and LAO* have proven effective for computing optimal and bounded sub-optimal solutions for Partially Observable Markov Decision Processes (POMDPs), which are typically formulated as belief MDPs. A belief represents a probability distribution over possible system states. Given a parent belief and an action, computing belief state transitions involves Bayesian updates that combine the transition and observation models of the POMDP to determine successor beliefs and their transition probabilities. However, there is a class of problems, specifically in robotics, where computing these transitions can be prohibitively expensive due to costly physics simulations, raycasting, or expensive collision checks required by the underlying transition and observation models, leading to long planning times. To address this challenge, we propose Lazy RTDP-Bel and Lazy LAO*, which defer computing expensive belief state transitions by leveraging Q-value estimation, significantly reducing planning time. We demonstrate the superior performance of the proposed lazy planners in domains such as contact-rich manipulation for pose estimation, outdoor navigation in rough terrain, and indoor navigation with a 1-D LiDAR sensor. Additionally, we discuss practical Q-value estimation techniques for commonly encountered problem classes that our lazy planners can leverage. Our results show that lazy heuristic search methods dramatically improve planning speed by postponing expensive belief transition evaluations while maintaining solution quality. 1 Introduction Partially Observable Markov Decision Processes (POMDPs) provide a principled framework for decision-making under uncertainty and have been widely employed in various robotics domains, including autonomous navigation and manipulation tasks ( Brechtel, Gindele, and Dillmann 2014 ; Pajarinen and Kyrki 2017 ) . As the true state of the system is not directly observable, POMDPs maintain a probability distribution over possible system states at any given time, referred to as belief states. They are commonly formulated and solved as a Markov Decision Process (MDP) in the belief space. However, solving POMDPs is notoriously challenging due to the belief space growing exponentially with each additional state variable (curse of dimensionality), as well as with the planning horizon (curse of history) ( Kaelbling, Littman, and Cassandra 1998 ) . Search-based solvers like RTDP-Bel ( Bonet and Geffner 2009 ) and LAO* ( Hansen and Zilberstein 2001 ) leverage heuristics to focus computational efforts on promising regions of the belief space, efficiently converging to optimal or bounded suboptimal solutions. Although powerful and effective in many problems, their applicability still remains limited—particularly in real-world robotics problems. One of the many reasons for this is the inherent assumption that belief transitions are readily available. Computing transitions in the belief space, i.e., determining the successor beliefs and their probabilities given the current belief over the system state and an action, involves Bayesian updates that combine the transition and observation models of the underlying POMDP. However, in many robotics applications, this computation poses a significant bottleneck due to the high computational cost of querying these models. For instance, outdoor robot navigation may require high-fidelity physics simulations to predict action outcomes, while contact-rich manipulation tasks often involve expensive collision checks to model expected interactions. These operations are expensive to query, even for a single system state. Since the belief state is a distribution over the system states, computing the transitions from a belief state would involve querying these operations for every state in (the support of) the belief. Since in a typical problem we can expect to search over thousands of belief states, the total cost of computing belief transitions becomes prohibitively expensive, limiting the practicality of POMDP-based solutions for such applications. To mitigate this challenge, we propose lazy heuristic search solvers for POMDPs, which defer expensive belief state transition computations until necessary. Specifically, we introduce two novel algorithms: Lazy RTDP-Bel and Lazy LAO*. These methods leverage Q -value estimation to identify the most promising action from a belief state, and only the transition corresponding to the most promising action is computed. The belief state transitions for other actions are postponed until the search deems these actions necessary, i.e., have the potential to improve the current solution. By postponing these expensive evaluations and only computing them when needed, we save significant computation time. We show that the Q -value estimates leveraged by our lazy planners are equivalent to heuristic functions and are readily available for common problems, particularly in robotics. Moreover, if the Q -value estimates are conservative, then the proposed lazy planners, like their vanilla counterparts, are guaranteed to converge to the optimal solution. We demonstrate the effectiveness of our proposed lazy planners on three robotics problems i) Manipulation for pose estimation using contacts, ii) Indoor navigation with a 1D LiDAR sensor, and iii) Outdoor rough terrain navigation. Belief transition computations for each of these domains are expensive due to them requiring mesh-to-mesh collision checks, ray casting operations, and physics-based simulations, respectively. Results presented in Section 5 , demonstrate the superior performance of the lazy algorithms on the abovementioned problems, significantly improving planning efficiency while maintaining solution quality. 2 Background In this manuscript, we introduce the concept of laziness in the context of Goal-POMDPs ( Bertsekas 2012 ) , though it naturally extends to reward-based formulations. 2.1 Goal-POMDPs Formally, a discrete Goal-POMDP is defined by the tuple \langle\mathcal{S},\mathcal{A},\mathcal{Z},G,\mathcal{T},\mathcal{O},c,b_{0}\rangle , where \mathcal{S} , \mathcal{A} , and \mathcal{Z} are finite non-empty sets representing the state space, action space, and observation space respectively. G\subseteq\mathcal{S} is the set of goal states. The transition model \mathcal{T}(s,a,s^{\prime})=p(s^{\prime}|s,a) defines the probability of transitioning to state s^{\prime} when executing action a from state s , while the observation model \mathcal{O}(s^{\prime},a,z)=p(z|s^{\prime},a) gives the probability of observing z upon entering s^{\prime} via action a . The cost function c(s,a) determines the cost of executing action a from state s , and b_{0} is the initial belief state, i.e., the distribution over possible initial states. We assume that goal states g\in G are cost-free, absorbing, and fully observable ( z_{g}\in\mathcal{Z} denotes the observation made from a goal state) : (i) c(g,a)=0,\forall,a\in\mathcal{A} , (ii) \mathcal{T}(g,a,g)=1 , and (iii) \mathcal{O}(g,a,z_{g})=1 for all a\in\mathcal{A} , with \mathcal{O}(s,a,z_{g})=0 for s\notin G . POMDPs are commonly solved by reformulating them as completely observable MDPs over the belief space. A belief state b is a probability distribution over states, where b(s) represents the probability of being in state s . Although the system state is not directly observable, we can compute belief updates that capture the effects of actions and observations on the belief state. The belief update after executing action a from belief b is given by b_{a}(s)=P(s|b,a)=\sum_{s^{\prime}\in\mathcal{S}}\mathcal{T}(s^{\prime},a,s)b(s^{\prime}) (1) Similarly, the probability of observing z after taking action a from b is, b_{a}(z)=P(z|b,a)=\sum_{s\in\mathcal{S}}b_{a}(s)\mathcal{O}(s,a,z) (2) Then, we can write the belief update when executing a from b and observing z as b_{a}^{z}(s)=\mathcal{O}(s,a,z)b_{a}(s)/b_{a}(z)\quad\text{if }\,b_{a}(z)\neq 0 (3) This formulation transforms the POMDP into a fully observable belief MDP, where the transition function is given by P(b_{a}^{z}|b,a)=b_{a}(z) . Consequently, reaching a goal state in the original POMDP translates to reaching a goal belief b_{g} , where b_{g}(s)=0 for all s\notin G . The objective of the problem is to compute a belief state policy from the initial belief b_{0} to a goal belief b_{g} while minimizing the expected cost. The Bellman equation for the belief MDP