Partially Observable Markov Decision Processes in Robotics: A Survey

Mikko Lauri; David Hsu; Joni Pajarinen

Source-linked AI summary

Partially Observable Markov Decision Processes in Robotics: A Survey

Mikko Lauri, David Hsu, Joni Pajarinen

arXiv:2209.10342v1Sep 21, 2022cs.ROcs.AIeess.SY

TL;DR

Robotic decision-making must handle incomplete and noisy information, while existing literature lacks a synthesized view of applying POMDPs across robot systems. This survey connects POMDP models and algorithms with six application areas, finding broad effectiveness and favoring scalable sampling-based online planning while identifying challenges in continuous spaces, model acquisition, and safety guarantees.

Problem
Existing surveys cover POMDP algorithms or individual robotics applications, but lack a synthesized view of how to apply POMDPs effectively across different robot systems.
Method
The survey analyzes six robotic application categories and connects their task characteristics with POMDP models, planning algorithms, and future research challenges.
Results
POMDP planning has succeeded across a wide range of robot tasks, with sampling-based online algorithms standing out for scalability in high-dimensional spaces and natural handling of dynamic environments.
Takeaways & Limitations
The survey provides practitioners with task characteristics for deciding when and how to apply POMDPs and gives algorithm designers directions for addressing robotic-system challenges.

Abstract

from arXiv · show

Noisy sensing, imperfect control, and environment changes are defining characteristics of many real-world robot tasks. The partially observable Markov decision process (POMDP) provides a principled mathematical framework for modeling and solving robot decision and control tasks under uncertainty. Over the last decade, it has seen many successful applications, spanning localization and navigation, search and tracking, autonomous driving, multi-robot systems, manipulation, and human-robot interaction. This survey aims to bridge the gap between the development of POMDP models and algorithms at one end and application to diverse robot decision tasks at the other. It analyzes the characteristics of these tasks and connects them with the mathematical and algorithmic properties of the POMDP framework for effective modeling and solution. For practitioners, the survey provides some of the key task characteristics in deciding when and how to apply POMDPs to robot tasks successfully. For POMDP algorithm designers, the survey provides new insights into the unique challenges of applying POMDPs to robot systems and points to promising new directions for further research.

I. INTRODUCTION

POMDPs provide a principled framework for robot decision-making under incomplete information, modeling uncertainty in sensing, actions, transitions, and rewards. This survey connects POMDP foundations and algorithms with diverse robotic applications and their practical challenges.

Motivation: Noisy sensing, imperfect control, changing environments, and inaccurate models make uncertainty intrinsic to many robot systems.Robots may choose actions that gather information for long-term success, not merely maximize short-term reward.
POMDP framework: A POMDP represents incomplete state information, stochastic transitions, noisy observations, rewards, and policies conditioned on action-observation history.Planning uses transition, observation, and reward models to reason about long-term effects and expected discounted reward.
POMDP framework: POMDP planning offers a general probabilistic framework for modeling uncertainty in robot systems and identifying conditions for optimal solutions.Its applicability spans many commonly encountered robot systems.
Survey scope: Existing surveys separately cover POMDP algorithms and individual robotics applications, but a synthesized view of effective cross-robot application is lacking.The survey addresses this gap by relating task characteristics to POMDP modeling and solution approaches.
Survey scope: The survey covers localization and navigation, target search and tracking, autonomous driving, manipulation and grasping, human-robot interaction, and multi-robot coordination.It organizes these applications alongside theoretical foundations, solution algorithms, and future challenges.
Finite-horizon models: A finite-horizon solution is a sequence of belief-to-action policies, with each step updating the belief through the chosen action and received observation.The belief update uses a Bayes filter, while dynamic programming constructs policies for the remaining horizon.

B. Infinite horizon

Infinite-horizon POMDPs model unending tasks with a stationary policy and a discounted objective. Their finite-horizon value functions converge to the unique infinite-horizon optimum, enabling bounded-error approximations.

