Point-Based Planning for Multi-Objective POMDPs

Diederik Marijn Roijers, Shimon Whiteson, Frans A. OliehoekIJCAI 2015 · OpenReview

Introduction

In many real-world autonomous systems, agents must navigate environments with hidden information while simultaneously balancing multiple conflicting objectives. For instance, a search-and-rescue robot must locate survivors (Objective A) while managing limited battery life (Objective B) in a partially observable environment. These scenarios are formally modeled as Multi-Objective Partially Observable Markov Decision Processes (MOPOMDPs).

A common approach to solving MOPOMDPs is to "scalarize" the objectives by assigning weights to each. However, when these weights are unknown or dynamic, the agent must pre-calculate a Convex Coverage Set (CCS)—a collection of policies that contains at least one optimal solution for every possible weighting. Calculating the CCS is computationally intensive because it requires solving multiple POMDPs, which are themselves notoriously difficult to solve.

The OLSAR Framework

The authors propose OLSAR (Optimistic Linear Support with Alpha Reuse), an algorithm designed to compute the CCS significantly faster than current state-of-the-art methods. OLSAR integrates three core innovations:

  1. Optimistic Linear Support (OLS): Instead of solving for arbitrary weights, OLS uses a priority queue to select weights where the potential for finding a better policy is highest. It focuses on the "corner weights" of the current value function where the gap between the known lower bound and an optimistic upper bound is largest.
  2. OLSAR-Compliant Perseus (OCPerseus): The authors modified the Perseus point-based solver to return $\alpha$-matrices. These matrices represent the multi-objective value of a policy across all states, allowing the algorithm to evaluate policies across all objectives simultaneously without additional computational overhead.
  3. Alpha Reuse: This is the primary breakthrough. When OLSAR moves to a new weight, it reuses the $\alpha$-matrices from previous iterations as a starting point. Because optimal policies for similar weights are often related, this "warm start" allows the solver to converge rapidly, often confirming optimality in a single step.
Optimistic Linear Support (OLS) identifies weights where the potential for finding a better policy is highest by examining the gap (Δ) between the current lower bound and an optimistic upper bound.

Experimental Results

OLSAR was evaluated against standard benchmarks, including modified versions of the Tiger problem (2 and 3 objectives) and a 20-state navigation maze (MO-Maze20).

The results demonstrate that OLSAR consistently outperforms existing methods in both speed and accuracy. On the 3-objective Tiger problem, OLSAR converged in approximately 2 seconds—ten times faster than versions without alpha reuse. In the more complex MO-Maze20 task, OLSAR reached a low error rate in under 300 minutes, whereas competing methods failed to converge even after 11 hours of runtime.

Performance comparison of OLSAR against other methods across three benchmarks. OLSAR (red) consistently achieves lower error (ε) in significantly less runtime compared to Random Sampling (RS) or standard OLS.

Conclusion

OLSAR represents a significant advancement in multi-objective planning under uncertainty. By intelligently reusing previously computed value functions and prioritizing high-impact weights, it makes the calculation of Convex Coverage Sets feasible for more complex problems. While currently focused on linear scalarization, future work may extend these techniques to non-linear preferences and constrained POMDPs, where specific objectives must be maintained above a safety threshold.

Summary updated

BibTeX
@inproceedings{roijers2015point,
  author = {Diederik Marijn Roijers and Shimon Whiteson and Frans A. Oliehoek},
  title = {{Point-Based Planning for Multi-Objective POMDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=UbVpDLiszT},
}
Figure