Publications

| Sorted by Date | Classified by Publication Type | Classified by Research Category |

Bounding the Probability of Resource Constraint Violations in Multi-Agent MDPs

Frits de Nijs, Erwin Walraven, Mathijs M. de Weerdt, and Matthijs T. J. Spaan. Bounding the Probability of Resource Constraint Violations in Multi-Agent MDPs. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 3562–3568, 2017.

Download

pdf [256.6kB]  

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.

Supplementary Material

Supplement

BibTeX Entry

@InProceedings{DeNijs17aaai,
  author =       {Frits de Nijs and Erwin Walraven and Mathijs M. de
                  Weerdt and Matthijs T. J. Spaan},
  title =        {Bounding the Probability of Resource Constraint
                  Violations in Multi-Agent {MDPs}},
  booktitle =    {Proceedings of the 31st AAAI Conference on
                  Artificial Intelligence},
  pages =        {3562--3568},
  year =         2017
}

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Generated by bib2html.pl (written by Patrick Riley) on Thu Feb 29, 2024 16:15:45 UTC