Bounded Approximations for Linear Multi-Objective Planning Under Uncertainty


  • Diederik Roijers University of Amsterdam
  • Joris Scharpff Delft University of Technology
  • Matthijs Spaan Delft University of Technology
  • Frans Oliehoek University of Amsterdam
  • Mathijs de Weerdt Delft University of Technology
  • Shimon Whiteson University of Amsterdam



multiple objectives, Markov decision process, planning


Planning under uncertainty poses a complex problem in which multiple objectives often need to be balanced. When dealing with multiple objectives, it is often assumed that the relative importance of the objectives is known a priori. However, in practice human decision makers often find it hard to specify such preferences, and would prefer a decision support system that presents a range of possible alternatives. We propose two algorithms for computing these alternatives for the case of linearly weighted objectives. First, we propose an anytime method, approximate optimistic linear support (AOLS), that incrementally builds up a complete set of ε-optimal plans, exploiting the piecewise linear and convex shape of the value function. Second, we propose an approximate anytime method, scalarised sample incremental improvement (SSII), that employs weight sampling to focus on the most interesting regions in weight space, as suggested by a prior over preferences. We show empirically that our methods are able to produce (near-)optimal alternative sets orders of magnitude faster than existing techniques.




How to Cite

Roijers, D., Scharpff, J., Spaan, M., Oliehoek, F., de Weerdt, M., & Whiteson, S. (2014). Bounded Approximations for Linear Multi-Objective Planning Under Uncertainty. Proceedings of the International Conference on Automated Planning and Scheduling, 24(1), 262-270.