Research output: Scientific - peer-review › Conference contribution

**Accelerated Vector Pruning for Optimal POMDP Solvers.** / Walraven, Erwin; Spaan, Matthijs.

Research output: Scientific - peer-review › Conference contribution

Walraven, E & Spaan, M 2017, Accelerated Vector Pruning for Optimal POMDP Solvers. in *Proceedings of the 31st Conference on Artificial Intelligence, AAAI 2017.* American Association for Artificial Intelligence (AAAI), pp. 3672-3678, 31st AAAI Conference on Artificial Intelligence, San Francisco, United States, 4/02/17.

Walraven, E., & Spaan, M. (2017). Accelerated Vector Pruning for Optimal POMDP Solvers. In *Proceedings of the 31st Conference on Artificial Intelligence, AAAI 2017 *(pp. 3672-3678). American Association for Artificial Intelligence (AAAI).

Walraven E, Spaan M. Accelerated Vector Pruning for Optimal POMDP Solvers. In Proceedings of the 31st Conference on Artificial Intelligence, AAAI 2017. American Association for Artificial Intelligence (AAAI). 2017. p. 3672-3678.

@inbook{69e95bade12f45c998fa1351476b7e03,

title = "Accelerated Vector Pruning for Optimal POMDP Solvers",

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.",

author = "Erwin Walraven and Matthijs Spaan",

year = "2017",

pages = "3672--3678",

booktitle = "Proceedings of the 31st Conference on Artificial Intelligence, AAAI 2017",

publisher = "American Association for Artificial Intelligence (AAAI)",

address = "United States",

}

TY - CHAP

T1 - Accelerated Vector Pruning for Optimal POMDP Solvers

AU - Walraven,Erwin

AU - Spaan,Matthijs

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 3672

EP - 3678

BT - Proceedings of the 31st Conference on Artificial Intelligence, AAAI 2017

PB - American Association for Artificial Intelligence (AAAI)

ER -

ID: 32868683