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.
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:
- 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.
- 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.
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