Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.5591/978-1-57735-516-8/IJCAI11-338 | IJCAI |
Keywords | Field | DocType |
key insight,heuristic function,full expansion,optimal solution,multiagent a,longer horizon,optimal heuristic search,heuristic search method,benchmark problem,search node,incremental expansion,highest heuristic value | Bottleneck,Heuristic,Mathematical optimization,Incremental heuristic search,Partially observable Markov decision process,Computer science,Beam search,Multi-agent system,Artificial intelligence,Consistent heuristic,Machine learning,Speedup | Conference |
Citations | PageRank | References |
21 | 0.88 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthijs T.J. Spaan | 1 | 863 | 63.84 |
| Frans A. Oliehoek | 2 | 397 | 40.32 |
| Christopher Amato | 3 | 479 | 35.66 |