In traditional artificial intelligence planning, agents are typically designed to maximize a single scalar reward. However, real-world decision-making is rarely unidimensional. Whether planning infrastructure maintenance to balance cost against traffic disruption or navigating a warehouse robot to optimize speed versus battery longevity, agents must navigate competing objectives. Diederik M. Roijers’ dissertation, Multi-objective decision-theoretic planning, addresses this complexity by developing agents capable of handling trade-offs without requiring predefined weights for each priority.
The Challenge of Scalarization
Most AI planning systems assume a scalar reward function. To apply these systems to multi-objective tasks, engineers often "scalarize" the problem upfront by assigning fixed weights to different objectives (e.g., $Utility = 0.7 \times \text{Profit} + 0.3 \times \text{Safety}$). This approach has significant drawbacks:
- Unknown Preferences: Decision-makers often do not know the optimal weights until they understand the available trade-offs.
- Non-linear Utility: If a user's utility function is non-linear, standard linear scalarization fails to capture the optimal policy.
Roijers focuses on the unknown weights scenario and the decision support scenario. The objective is to compute a Coverage Set: a collection of policies such that at least one is optimal for any possible user preference. The research aims to generate these sets efficiently across various environments, including multi-agent coordination, Markov Decision Processes (MDPs), and Partially Observable MDPs (POMDPs).
Methodology: Optimistic Linear Support (OLS)
The primary contribution of this work is the Optimistic Linear Support (OLS) framework. Roijers distinguishes between two algorithmic approaches:
- Inner Loop Methods: These modify the fundamental operators of a solver (e.g., "sum" and "max") to process vectors. While powerful, they are complex to implement and memory-intensive.
- Outer Loop Methods (OLS): This is the proposed modular framework. OLS functions as a "shell" around existing single-objective solvers.
How OLS Operates
OLS treats a single-objective solver as a black-box subroutine. It iteratively selects "corner weights"—specific trade-off points where the current set of policies is most likely to be improved. The framework is "optimistic" because it identifies the weight vector that could potentially reduce the maximum possible utility loss of the current set. This process continues until the algorithm proves that no better policies exist, resulting in a Convex Coverage Set (CCS).
A key advantage of this "outer-loop" approach is modularity. As single-objective solvers improve, the multi-objective planner automatically benefits without requiring internal modifications.
Benchmarks and Evaluation
The OLS framework was evaluated across several diverse domains:
- Multi-objective Coordination Graphs (MO-CoGs): Tested using random graphs and the Mining Day benchmark, which involves balancing the extraction of different resources across multiple locations.
- Maintenance Planning Problem (MPP): A large-scale MOMDP based on real-world infrastructure data, balancing budgetary constraints against traffic delays.
- MOPOMDP Benchmarks: Adapted classic problems like Tiger (balancing reward vs. risk) and Maze20 for multi-objective, partially observable settings.
Key Insights
The Utility-Based Philosophy
Rather than seeking every mathematically "Pareto optimal" point—which can be numerous or even infinite—the research advocates for finding only those points a rational user might actually choose. This leads to the CCS, which is significantly smaller and more computationally efficient to produce than a full Pareto front.
Value Reuse (Hot-Starting)
In sequential problems like MOPOMDPs, Roijers introduced the concept of "hot-starting." By reusing value functions (Alpha-matrices) from previous OLS iterations, the solver avoids starting from scratch when weights shift slightly, drastically reducing computation time.
Results and Scalability
The empirical results demonstrate the efficiency of the OLS approach:
- Speed: In coordination tasks, the OLS-based algorithm (VELS) outperformed state-of-the-art inner-loop methods by a factor of 16 for two-objective problems.
- Scalability: OLS successfully solved Mining Day instances involving up to 1,000 agents, a scale previously considered intractable for multi-objective coordination.
- MOPOMDP Performance: The OLSAR algorithm, the first scalable method for multi-objective POMDPs, achieved convergence an order of magnitude faster than baseline versions by utilizing value reuse.
Limitations and Future Directions
Despite its successes, the framework faces challenges as the number of objectives increases. The number of "corner weights" to evaluate grows exponentially with the dimensionality of the objective space. Additionally, the current framework assumes continuous trade-offs and does not yet accommodate lexicographical preferences (where one objective is strictly prioritized over another).
Future research directions include interactive planning, where the algorithm incorporates human feedback during the search process to prune the search space more effectively and reach optimal decisions faster.
Summary updated