Multiagent Simple Temporal Problem: The Arc-Consistency Approach

Shufeng Kong, Jae Hee Lee, Sanjiang Li

Abstract

The Simple Temporal Problem (STP) is a fundamental temporal reasoning problem and has recently been extended to the Multiagent Simple Temporal Problem (MaSTP). In this paper we present a novel approach that is based on enforcing arc-consistency (AC) on the input (multiagent) simple temporal network. We show that the AC-based approach is sufficient for solving both the STP and MaSTP and provide efficient algorithms for them. As our AC-based approach does not impose new constraints between agents, it does not violate the privacy of the agents and is superior to the state-of-the-art approach to MaSTP. Empirical evaluations on diverse benchmark datasets also show that our AC-based algorithms for STP and MaSTP are significantly more efficient than existing approaches.

Introduction

The Simple Temporal Problem (STP) is a cornerstone of AI scheduling and planning, involving the management of time points and interval constraints. When extended to multiagent environments (MaSTP), agents must coordinate shared tasks while maintaining private local schedules.

A Multiagent Simple Temporal Network (MaSTN) where agents Alice, Bob, X, and Y coordinate via shared variables (red nodes).

A significant challenge in MaSTP is preserving agent privacy. Previous state-of-the-art algorithms, such as $D\Delta PPC$, rely on graph triangulation. This technique often introduces new constraints between agents who were not originally connected to "fill in" the graph, forcing them to share more information than necessary. Furthermore, these algorithms can be computationally expensive as problem sizes grow.

The Arc-Consistency Approach

This paper introduces a novel solution based on arc-consistency (AC). Traditionally used for discrete domains, the authors provide a formal proof that enforcing AC is sufficient to solve STPs even though time is continuous. This is possible because STP constraints are convex.

The authors propose two primary algorithms:

  1. ACSTP (Centralized): Iteratively refines variable domains by intersecting them with neighbor constraints, terminating when consistency is reached or an empty domain is found.
  2. DisACSTP (Distributed): Agents run the process locally and only share domains of "shared variables" with direct neighbors. This approach preserves privacy by strictly adhering to the original constraint graph and avoiding the creation of new inter-agent edges.

Empirical Results

The AC-based algorithms were evaluated against benchmarks including scale-free networks, the New York road network, and factory scheduling domains.

Performance comparison of ACSTP against P3C on scale-free and real-world road network datasets, showing significant efficiency gains.

The results demonstrate a massive performance leap over previous state-of-the-art methods ($P^3C$ and $D\Delta PPC$):

  • Efficiency: ACSTP was 100–1000 times faster than $P^3C$ on scale-free graphs and 5–12 times faster on road networks.
  • Distributed Performance: DisACSTP was 5–30 times faster than $D\Delta PPC$ on random multiagent networks and 2–10 times faster on factory scheduling tasks.
  • Scalability: The AC-based approach scales significantly better as the number of agents or external constraints increases, with constraint checks growing much more slowly than triangulation-based methods.

Conclusion

By leveraging arc-consistency, this work provides a more efficient and privacy-preserving framework for solving complex temporal problems. Future research will explore extending this approach to Disjunctive Temporal Problems (DTPs) and dynamic environments where constraints are added or removed on the fly.

Summary updated

Abstract

The Simple Temporal Problem (STP) is a fundamental temporal reasoning problem and has recently been extended to the Multiagent Simple Temporal Problem (MaSTP). In this paper we present a novel approach that is based on enforcing arc-consistency (AC) on the input (multiagent) simple temporal network. We show that the AC-based approach is sufficient for solving both the STP and MaSTP and provide efficient algorithms for them. As our AC-based approach does not impose new constraints between agents, it does not violate the privacy of the agents and is superior to the state-of-the-art approach to MaSTP. Empirical evaluations on diverse benchmark datasets also show that our AC-based algorithms for STP and MaSTP are significantly more efficient than existing approaches.
BibTeX
@inproceedings{kong2018multiagent,
  author = {Shufeng Kong and Jae Hee Lee and Sanjiang Li},
  title = {{Multiagent Simple Temporal Problem: The Arc-Consistency Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12087},
}

Loading related content...

Figure