Bounded approximations for linear multi-objective planning under uncertainty

Diederik M. Roijers, Joris Scharpff, Matthijs T.J. Spaan, Frans A. Oliehoek, Mathijs M. De Weerdt, Shimon Whiteson

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

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 exactly, 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, thereby demonstrating that our methods provide sensible approximations in stochastic multi-objective domains.

Original languageEnglish
Title of host publicationBNAIC 2014
Subtitle of host publicationProceedings of the 26th Benelux Conference on Artificial Intelligence
EditorsF. Grootjen, M. Otworowska, J. Kwisthout
PublisherIpskamp BV
Pages169-170
Number of pages2
Publication statusPublished - 1 Jan 2014
Event26th Benelux Conference on Artificial Intelligence, BNAIC 2014: 26th Benelux Conference on Artificial Intelligence - Nijmegen, Netherlands
Duration: 6 Nov 20147 Nov 2014
Conference number: 26
http://bnaic2014.org/

Publication series

NameBelgian/Netherlands Artificial Intelligence Conference
ISSN (Print)1568-7805

Conference

Conference26th Benelux Conference on Artificial Intelligence, BNAIC 2014
Country/TerritoryNetherlands
CityNijmegen
Period6/11/147/11/14
Internet address

Fingerprint

Dive into the research topics of 'Bounded approximations for linear multi-objective planning under uncertainty'. Together they form a unique fingerprint.

Cite this