Efficient Methods for Multi-Objective Decision-Theoretic Planning

Diederik Marijn RoijersIJCAI 2015

Introduction

In traditional artificial intelligence and decision-theoretic planning, agents are typically designed to maximize a single scalar reward—such as a score, profit, or success rate. However, real-world scenarios rarely involve a single metric. A forest manager must balance timber yields with ecological preservation, and a mining operation must navigate the fluctuating market values of multiple extracted metals. When objectives conflict, there is no single "best" solution; instead, there is a set of optimal trade-offs.

This paper explores efficient strategies for multi-objective decision-making, specifically focusing on the Convex Coverage Set (CCS). By prioritizing the CCS over the traditional, more exhaustive Pareto front, the research introduces frameworks that significantly reduce computational complexity while maintaining decision-making utility.

The Convex Coverage Set (CCS) vs. Pareto Front

In multi-objective optimization, researchers often seek the Pareto Coverage Set (PCS), which contains every solution where one objective cannot be improved without degrading another. While comprehensive, the PCS can be prohibitively large and computationally expensive to calculate.

This research argues that for many applications, the Convex Coverage Set (CCS) is a superior target. The CCS consists of the solutions that are optimal for some linear combination of objectives. If a decision-maker eventually selects a policy based on a weighted sum of objectives—even if those weights are unknown at the time of planning—the CCS provides all necessary optimal choices. Because the CCS is typically much smaller than the full Pareto front, targeting it allows for more efficient algorithms.

Methodological Frameworks

The paper categorizes multi-objective planning methods into two distinct architectural patterns:

1. Inner Loop Approaches

Inner loop methods embed multi-objective logic directly into the planning algorithm. An example is CMOVE, which adapts the "Variable Elimination" algorithm to pass sets of multi-objective vectors between agents in a coordination graph. These methods are often robust when dealing with a high number of objectives but can struggle as the state space of the problem grows.

2. Outer Loop Approaches: Optimistic Linear Support (OLS)

The primary contribution of this work is the Optimistic Linear Support (OLS) framework. OLS is an "outer loop" method that treats the multi-objective problem as a sequence of single-objective "scalarized" problems. The process follows a specific logic:

  • Weight Selection: It selects a weight vector (e.g., 70% Objective A, 30% Objective B).
  • Single-Objective Solving: It calls a "black-box" single-objective solver to find the optimal policy for those specific weights.
  • Priority Search: It utilizes a priority queue to identify "corner weights"—points where the current set of solutions has the highest uncertainty—and solves those next.
  • Termination: The process continues until it is mathematically guaranteed that no further improvements to the convex hull can be found.

Evaluation and Key Insights

The methods were evaluated across several frameworks, including Multi-Objective Coordination Graphs (MO-CoGs), Multi-Objective MDPs (MOMDPs), and Multi-Objective POMDPs (MOPOMDPs). Key findings include:

  • Solver Agnosticism: OLS is highly flexible because it is independent of the underlying single-objective solver. Any advancement in single-objective planning can be immediately integrated into the OLS framework to improve multi-objective performance.
  • Scaling Trade-offs: A clear divide exists in performance: inner loop methods are better suited for a high number of objectives, whereas outer loop methods like OLS scale significantly better as the problem size (number of agents or states) increases.
  • Memory Efficiency: The outer loop method VELS (Variable Elimination Linear Support) proved to be much more memory-efficient than its inner-loop counterpart, CMOVE, requiring memory resources comparable to standard single-objective elimination.
  • Bounded Approximation: OLS allows for early termination with a "bounded approximation." If computation must stop, the algorithm can quantify the maximum possible error ($\epsilon$), informing the user of the potential value lost by not completing the full search.

Conclusion and Future Work

By focusing on the Convex Coverage Set and leveraging the OLS framework, this research provides a scalable path for complex multi-objective planning. While OLS is highly efficient for a small number of objectives, its efficiency decreases as objectives multiply, suggesting a continued role for inner-loop methods in specific contexts.

Future research directions include addressing fully observable multi-agent MDPs by exploiting "sparse interactions" between agents. Additionally, the author aims to extend these techniques to Dec-POMDPs, where decentralized agents must coordinate their multi-objective trade-offs without a central controller.

Summary updated

BibTeX
@inproceedings{roijers2015efficient,
  author = {Diederik Marijn Roijers},
  title = {{Efficient Methods for Multi-Objective Decision-Theoretic Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure