Constrained multiagent Markov decision processes: a taxonomy of problems and algorithms

Frits de Nijs, Erwin Walraven, Mathijs M. de Weerdt, Matthijs T.J. Spaan

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)


In domains such as electric vehicle charging, smart distribution grids and autonomous warehouses, multiple agents share the same resources. When planning the use of these resources, agents need to deal with the uncertainty in these domains. Although several models and algorithms for such constrained multiagent planning problems under uncertainty have been proposed in the literature, it remains unclear when which algorithm can be applied. In this survey we conceptualize these domains and establish a generic problem class based on Markov decision processes. We identify and compare the conditions under which algorithms from the planning literature for problems in this class can be applied: whether constraints are soft or hard, whether agents are continuously connected, whether the domain is fully observable, whether a constraint is momentarily (instantaneous) or on a budget, and whether the constraint is on a single resource or on multiple. Further we discuss the advantages and disadvantages of these algorithms. We conclude by identifying open problems that are directly related to the conceptualized domains, as well as in adjacent research areas.

Original languageEnglish
Pages (from-to)955-1001
Number of pages47
JournalJournal of Artificial Intelligence Research
Publication statusPublished - 8 Mar 2021


  • Markov decision processes
  • Multiagent Systems

Cite this