Infinite-horizon formulation: Infinite-horizon POMDPs represent unending tasks and require 0 ≤γ < 1 so total discounted reward remains well-defined.Because infinitely many decisions remain, the solution is a stationary policy applied at every time step.
Infinite-horizon formulation: The infinite-horizon optimal value function is the unique fixed point of the Bellman equation as the finite horizon tends to infinity.The corresponding optimal policy selects an action maximizing the infinite-horizon action-value function.
Approximation guarantee: δ error is guaranteed by solving a sufficiently large finite horizon when the iteration bound satisfies ϵ < δ(1 −γ)/γ.The resulting policy has approximation error at most δ.

III. POMDP ALGORITHMS

This section introduces POMDP solution algorithms through the Tiger problem, a simple example illustrating decision-making under uncertainty. It contrasts this didactic example with the more dynamic Tag problem.

POMDP solution algorithms compute optimal or approximately optimal value functions and policies.
The Tiger problem illustrates POMDP decision-making with hidden state, risky door-opening actions, and informative listening observations.
The survey uses Tiger because its simplicity clearly illustrates the POMDP principle despite lacking meaningful dynamics.
The Tag problem adds changing robot and opponent locations that affect actions, rewards, and observations.

A. Offline algorithms

Offline algorithms compute policies before execution, using value-function representations based on α-vectors. Exact methods are limited by rapid growth, while point-based methods trade optimality for scalability.

Offline algorithms compute a policy for all possible belief states before policy execution.
Finite-horizon optimal value functions are piecewise linear and convex in the belief state, represented by α-vectors.
Exact offline methods apply dynamic programming to iteratively construct α-vector sets and recover optimal policies.
Exact methods suit small problems with up to a few dozen states, but α-vector growth makes large action and observation spaces infeasible.
Point-based methods maintain one α-vector per selected belief state, reducing representation size compared with exact algorithms.
Point-based algorithms address significantly larger problems by sacrificing optimality, yet remain intractable for very large problems.

B. Online algorithms

Online algorithms interleave planning and execution, searching reachable histories or belief states to select actions for the current belief. Sampling and tree-sparsification techniques improve scalability but can sacrifice guarantees.

Online algorithms compute an optimal or approximately optimal action for the current belief, execute it, observe, and replan.
History trees alternate triangular decision nodes for actions with circular chance nodes for observations.
Tree-search size grows exponentially because depth t contains |A|^t|Ω|^t decision nodes.
POMCP uses selection, expansion, simulation or rollout, and backpropagation to build a sparse search tree with Monte Carlo tree search.
Sampling-based methods avoid explicit belief tracking by propagating state particles through simulated transitions and observations.
POMCPOW extends MCTS for continuous actions and observations, whereas DESPOT searches finite randomly sampled scenarios.
Policy-search algorithms gain scalability by restricting the search space, but often lose the ability to bound solution quality.

C. Heuristics

Heuristics provide inexpensive approximate POMDP solutions by simplifying decision calculations. Their computational savings come with weaker reasoning about long-term effects or solution quality.

Heuristics use simple principles to obtain computationally inexpensive POMDP solutions, without the approximation guarantees of reviewed algorithms.
The greedy policy chooses the action maximizing expected immediate reward but ignores long-term effects and lacks a performance-gap guarantee.
QMDP computes a fully observable MDP value and uses it as an upper bound for the POMDP value function.
QMDP is computationally cheaper than a full POMDP solution but is not well suited when explicit information gathering is required.
OLFC repeatedly computes an optimal open-loop action sequence, executes its first action, updates beliefs from observations, and repeats.
OLFC considers fewer action sequences than closed-loop policies, but no error bound relative to an optimal solution is known.

IV. POMDPS IN ROBOTICS

POMDPs have been widely applied across robotic domains, with application-specific uncertainties and a diverse set of solution algorithms. The survey organizes these applications and algorithms while noting that its overview necessarily omits some details.

