Lifting in Multi-agent Systems under Uncertainty

Braun, Tanya; Gehrke, Marcel; Lau, Florian; Möller, Ralf

Forschungsartikel in Sammelband (Konferenz)

Zusammenfassung

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 their complexity and tractability. This work allows for solving a new optimisation problem that asks for the number of agents needed to satisfy a goal.

Details zur Publikation

Buchtitel: UAI-22 Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence
Veröffentlichungsjahr: 2022
Sprache, in der die Publikation verfasst ist: Englisch
Veranstaltung: digital
Link zum Volltext: https://proceedings.mlr.press/v180/braun22a.html