Steady-State Strategy Synthesis for Swarms of Autonomous Agents

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00141859" target="_blank" >RIV/00216224:14330/25:00141859 - isvavai.cz</a>

Result on the web

<a href="https://www.ijcai.org/proceedings/2025/16" target="_blank" >https://www.ijcai.org/proceedings/2025/16</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24963/ijcai.2025/16" target="_blank" >10.24963/ijcai.2025/16</a>

Result language

angličtina

Original language name

Steady-State Strategy Synthesis for Swarms of Autonomous Agents

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence

ISBN

9781956792065

ISSN

—

e-ISSN

1045-0823

Number of pages

8

Pages from-to

135-142

Publisher name

International Joint Conferences on Artificial Intelligence

Place of publication

Kalifornie

Event location

Montreal

Event date

Jan 1, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—