Oliehoek, Frans A 
ORCID: 0000-0003-4372-5055, Spaan, Matthijs TJ and Witwicki, Stefan
(2015)
Influence-Optimistic Local Values for Multiagent Planning --- Extended
Version.
CoRR, abs/15.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1502.05443v2.pdf - Unspecified Download (703kB) |
Abstract
Recent years have seen the development of methods for multiagent planning under uncertainty that scale to tens or even hundreds of agents. However, most of these methods either make restrictive assumptions on the problem domain, or provide approximate 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. To allow for meaningful benchmarking through measurable quality guarantees on a very general class of problems, this paper introduces a family of influence-optimistic upper bounds for factored decentralized partially observable Markov decision processes (Dec-POMDPs) that do not have factored value functions. Intuitively, we derive bounds on very large multiagent planning problems by subdividing them in sub-problems, and at each of these sub-problems making optimistic assumptions with respect to the influence that will be exerted by the rest of the system. We numerically compare the different upper bounds and demonstrate how we can achieve a non-trivial guarantee that a heuristic solution for problems with hundreds of agents is close to optimal. Furthermore, we provide evidence that the upper bounds may improve the effectiveness of heuristic influence search, and discuss further potential applications to multiagent planning.
| Item Type: | Article |
|---|---|
| Additional Information: | Long version of IJCAI 2015 paper (and extended abstract at AAMAS 2015) |
| Uncontrolled Keywords: | cs.AI, cs.AI, cs.SY, I.2.11 |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 12 Apr 2016 11:15 |
| Last Modified: | 17 Dec 2022 02:58 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3000443 |
Share
Share
