Accelerated Vector Pruning for Optimal POMDP Solvers

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

16 Citations (Scopus)

Abstract

Partially Observable Markov Decision Processes (POMDPs) are powerful models for planning under uncertainty in partially observable domains. However, computing optimal solutions for POMDPs is challenging because of the high computational requirements of POMDP solution algorithms. Several algorithms use a subroutine to prune dominated vectors in value functions, which requires a large number of linear programs (LPs) to be solved and it represents a large part of the total running time. In this paper we show how the LPs in POMDP pruning subroutines can be decomposed using a Benders decomposition. The resulting algorithm incrementally adds LP constraints and uses only a small fraction of the constraints. Our algorithm significantly improves the performance of existing pruning methods and the commonly used incremental pruning algorithm. Our new variant of incremental pruning is the fastest optimal pruning-based POMDP algorithm.
Original languageEnglish
Title of host publicationProceedings of the 31st Conference on Artificial Intelligence, AAAI 2017
PublisherAmerican Association for Artificial Intelligence (AAAI)
Pages3672-3678
Number of pages7
ISBN (Electronic)978-1577357803
Publication statusPublished - 2017
Event31st AAAI Conference on Artificial Intelligence: AAAI 2017 - Hilton San Francisco Union Square, San Francisco, United States
Duration: 4 Feb 201710 Feb 2017
Conference number: 31
https://aaai.org/Conferences/AAAI/aaai17.php

Conference

Conference31st AAAI Conference on Artificial Intelligence
Abbreviated title AAAI Conference on Artificial Intelligence
CountryUnited States
CitySan Francisco
Period4/02/1710/02/17
Internet address

Fingerprint Dive into the research topics of 'Accelerated Vector Pruning for Optimal POMDP Solvers'. Together they form a unique fingerprint.

Cite this