Factored Upper Bounds for Multiagent Planning Problems under Uncertainty with Non-Factored Value Functions

Oliehoek, Frans A.; Spaan, Matthijs T. J.; Witwicki, Stefan J.

Factored Upper Bounds for Multiagent Planning Problems under Uncertainty with Non-Factored Value Functions

Frans A. Oliehoek, Matthijs T. J. Spaan, Stefan J. Witwicki

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 1645-1650.

Abstract

Nowadays, multiagent planning under uncertainty scales to tens or even hundreds of agents. However, current methods either are restricted to problems with factored value functions, or provide solutions without any guarantees on quality. Methods in the former category typically build on heuristic search using upper bounds on the value function. Unfortunately, no techniques exist to compute such upper bounds for problems with non-factored value functions, which would additionally allow for meaningful benchmarking of methods of the latter category. To mitigate this problem, this paper introduces a family of influence-optimistic upper bounds for factored Dec-POMDPs without factored value functions. We demonstrate how we can achieve firm quality guarantees for problems with hundreds of agents.

Frans A. Oliehoek, Matthijs T. J. Spaan, and Stefan J. Witwicki. 2015. Factored Upper Bounds for Multiagent Planning Problems under Uncertainty with Non-Factored Value Functions. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 1645–1650. https://ijcai.org/proceedings/2015/235

@inproceedings{ijcai2015p235,
  title     = {Factored Upper Bounds for Multiagent Planning Problems under Uncertainty with Non-Factored Value Functions},
  author    = {Oliehoek, Frans A. and Spaan, Matthijs T. J. and Witwicki, Stefan J.},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {1645--1650},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/235},
}

TY  - CPAPER
TI  - Factored Upper Bounds for Multiagent Planning Problems under Uncertainty with Non-Factored Value Functions
AU  - Oliehoek, Frans A.
AU  - Spaan, Matthijs T. J.
AU  - Witwicki, Stefan J.
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 1645
EP  - 1650
UR  - https://ijcai.org/proceedings/2015/235
ER  -