Temporal CSP

From Glossary

Jump to: navigation, search

A temporal constraint satisfaction problem (TCSP) is a constraint satisfaction problem that involves a set of variables LaTeX: \{x_1,\dots , x_n\} having continuous or discrete domains; each variable represents a time point. Each constraint is represented by a set of intervals LaTeX: \{I_1, \dots , I_k\}=\{[a_1,b_1], \dots , [a_k,b_k]\}.

A unary constraint LaTeX: T_i restricts the domain of variable LaTeX: x_i to the given set of intervals; that is, it represents the disjunction LaTeX: (a_1\leq x_i\leq b_1) \vee \dots \vee >(a_k\leq x_i\leq b_k) .

A binary constraint LaTeX: T_{ij} restricts the permissible values for the distance LaTeX: x_j-x_i; it represents the disjunction LaTeX: (a_1\leq x_j-x_i\leq b_1) \vee \dots \vee >(a_k\leq x_j-x_i\leq b_k) .

In canonical form, all intervals of a constraint are pair-wise disjoint.

Personal tools