The survey examines POMDP planning in localization and navigation, autonomous driving, search and tracking, manipulation, human-robot interaction, and multi-robot coordination.
Table I organizes commonly used robotic POMDP algorithms into point-based, tree search, policy search, and heuristic categories.
The reviewed application domains differ in whether uncertainty arises from the state, dynamics, or perception.
The table provides a rough overview, omitting hierarchical control, application-specific challenges, and methods for handling high-dimensional observations.

A. Localization and Navigation

Localization and navigation involve uncertainty about the robot’s location and environment, often with continuous, dynamic, and partially observed spaces. The survey describes discretization, hierarchical planning, belief-dependent rewards, and specialized methods used to make these problems tractable.

Key sources of uncertainty and challenges: Robot location is uncertain because sensors are noisy and observe only parts of the environment, while the environment’s composition may also be unknown.
Key sources of uncertainty and challenges: Localization, path planning, and path following can be modeled jointly or separately, with planning used to gather information, reach goals, and avoid hazards.
Key sources of uncertainty and challenges: Continuous states, actions, and observations, multimodal beliefs from perceptual aliasing, moving obstacles, changing goals, and dynamic environments make these tasks challenging.
Solution methods: POMDPs are used for high- and low-level localization, path planning, and path following, commonly with discretization and hierarchical models for long horizons.
Solution methods: Hierarchical POMDPs split navigation into high-level waypoint selection and low-level travel, shortening planning horizons and enabling near-real-time replanning.
Solution methods: PLGRIM combines local POMCP search with global QMDP planning, but QMDP is appropriate only when future belief uncertainty can be ignored.

B. Autonomous driving

Autonomous driving uses POMDPs to handle uncertainty from traffic participants, occlusions, and partially observable intentions. Practical approaches discretize or simplify continuous problems and often combine hierarchical high-level decisions with low-level vehicle control.

Key sources of uncertainty and challenges: Autonomous driving must estimate state, predict dynamic objects, and control the vehicle despite occlusions and uncertain intentions of other traffic participants.
Key sources of uncertainty and challenges: Hierarchical control commonly assigns lane changing, distance keeping, and overtaking to high-level planning, while acceleration and steering remain low-level control tasks.
Solution methods: Continuous driving spaces are often discretized, with short horizons, sparse actions, mixed observability, illegal-action pruning, and variable time granularity used for tractability.
Solution methods: Some approaches model traffic participants explicitly, while others evaluate combinations of participant behaviors; with two policies per participant, the latter requires evaluating 2^n combinations.

C. Target search, tracking, and avoidance

Target search, tracking, and avoidance require reasoning about uncertain target behavior, high-dimensional sensing, and interactions with navigation. The survey describes hierarchical, discretized, factorized, continuous-state, and belief-reward methods for managing these challenges.

Key sources of uncertainty and challenges: Search, tracking, and avoidance combine navigation and localization with models of target behavior and sensor uncertainty to gather information or avoid targets.
Key sources of uncertainty and challenges: Target behavior is domain-specific and difficult to predict, while cameras and other sensors can produce high-dimensional observations.
Key sources of uncertainty and challenges: Discretizing multiple target states causes exponential state-space growth because the combined state size equals the product of individual grid sizes.
Solution methods: Common solution strategies include hierarchical control, grid discretization, state factorization, mixed observability, and direct continuous-state planning.
Solution methods: Image-based POMDP methods abstract images into low-dimensional representations rather than using raw images as observations.
Solution methods: Belief-dependent rewards such as negative entropy encourage uncertainty reduction, while submodularity supports computationally cheap greedy policies with performance guarantees.

D. Manipulation and grasping

Robotic manipulation uses POMDPs to plan under noisy sensing, occlusions, uncertain object properties, and continuous robot dynamics. Surveyed solutions simplify these challenges through discretization, particle beliefs, hierarchical decomposition, and closed-loop tactile control.

