Flexibility and Decoupling in the Simple Temporal Problem

Wilson, Michel; Klos, Tomas; Witteveen, Cees; Huisman, Bob

Flexibility and Decoupling in the Simple Temporal Problem

Michel Wilson, Tomas Klos, Cees Witteveen, Bob Huisman

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2422-2427.

Abstract

In this paper we concentrate on finding a suitable metric to determine the flexibility of a Simple Temporal Problem (STP). After reviewing some flexibility metrics that have been proposed, we conclude that these metrics fail to capture the correlation between events specified in the STP, resulting in an overestimation of the available flexibility in the system. We propose to use an intuitively more acceptable flexibility metric based upon uncorrelated time-intervals for the allowed starting times of events in an STP. This metric is shown to be computable in low-polynomial time. As a byproduct of the flexibility computation, we get a decomposition of the STN almost for free: for every possible k-partitioning of the event space, a decomposition can be computed in O(k)-time. Even more importantly, we show that contrary to popular belief, such a decomposition does not affect the flexibility of the original STP.

Michel Wilson, Tomas Klos, Cees Witteveen, and Bob Huisman. 2013. Flexibility and Decoupling in the Simple Temporal Problem. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 2422–2427. https://ijcai.org/proceedings/2013/356

@inproceedings{ijcai2013p356,
  title     = {Flexibility and Decoupling in the Simple Temporal Problem},
  author    = {Wilson, Michel and Klos, Tomas and Witteveen, Cees and Huisman, Bob},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {2422--2427},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/356},
}

TY  - CPAPER
TI  - Flexibility and Decoupling in the Simple Temporal Problem
AU  - Wilson, Michel
AU  - Klos, Tomas
AU  - Witteveen, Cees
AU  - Huisman, Bob
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 2422
EP  - 2427
UR  - https://ijcai.org/proceedings/2013/356
ER  -