A decentralised partially observable Markov decision problem (DecPOMDP) formalises collaborative multi-agent decision making. A solution to a DecPOMDP is a joint policy for the agents, fulfilling an optimality criterion such as maximum expected utility. A crux is that the problem is intractable regarding the number of agents. Inspired by lifted inference, this paper examines symmetries within the agent set for a potential tractability. Specifically, this paper contributes (i) specifications of counting and isomorphic symmetries, (ii) a compact encoding of symmetric DecPOMDPs as partitioned DecPOMDPs, and (iii) a formal analysis of complexity and tractability. This works allows tractability in terms of agent numbers and a new query type for isomorphic DecPOMDPs.
Original languageEnglish
Title of host publication38th Conference on Uncertainty in Artificial Intelligence (UAI 2022), Eindhoven, Netherlands, August 1-5, 2022
Number of pages11
Publication date2022
Publication statusPublished - 2022
EventUAI 2022: 38th Conference on Uncertainty in Artificial Intelligence - Eindhoven University of Technology , Eindhoven, Netherlands
Duration: 01.08.202205.08.2022

Research Areas and Centers

  • Centers: Center for Artificial Intelligence Luebeck (ZKIL)
  • Research Area: Intelligent Systems


Dive into the research topics of 'Lifting in Multi-agent Systems under Uncertainty'. Together they form a unique fingerprint.

Cite this