Towards a Unified View of Social Laws with Instantaneous Actions

Alexander Tuisov, Evgeny Mishlyakov, Alexander Shleyfman, Erez KarpasIJCAI 2025 · DOI

TL;DR

This paper introduces a more general framework for verifying "social laws" in multi-agent systems. Their new compilation method can handle a wider range of planning problems, including those with numeric variables and complex action preconditions, while maintaining state-of-the-art performance. This work paves the way for integrating social laws into more sophisticated AI planning scenarios.

What Problem Does This Paper Address?

In multi-agent systems, where multiple autonomous agents operate in a shared environment, it's common for their actions to interfere with each other, potentially preventing them from achieving their individual goals. "Social laws" are sets of rules designed to implicitly coordinate agent behavior and prevent such conflicts, much like traffic laws guide human drivers. A crucial property of these social laws is "robustness": they must guarantee that every agent can still achieve its goal, regardless of the other agents' plans.

The challenge lies in efficiently verifying whether a given social law is indeed robust. Previous approaches have successfully reduced this verification problem to classical or numeric AI planning tasks. However, these methods were limited in the types of planning problems they could handle, particularly concerning the expressivity of action preconditions (e.g., allowing negations) and the integration of numeric variables. This paper aims to bridge this gap by proposing a more general compilation technique that can handle a broader spectrum of multi-agent planning formalisms.

Methods

The core contribution of this paper is a novel compilation technique that transforms the social law robustness verification problem into a single-agent planning problem. This new compilation is more general than prior work in several key ways:

  • Unified Framework: It can handle both classical and numeric multi-agent planning formalisms.
  • Expressive Preconditions: It supports action preconditions expressed using first-order logic with equality, allowing for negations and more complex logical relationships.
  • External Interference Handling: The details of how actions interfere with each other are treated as independent and handled by an external procedure, making the compilation adaptable.
  • Instantaneous Actions: The compilation is designed for planning problems where actions are instantaneous.

The compilation works by creating multiple copies of the original problem's variables: "local" copies for each agent and a "global" copy to emulate joint execution. It then constructs a complex planning problem with auxiliary flags and specialized actions. These actions simulate different outcomes of an agent's action: success, failure due to precondition violation, or waiting. The compiled problem is designed such that a solvable plan in the compiled problem corresponds to a scenario where the social law is not robust (i.e., a counterexample exists). Conversely, an unsolvable compiled problem indicates that the social law is robust.

Datasets

The paper evaluates their approach using benchmarks adapted from the "Competition of Distributed and Multi-Agent Planners" and the "Numeric track of IPC 2023." These domains include:

  • GRID: Agents navigate a grid, with a social law enforcing directional rules and collision avoidance. Both classical and numeric versions are used.
  • ZENOTRAVEL: Agents (aircraft) transport individuals between cities, with a social law assigning individuals to appropriate aircraft. Both classical and numeric versions are used.
  • BLOCKS WORLD: Agents (robotic arms) pick and stack blocks, requiring coordination for collective objectives.
  • DRIVERLOG: Agents (drivers) transport packages, where social laws are noted as difficult to make robust due to dependencies.
  • MARKET TRADER: Agents (camels) trade goods between markets.
  • EXPEDITION: Agents (sleds) navigate networks, managing supplies and capacity.

The paper notes that they do not employ the numeric compilation by Nir et al. [2023] directly because it requires manual problem adjustment.

Key Insights and Ideas

  • Generality is Key: The ability to handle more expressive action preconditions (like negations) and numeric variables significantly broadens the applicability of social laws in AI planning.
  • Compilation as Verification: The core idea of reducing social law robustness verification to a planning problem remains powerful, but the new compilation makes it applicable to a wider class of problems.
  • Performance Trade-off: While increased generality might intuitively suggest a performance hit, the authors demonstrate that their approach maintains comparable performance to previous state-of-the-art methods.
  • Foundation for Future Work: This work is presented as a step towards integrating planning-based social laws with research on modal logics of norm compliance, suggesting a richer theoretical foundation for agent coordination.

Key Results

The empirical evaluation compares their "new" compilation against an "old" compilation (from Karpas et al., 2017) on various domains. The key findings are:

  • Comparable Performance: The new compilation achieves comparable geometric mean runtimes to the older method.
  • Increased Coverage: The new compilation verifies two more instances with social laws in the classical ZENOTRAVEL domain.
  • Slightly Slower: The new compilation is noted as being slightly slower overall, which is attributed to its increased generality.
  • Fewer Counterexamples: The new compilation finds one less counterexample in the DRIVERLOG domain.

Limitations and Future Work

  • Limitations: The paper focuses on instantaneous actions. The compilation requires that the negation of action preconditions can be efficiently computed. The authors acknowledge that the increased generality might lead to more challenging planning problems, as seen in the slightly slower performance in some cases.
  • Future Work: The authors suggest that this work is a first step towards integrating planning-based social laws with research on social norms and modal logic, opening up new avenues for research in multi-agent systems. They also highlight the potential for applying this compilation to richer planning formalisms.

Summary updated

BibTeX
@inproceedings{tuisov2025towards,
  author = {Alexander Tuisov and Evgeny Mishlyakov and Alexander Shleyfman and Erez Karpas},
  title = {{Towards a Unified View of Social Laws with Instantaneous Actions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/963},
}

Loading related content...

Figure