Multiagent Simple Temporal Problem: The Arc-Consistency Approach

Shufeng Kong, Jae Hee Lee, Sanjiang Li

Temporal reasoning is a cornerstone of automated planning and scheduling. At AAAI-18, researchers presented a significant advancement in solving the Simple Temporal Problem (STP) and its multiagent variant (MaSTP). By leveraging Arc-Consistency (AC)—a technique traditionally associated with finite-domain problems—the authors developed algorithms that are not only faster but also more privacy-preserving than existing triangulation-based methods.

The MaSTP Framework

The Simple Temporal Problem (STP) involves managing a set of time-point variables subject to linear constraints (e.g., "Task B must start between 10 and 20 minutes after Task A ends"). In a multiagent setting (MaSTP), these variables are distributed among several agents. Each agent maintains a set of private local constraints while coordinating on shared global constraints where their schedules intersect.

Figure 1: A multiagent temporal network illustrating local and shared constraints between agents Alice, Bob, X, and Y.

Traditional solutions rely on Path-Consistency (PC) or triangulation methods like $P^3C$. These approaches often suffer from high computational complexity ($O(n^3)$) and privacy leaks. Triangulation can force agents to establish direct constraints with others they do not naturally interact with, exposing sensitive scheduling data.

From Path-Consistency to Arc-Consistency

The core contribution of this work is the theoretical proof that enforcing Arc-Consistency is sufficient to solve the STP. While AC is generally considered a "weak" consistency check in general Constraint Satisfaction Problems (CSPs), the authors demonstrate that for the specific linear structure of STPs, the AC-closure results in minimal domains. This means that simply ensuring every pair of variables is consistent with their direct constraints is enough to find the full solution space.

This insight led to two primary algorithms:

  1. ACSTP (Centralized): An iterative algorithm with $O(en)$ complexity, where $e$ is the number of constraints and $n$ is the number of variables. It avoids the overhead of graph triangulation entirely.
  2. DisACSTP (Distributed): A multiagent version where agents only exchange domain information for shared variables. This preserves the "agent graph" structure, ensuring privacy by avoiding the creation of "phantom" constraints between unrelated agents.

Experimental Results

The researchers evaluated their approach against state-of-the-art methods across various benchmarks, including synthetic scale-free graphs and real-world data like the New York Road Network.

Figure 4: Performance comparison showing ACSTP outperforming P³C by up to three orders of magnitude across different network topologies.

The results were striking. In centralized tests, ACSTP was consistently 100 to 1,000 times faster than the state-of-the-art $P^3C$ algorithm. Even on sparse networks like the New York road dataset, ACSTP maintained a 5–12x speed advantage. In the multiagent domain, DisACSTP outperformed the leading distributed algorithm, D$\Delta$PPC, by factors of 2 to 30, demonstrating superior scalability as the number of agents and tasks increased.

Conclusion

By revisiting Arc-Consistency, this research provides a more efficient and private path for multiagent temporal coordination. The move away from triangulation-based methods removes a significant bottleneck in both computation and privacy. While the current framework focuses on simple constraints, future work aims to extend these AC-based methods to handle disjunctive constraints, dynamic updates, and temporal uncertainty.

Reference: Kong, S., Lee, J. H., & Li, S. (2018). Multiagent Simple Temporal Problem: The Arc-Consistency Approach. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1).

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},
}
Figure