Multiagent Simple Temporal Problem: The Arc-Consistency Approach
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.
Cite
Text
Kong et al. "Multiagent Simple Temporal Problem: The Arc-Consistency Approach." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.12087Markdown
[Kong et al. "Multiagent Simple Temporal Problem: The Arc-Consistency Approach." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/kong2018aaai-multiagent/) doi:10.1609/AAAI.V32I1.12087BibTeX
@inproceedings{kong2018aaai-multiagent,
title = {{Multiagent Simple Temporal Problem: The Arc-Consistency Approach}},
author = {Kong, Shufeng and Lee, Jae Hee and Li, Sanjiang},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {6219-6226},
doi = {10.1609/AAAI.V32I1.12087},
url = {https://mlanthology.org/aaai/2018/kong2018aaai-multiagent/}
}