P3C: A New Algorithm for the Simple Temporal Problem

Léon Planken, Roman van der Krogt, Mathijs de Weerdt

The Simple Temporal Problem (STP) is a sub-problem of almost any planning or scheduling problem involving time constraints. An existing efficient method to solve the STP, called Triangle-STP, is based on partial path consistency and starts from a chordal constraint graph. In this paper, we analyse this algorithm and show that there exist instances for which its time complexity is quadratic in the number of triangles in the constraint graph. We propose a new algorithm, P3C, whose worst-case time complexity is is linear in the number of triangles. We show both formally and experimentally that P3C outperforms Triangle-STP significantly.

URL: http://apstwo.st.ewi.tudelft.nl/~planken/icaps08-p3c.pdf

Subjects: 3.6 Temporal Reasoning; 15.2 Constraint Satisfaction

Submitted: Jun 27, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.