Multi-objective decision-theoretic planning with Optimistic Linear Support

6^th September 2016, 13:00 Ashton Lecture Theater
Dr. Diederik Roijers
Robert Hooke Building,
Parks Road,
Oxford OX1 3PR

Abstract

Many real-world decision problems require making trade-offs between multiple objectives. However, in some cases, the relative importance of the objectives is not known when the problem is solved, precluding the use of single-objective methods. Instead, multi-objective methods, which compute the set of all potentially optimal solutions, are required.

We propose optimistic linear support (OLS), a generic framework for multi-objective decision problems that computes the convex coverage set (CCS) - the set of all potentially optimal solutions when either the objectives are linearly weighted, or when policies can be stochastic. OLS achieves this by solving the multi-objective decision problems as a series of single-objective decision problems. First, we outline OLS, and show how it applies to any multi-objective decision problem, and show how the runtime and space complexity, as well as the quality bounds of OLS-based methods can be established. Second, we show how OLS can be used to create a novel point-based planning method for Multi-Objective POMDPs, which we call OLS with Alpha Reuse (OLSAR). A key insight underlying OLSAR is that the policies and value functions produced while solving a series of single-objective POMDPs can be reused to more quickly solve single-objective POMDPs, later in the series. Finally, our current work on multiple objectives in the context of social robotics is briefly discussed.