---
title: "Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion"
authors:
  - "Matthijs T. J. Spaan"
  - "Frans A. Oliehoek"
  - "Christopher Amato"
doi: "10.5591/978-1-57735-516-8/IJCAI11-338"
url: "https://ijcai.org/proceedings/2011/338"
pdf: "https://ijcai.org/proceedings/2011/0338.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "2027-2031"
track: ""
keywords:
---

# Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion

Matthijs T. J. Spaan, Frans A. Oliehoek, Christopher Amato

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 2027-2031. DOI: [10.5591/978-1-57735-516-8/IJCAI11-338](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-338)

## Abstract

Planning under uncertainty for multiagent systems can be formalized as a decentralized partially observable Markov decision process. We advance the state of the art for optimal solution of this model, building on the Multiagent A* heuristic search method. A key insight is that we can avoid the full expansion of a search node that generates a number of children that is doubly exponential in the node's depth. Instead, we incrementally expand the children only when a next child might have the highest heuristic value. We target a subsequent bottleneck by introducing a more memory-efficient representation for our heuristic functions. Proof is given that the resulting algorithm is correct and experiments demonstrate a significant speedup over the state of the art, allowing for optimal solutions over longer horizons for many benchmark problems.