Projects per year
Abstract
Multi-agent planning problems with constraints on global resource consumption occur in several domains. Existing algorithms for solving Multi-agent Markov Decision Processes can compute policies that meet a resource constraint in expectation, but these policies provide no guarantees on the probability that a resource constraint violation will occur. We derive a method to bound constraint violation probabilities using Hoeffding's inequality. This method is applied to two existing approaches for computing policies satisfying constraints: the Constrained MDP framework and a Column Generation approach. We also introduce an algorithm to adaptively relax the bound up to a given maximum violation tolerance. Experiments on a hard toy problem show that the resulting policies outperform static optimal resource allocations to an arbitrary level. By testing the algorithms on more realistic planning domains from the literature, we demonstrate that the adaptive bound is able to efficiently trade off violation probability with expected value, outperforming state-of-the-art planners.
Original language | English |
---|---|
Title of host publication | Proceedings of the 31st Conference on Artificial Intelligence, AAAI 2017 |
Publisher | American Association for Artificial Intelligence (AAAI) |
Pages | 3562-3568 |
Number of pages | 7 |
ISBN (Print) | 978-1577357803 |
Publication status | Published - 2017 |
Event | 31st AAAI Conference on Artificial Intelligence: AAAI 2017 - Hilton San Francisco Union Square, San Francisco, United States Duration: 4 Feb 2017 → 10 Feb 2017 Conference number: 31 https://aaai.org/Conferences/AAAI/aaai17.php |
Conference
Conference | 31st AAAI Conference on Artificial Intelligence |
---|---|
Abbreviated title | AAAI Conference on Artificial Intelligence |
Country/Territory | United States |
City | San Francisco |
Period | 4/02/17 → 10/02/17 |
Internet address |
Keywords
- Markov Decision Process
- Resource constraints
- Planning under uncertainty
Fingerprint
Dive into the research topics of 'Bounding the probability of resource constraint violations in multi-agent MDPs'. Together they form a unique fingerprint.Projects
- 1 Finished
-
GCP: Gaming beyond the Copper Plate
de Weerdt, M. M., Spaan, M. T. J., de Vries, L. J., Witteveen, C., van der Sluis, L., Walraven, E. M. P., Philipsen, R. M., Morales Espana, G. A. & Ramirez Elizondo, L. M.
1/10/14 → 31/10/18
Project: Research