Abstract
Partially-observable Markov decision processes provide a general model for decision theoretic planning problems, allowing trade-offs between various courses of actions to be determined under conditions of uncertainty, and incorporating partial observations made by an agent. Dynamic programming algorithms based on the belief state of an agent can be used to construct optimal policies without explicit consideration of past history, but at high computational cost. In this paper, we discuss how structured representations of system dynamics can be incorporated in classic POMDP solution algorithms. We use Bayesian networks with structured conditional probability matrices to represent POMDPs, and use this model to structure the belief space for POMDP algorithms, allowing irrelevant distinctions to be ignored. Apart from speeding up optimal policy construction, we suggest that such representations can be exploited in the development of useful approximation methods.
Introduction
Planning in real-world environments is inherently complex due to uncertain action outcomes and partial observability. Partially Observable Markov Decision Processes (POMDPs) offer a robust mathematical framework for these problems but are plagued by the "curse of dimensionality." In a standard POMDP with $n$ binary state variables, the state space consists of $2^n$ states. Traditional solution algorithms represent these states explicitly using large vectors and matrices, making computation intractable as the number of variables increases.
This paper addresses this challenge by observing that many variables are often irrelevant to specific decisions. For instance, a robot's decision to use an umbrella should be independent of unrelated environmental variables. By exploiting this problem structure, we can avoid exhaustive state enumeration.
Structured Representations for POMDPs
We propose a framework that replaces explicit state-based representations with compact, structured models:
- Two-Slice Bayesian Networks: System dynamics are represented using a "two-slice" Bayesian network (BN), which models how variables at time $t$ influence those at time $t+1$.
- Tree-Structured CPTs: Within the BN, conditional probability tables (CPTs) are represented as decision trees. This captures "context-specific independence," where a variable's relevance depends on the values of other variables.
- Structured Value Functions ($\alpha$-trees): The value of a policy over the belief space is represented using $\alpha$-functions, which we also model as decision trees.
- Abductive Explanation: The algorithm performs backward reasoning from a reward tree to identify which current variables are necessary to predict future rewards.
- Structured Domination Testing: Classic pruning algorithms (like Monahan’s) are adapted to use these trees. Linear Programming (LP) is performed over the leaves of the trees rather than the entire state space.
Case Study: The Robot Coffee Problem
To illustrate these concepts, we utilize a "Robot Coffee" running example. The environment is defined by variables such as whether it is raining ($R$), if the robot has an umbrella ($U$), if the robot is wet ($W$), if the user wants coffee ($WC$), and if the robot has coffee ($HC$). The robot can perform actions like GetC (get coffee) or TestC (check user preference).
The goal is to deliver coffee when requested while avoiding getting wet or delivering coffee unnecessarily. The reward function is structured to reflect these priorities, as shown in the decision tree representation.
Key Insights and Results
The primary contribution of this work is the ability to ignore irrelevant distinctions. By using tree-based representations, the algorithm automatically collapses the state space into abstract states, effectively merging planning with numerical optimization.
Key results include:
- Computational Efficiency: The number of variables in the Linear Programs used for policy pruning is reduced from the total number of states ($|S|$) to the number of leaves in the value tree. In structured domains, this represents an exponential reduction in complexity.
- Algorithmic Integration: We demonstrate a systematic method for incorporating structured representations into value iteration, proving that compactness can be maintained throughout the planning process.
Limitations and Future Work
While structured representations offer significant gains, they face the challenge of "tree fragmentation." As the planning horizon grows, decision trees can become increasingly fine-grained, potentially reaching the size of the full state space in the worst case.
Future research should focus on:
- Approximation Methods: Pruning low-value branches of the trees could trade minor accuracy for substantial speed increases.
- Advanced Solvers: Adapting more modern POMDP solvers, such as the Witness algorithm, to utilize these structured representations.
Summary updated