Key sources of uncertainty and challenges: Unknown, cluttered manipulation environments create uncertainty through noisy sensors, occlusions, and unknown object properties.
Key sources of uncertainty and challenges: POMDP task planning represents high-level choices such as which object to manipulate and which operation to perform.
Solution methods: Discretizing states, actions, and observations can produce tractable POMDPs for manipulation tasks with continuous physical variables.
Solution methods: The full tactile POMDP solution outperforms the QMDP heuristic, indicating that closed-loop information gathering is useful during push-grasping.
Solution methods: A DESPOT-generated imitation policy empirically generalizes to novel objects absent from its training data.
Solution methods: Particle beliefs represent uncertainty over object locations, identities, and scene hypotheses when segmentation and occlusion are uncertain.

E. Human-robot interaction

Human-robot interaction applies POMDPs to infer hidden human intentions and mental states while choosing actions under uncertain, multimodal information. Applications include assistance, communication, social interaction, diagnosis, tutoring, and interactive task execution.

Key sources of uncertainty and challenges: HRI uncertainty arises because human intentions and mental states cannot be directly measured and must be inferred from other data.
Key sources of uncertainty and challenges: Human behavior models represent variables such as mental state, competence, pose, and location to support safety and comfort.
Solution methods: Pearl used a hierarchical POMDP while navigating a nursing home, guiding residents, and answering queries under computational constraints.
Solution methods: POMDP-based HRI models latent user states for monitoring, assistance, interaction, and task-specific prediction.
Solution methods: Communication-aware models let robots ask humans for information or plan bi-directional communication during interaction.
Solution methods: Some systems learn unknown reward or observation models from users by maintaining a finite set of hypothetical POMDPs.

F. Multi-robot coordination

Multi-robot coordination is complicated by asymmetric information and limited communication, since each robot may lack other agents’ private histories. POMDP-based approaches range from shared-belief centralized models to decentralized policies and approximate local coordination.

Key sources of uncertainty and challenges: Limited communication creates asymmetric information because one robot generally cannot know another robot’s action-observation history or predict its action.
Solution methods: Hierarchical multi-robot planning decomposes task macro actions into local feedback controllers that transform initial beliefs toward goals.
Solution methods: When robots can communicate freely, a multi-agent POMDP uses joint action and observation tuples with a shared belief state.
Solution methods: A Dec-POMDP supports decentralized execution without requiring robots to share belief states or other agents’ action-observation histories.
Solution methods: Dec-POMDP methods can be exact or approximate, but their computational complexity limits some approaches to small teams, actions, and observations.
Solution methods: Mapping decentralized coordination to local single-agent problems improves tractability at the cost of losing optimality.
Solution methods: Runtime communication can update beliefs or observations, predict missing teammate data, or periodically exchange policies without centralized planning.

V. CHALLENGES AND FUTURE DIRECTIONS

The survey identifies model acquisition, continuous robot variables, high-dimensional sensing, and safety as central barriers to broader POMDP deployment. It highlights learning-based modeling, continuous-space algorithms, fault-aware planning, and tighter integration of model learning with planning as future directions.

Model uncertainty: Accurate dynamics, observation, and reward models are difficult to acquire, although most reviewed POMDP approaches assume they are given.
Model uncertainty: Learning-based approaches address model uncertainty through imitation learning, belief representation learning, multi-robot reinforcement learning, and Bayesian reinforcement learning.
Continuous state, action, observation, and time: Discretizing continuous states, actions, observations, and time can produce inaccurate solutions, especially in high-dimensional robotic tasks.
Continuous state, action, observation, and time: POMCP and DESPOT handle continuous states and observations through Monte Carlo sampling, but their actions remain discrete.
Safe POMDPs in robotics: Safety-constrained POMDP methods remain limited to a few robotic applications because of computational complexity and gaps between models and real tasks.
Safe POMDPs in robotics: System health monitoring may be integrated with decision-making to support greater fault resiliency in robotics.
Conclusion: Sampling-based online POMDP planning is favored for scalability in high-dimensional spaces and natural handling of dynamic environments.
Conclusion: Future work should integrate POMDP model learning with planning while connecting results to theoretical guarantees for reliable and safe decisions.