Steady-State Strategy Synthesis for Swarms of Autonomous Agents

D 2025

Steady-State Strategy Synthesis for Swarms of Autonomous Agents

JONÁŠ, Martin; Antonín KUČERA; Vojtěch KŮR a Jan MAČÁK

Základní údaje

Originální název

Steady-State Strategy Synthesis for Swarms of Autonomous Agents

Autoři

JONÁŠ, Martin; Antonín KUČERA; Vojtěch KŮR a Jan MAČÁK

Vydání

Kalifornie, Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, od s. 135-142, 8 s. 2025

Nakladatel

International Joint Conferences on Artificial Intelligence

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00141859

Organizační jednotka

Fakulta informatiky

ISBN

978-1-956792-06-5

DOI

https://doi.org/10.24963/ijcai.2025/16

EID Scopus

2-s2.0-105021839663

Klíčová slova anglicky

Agent-based and Multi-agent Systems: MAS: Multi-agent planning; Planning and Scheduling: PS: Distributed and multi-agent planning; Planning and Scheduling: PS: Markov decisions processes

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 4. 2026 11:07, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Steady-state synthesis aims to construct a policy for a given MDP D such that the long-run average frequencies of visits to the vertices of D satisfy given numerical constraints. This problem is solvable in polynomial time, and memoryless policies are sufficient for approximating an arbitrary frequency vector achievable by a general (infinite-memory) policy. We study the steady-state synthesis problem for multiagent systems, where multiple autonomous agents jointly strive to achieve a suitable frequency vector. We show that the problem for multiple agents is computationally hard (PSPACE or NP hard, depending on the variant), and memoryless strategy profiles are insufficient for approximating achievable frequency vectors. Furthermore, we prove that even evaluating the frequency vector achieved by a given memoryless profile is computationally hard. This reveals a severe barrier to constructing an efficient synthesis algorithm, even for memoryless profiles. Nevertheless, we design an efficient and scalable synthesis algorithm for a subclass of full memoryless profiles, and we evaluate this algorithm on a large class of randomly generated instances. The experimental results demonstrate a significant improvement against a naive algorithm based on strategy sharing.

Návaznosti

MUNI/A/1666/2024, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 25

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 25

Přiložené soubory

ijcai_2025-paper_2066-accepted.pdf Verze souboru

Citovat

JONÁŠ, Martin; Antonín KUČERA; Vojtěch KŮR a Jan MAČÁK. Steady-State Strategy Synthesis for Swarms of Autonomous Agents. Online. In James Kwok. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Kalifornie: International Joint Conferences on Artificial Intelligence, 2025, s. 135-142. ISBN 978-1-956792-06-5. Dostupné z: https://doi.org/10.24963/ijcai.2025/16.

@inproceedings{2514147,
   author = {Jonáš, Martin and Kučera, Antonín and Kůr, Vojtěch and Mačák, Jan},
   address = {Kalifornie},
   booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence},
   doi = {https://doi.org/10.24963/ijcai.2025/16},
   editor = {James Kwok},
   keywords = {Agent-based and Multi-agent Systems: MAS: Multi-agent planning; Planning and Scheduling: PS: Distributed and multi-agent planning; Planning and Scheduling: PS: Markov decisions processes},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Kalifornie},
   isbn = {978-1-956792-06-5},
   pages = {135-142},
   publisher = {International Joint Conferences on Artificial Intelligence},
   title = {Steady-State Strategy Synthesis for Swarms of Autonomous Agents},
   url = {https://www.ijcai.org/proceedings/2025/16},
   year = {2025}
}

TY  - CONF
ID  - 2514147
AU  - Jonáš, Martin - Kučera, Antonín - Kůr, Vojtěch - Mačák, Jan
PY  - 2025
TI  - Steady-State Strategy Synthesis for Swarms of Autonomous Agents
PB  - International Joint Conferences on Artificial Intelligence
CY  - Kalifornie
SN  - 9781956792065
KW  - Agent-based and Multi-agent Systems: MAS: Multi-agent planning
KW  - Planning and Scheduling: PS: Distributed and multi-agent planning
KW  - Planning and Scheduling: PS: Markov decisions processes
UR  - https://www.ijcai.org/proceedings/2025/16
N2  - Steady-state synthesis aims to construct a policy for a given MDP D such that the long-run average frequencies of visits to the vertices of D satisfy given numerical constraints. This problem is solvable in polynomial time, and memoryless policies are sufficient for approximating an arbitrary frequency vector achievable by a general (infinite-memory) policy. We study the steady-state synthesis problem for multiagent systems, where multiple autonomous agents jointly strive to achieve a suitable frequency vector. We show that the problem for multiple agents is computationally hard (PSPACE or NP hard, depending on the variant), and memoryless strategy profiles are insufficient for approximating achievable frequency vectors. Furthermore, we prove that even evaluating the frequency vector achieved by a given memoryless profile is computationally hard. This reveals a severe barrier to constructing an efficient synthesis algorithm, even for memoryless profiles. Nevertheless, we design an efficient and scalable synthesis algorithm for a subclass of full memoryless profiles, and we evaluate this algorithm on a large class of randomly generated instances. The experimental results demonstrate a significant improvement against a naive algorithm based on strategy sharing.
ER  -

JONÁŠ, Martin; Antonín KUČERA; Vojtěch KŮR a Jan MAČÁK. Steady-State Strategy Synthesis for Swarms of Autonomous Agents. Online. In James Kwok. \textit{Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence}. Kalifornie: International Joint Conferences on Artificial Intelligence, 2025, s.~135-142. ISBN~978-1-956792-06-5. Dostupné z: https://doi.org/10.24963/ijcai.2025/16.

Přehled o publikaci