Constrained Multiagent Markov Decision Processes: a Taxonomy of Problems and Algorithms

Frits de Nijs, Erwin Walraven, Mathijs Michiel de Weerdt, Matthijs T. J. SpaanJAIR 2021 · OpenReview

TL;DR

This paper provides a comprehensive survey and taxonomy of algorithms for constrained multiagent Markov decision processes (CMMDPs). It clarifies how different problem characteristics (like constraint strictness, observability, and communication) dictate the choice of algorithm, offering a much-needed guide for researchers and practitioners in this complex field.

What Problem Does This Paper Address?

In many real-world scenarios, multiple intelligent agents must coordinate their actions to achieve goals while sharing limited resources. Think of autonomous warehouses with robots competing for charging stations, or electric vehicles coordinating their charging to avoid overloading the power grid. These scenarios are characterized by:

  • Multiple Agents: Several independent decision-makers.
  • Shared Resources: Agents rely on common assets (e.g., bandwidth, power, physical space).
  • Uncertainty: The environment's state and the outcomes of actions are not perfectly known.
  • Constraints: The use of shared resources is limited, requiring careful planning to avoid violations.

While numerous algorithms exist for these CMMDPs, it's often unclear which algorithm is best suited for a given problem. This paper aims to bridge that gap by providing a structured understanding of the problem space and the available solution approaches.

Methods

The paper's core contribution is a taxonomy of CMMDP problems and algorithms. It achieves this by:

  1. Conceptualizing CMMDPs: Defining a generic problem class based on Markov Decision Processes, highlighting key properties that differentiate problems. These properties include:
  2. Constraint Strictness: Soft (met in expectation) vs. Hard (must be met).
  3. Connectivity: Whether agents can reliably communicate during execution (connected vs. disconnected).
  4. Observability: Whether the state is fully or partially observable.
  5. Constraint Timespan: Instantaneous (per time step) vs. Budget (over the entire horizon).
  6. Resource Scope: Single vs. multiple resources.
  7. Categorizing Algorithms: Grouping existing algorithms based on how they handle these properties, particularly focusing on:
  8. Resource Preallocations: Offline methods that assign resources to agents beforehand.
  9. Online and Hybrid Methods: Approaches that involve coordination and decision-making during execution.
  10. Analyzing Trade-offs: Discussing the advantages and disadvantages of different algorithmic approaches in relation to the problem properties.

Datasets

Not discussed in the paper. The paper focuses on a theoretical survey and taxonomy of algorithms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • No One-Size-Fits-All: The paper strongly emphasizes that the "best" algorithm is highly dependent on the specific characteristics of the CMMDP problem. Understanding these characteristics is crucial for effective algorithm selection.
  • Soft vs. Hard Constraints: Soft constraints (met in expectation) are significantly easier to handle algorithmically, often allowing for polynomial-time solutions. Hard constraints, however, pose a much greater challenge, often requiring approximations or specialized algorithms.
  • Partial Observability is a Major Hurdle: Algorithms that handle partial observability in CMMDPs are significantly more complex and less scalable, especially when combined with hard constraints.
  • Communication is Key (But Not Always Available): Connected domains allow for more sophisticated online coordination, while disconnected domains necessitate preallocation strategies.
  • The Power of Linear Programming: Many CMMDP algorithms leverage linear programming (LP) formulations, either directly or as a basis for more complex techniques like column generation. This highlights LP's role in handling resource constraints.

Key Results

The paper doesn't present new empirical results but rather synthesizes existing knowledge. Its primary "result" is the structured taxonomy and the clear identification of:

  • Algorithm Suitability: Which algorithms are appropriate for which combinations of problem properties (e.g., deterministic preallocations for hard constraints, online methods for connected domains).
  • Research Gaps: Areas that are under-explored, such as dealing with hard instantaneous constraints in partially observable domains, or combining online and offline methods effectively.

Limitations and Future Work

The authors acknowledge several limitations and point towards promising future research directions:

  • Hard Constraints: There's a need for more efficient methods to handle hard constraints, especially in conjunction with partial observability.
  • Realistic Constraints: Current algorithms often assume discounted costs, which isn't always realistic. Future work should explore models that drop this assumption.
  • Hybrid Approaches: Combining the strengths of online and offline methods for better performance and adaptability is an open area.
  • Decoupling Level: The current agent-level decoupling might be too restrictive. Exploring group-based or other forms of agent interaction modeling could be beneficial.
  • Benchmark Problems: The development of challenging and realistic benchmark problems is crucial for advancing the field and enabling direct comparison of algorithms.
  • Inter-agent Coordination: Integrating CMMDPs with other forms of agent coordination beyond resource sharing is largely unexplored.

Summary updated

Abstract

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.
BibTeX
@article{nijs2021constrained,
  author = {Frits de Nijs and Erwin Walraven and Mathijs Michiel de Weerdt and Matthijs T. J. Spaan},
  title = {{Constrained Multiagent Markov Decision Processes: a Taxonomy of Problems and Algorithms}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  url = {https://openreview.net/forum?id=nqOUGjalfQT},
}
Figure