Steady-State Strategy Synthesis for Swarms of Autonomous Agents

Martin Jonás, Antonín Kucera, Vojtech Kur, Jan MacákIJCAI 2025 · DOI

TL;DR

This paper tackles the challenge of coordinating multiple autonomous agents to achieve collective long-term goals, specifically by ensuring that certain states in their environment are visited with desired frequencies. The authors demonstrate that this multi-agent problem is significantly harder than its single-agent counterpart, requiring more complex strategies and posing computational hurdles. They introduce an efficient incremental algorithm that effectively synthesizes strategies for these swarms, outperforming a naive baseline in practice.

What Problem Does This Paper Address?

Imagine a fleet of delivery drones that need to collectively ensure that specific charging stations are visited with a certain minimum frequency to maintain operational readiness. Or consider a team of robots in a warehouse tasked with inspecting inventory items, where each item needs to be checked periodically. These scenarios fall under the umbrella of "steady-state policy synthesis," which aims to design decision-making policies (strategies) for agents operating in a probabilistic environment (a Markov Decision Process or MDP).

The core problem is to find a strategy profile (a set of strategies, one for each agent) such that the long-run average frequencies of visiting certain states (or groups of states, defined by colors) meet predefined targets. While this problem is well-understood and computationally tractable for a single agent, this paper investigates its extension to multiple autonomous agents. The key challenge is that the collective behavior of multiple agents introduces complexities that don't exist in the single-agent case, making existing solutions insufficient.

Methods

The authors first analyze the fundamental properties of multi-agent steady-state synthesis. They establish that for two or more agents, the power of different types of strategies (full memoryless, memoryless, finite-memory, and general history-dependent) strictly increases. This is a crucial departure from the single-agent case, where memoryless strategies are often sufficient. They also prove that determining whether a desired frequency vector is achievable and evaluating the frequency vector achieved by a given strategy profile are computationally hard problems (PSPACE-hard and coNP-hard, respectively).

To address these challenges, the paper proposes an incremental synthesis algorithm. The core idea is to build the strategy profile for k agents by iteratively adding one agent at a time. Starting with a strategy for one agent, the algorithm then finds a strategy for a second agent that, when combined with the first, best improves the collective performance towards the objective. This process is repeated until all k agents have been assigned a strategy. This incremental approach is designed to avoid the blow-up in complexity that would arise from considering all agents simultaneously. The algorithm relies on solving a series of linear programs, where each program is designed to find a strategy for the next agent that optimizes the collective objective, given the strategies of the already-assigned agents.

Datasets

The authors evaluated their algorithm on randomly generated benchmarks. These benchmarks consist of:

  • Aperiodic graphs: Generated with up to 400 vertices and an edge probability of 0.01.
  • Periodic graphs: Generated with structures resembling cyclic classes, with varying numbers of cyclic classes and vertices per class.
  • Objectives: Randomly generated objectives with up to 30 colors, and target values assigned to each vertex.

The paper does not mention using pre-existing datasets for training or evaluation.

Key Insights and Ideas

  • Multi-agent complexity: The problem of steady-state synthesis becomes significantly harder with multiple agents. The power of different strategy types (memoryless vs. history-dependent) increases with the number of agents, meaning simpler strategies are no longer sufficient.
  • Memory is crucial: Unlike the single-agent case, memoryless strategies are generally insufficient for approximating desired frequency vectors in multi-agent systems.
  • Computational barriers: Evaluating the performance of even simple memoryless strategy profiles is computationally hard, posing a significant obstacle to designing efficient synthesis algorithms.
  • Incremental approach: The proposed incremental algorithm offers a practical solution by building the multi-agent strategy step-by-step, avoiding the combinatorial explosion of considering all agents at once. This approach trades some completeness for efficiency.
  • Strategy sharing is suboptimal: A naive baseline strategy of having all agents share the same strategy is shown to be significantly less effective than the incremental approach, requiring more agents to achieve the desired objectives.

Key Results

  • Complexity Classification: The paper proves that multi-agent steady-state synthesis is PSPACE-hard for general strategies and NP-hard for memoryless and finite-memory strategies, even for simple graph structures.
  • Algorithm Performance: The proposed incremental synthesis algorithm significantly outperforms a naive strategy-sharing baseline. It often requires fewer agents to satisfy the objective and achieves better distances to the objective when the number of agents is insufficient.
  • On average, the incremental algorithm required 10.40 agents compared to 16.65 for the baseline.
  • The algorithm achieved better results on 3163 out of 3248 benchmarks.
  • Efficiency: While the incremental algorithm is computationally more intensive than the baseline (due to solving multiple linear programs), its execution times are still within practical limits (e.g., a maximum of 5.08 seconds on aperiodic benchmarks and 28.88 seconds on periodic benchmarks).

Limitations and Future Work

  • Completeness: The incremental algorithm is not guaranteed to find a solution even if one exists. It trades completeness for efficiency.
  • Non-full MR profiles: The current algorithm focuses on full memoryless profiles. Extending it to handle non-full memoryless profiles is a direction for future work.
  • General infinite-horizon objectives: The paper's focus is on steady-state objectives. Generalizing the approach to other infinite-horizon objectives is also suggested as future research.
  • Gap estimation: The proof of Theorem 1 involves a "gap estimating function" whose asymptotic upper bound is noted as potentially improvable.

Summary updated

BibTeX
@inproceedings{jonas2025steady,
  author = {Martin Jonás and Antonín Kucera and Vojtech Kur and Jan Macák},
  title = {{Steady-State Strategy Synthesis for Swarms of Autonomous Agents}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/16},
}

Loading related content...

Figure