Skip to Main content Skip to Navigation
Theses

Mathematical programming methods for decentralized POMDPs

Abstract : In this thesis, we study the problem of the optimal decentralized control of a partially observed Markov process over a finite horizon. The mathematical model corresponding to the problem is a decentralized POMDP (DEC-POMDP). Many problems in practice from the domains of artificial intelligence and operations research can be modeled as DEC-POMDPs. However, solving a DEC-POMDP exactly is intractable (NEXP-hard). The development of exact algorithms is necessary in order to guide the development of approximate algorithms that can scale to practical sized problems. Existing algorithms are mainly inspired from POMDP research (dynamic programming and forward search) and require an inordinate amount of time for even very small DEC-POMDPs. In this thesis, we develop a new mathematical programming based approach for exactly solving a finite horizon DEC-POMDP. We use the sequence form of a control policy in this approach. Using the sequence form, we show how the problem can be formulated as a mathematical progam with a nonlinear object and linear constraints. We thereby show how this nonlinear program can be linearized to a 0-1 mixed integer linear program (MIP). We present two different 0-1 MIPs based on two different properties of a DEC-POMDP. The computational experience of the mathematical programs presented in the thesis on four benchmark problems (MABC, MA-Tiger, Grid Meeting, Fire Fighting) shows that the time taken to find an optimal joint policy is one or two orders or magnitude lesser than the exact existing algorithms. In the problems tested, the time taken drops from several hours to a few seconds or minutes.
Document type :
Theses
Complete list of metadata

Cited literature [78 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/tel-01748545
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 11:37:52 AM
Last modification on : Tuesday, April 24, 2018 - 1:52:08 PM
Long-term archiving on: : Friday, September 14, 2018 - 7:37:32 AM

File

SCD_T_2008_0092_ARAS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01748545, version 1

Collections

Citation

Raghav Aras. Mathematical programming methods for decentralized POMDPs. Other [cs.OH]. Université Henri Poincaré - Nancy 1, 2008. English. ⟨NNT : 2008NAN10092⟩. ⟨tel-01748545⟩

Share

Metrics

Record views

93

Files downloads

92