Temporal Constraint Satisfaction Problem (TCSP)

t0

t1

t2

[0,3]

[1,5] [7,9]

• Variables correspond to time points

• Constraints retrict allowable distances between time points

• Constraints can be represented as sets of intervals
  • Simple temporal problem (STP)
    • All constraints have at most one interval (TRACTABLE!!!)

• Solution of general TCSP involves enforcing path-constistency
  • Approximations such as loose path consistency can be used to detect inconsistencies

[Dechter, Schwalb, AIJ 1997]

[ 7,20]

[1,12]

[ 7,12]

Previous slide

Next slide

Back to first slide

View graphic version