In this paper, we provide a polynomial-time deterministic algorithm, and an even simpler randomized algorithm, for solving a restricted (but very expressive) class of disjunctive temporal problems (DTPs). The general form of a DTP is as follows. We are given a set of events χ = {X_0, X_1... X_N} (X_0 is the "beginning of the world" node and is set to 0 by convention), and a set of constraints C. A constraint c_i ∈ C is a disjunction of the form S_((i,1)) ∨ s_((i,2)) ... s_((i,T_i)). Here, s_((i,j)) (1 ≤ j ≤ T_i) is a simple temporal constraint of the form L_((i,j)) ≤ X_(b_(i,j)) — X_(a_(i,j)) ≤ U_((i,j)) for 0 ≤ a_((i,j)),b_((i,j)) ≤ N. We will first provide a pseudo-polynomial-time randomized algorithm for solving the following restricted class of DTPs (which we will refer to as RDTPs (restricted DTPs)): Any c_i ∈ C is of one of the following types: (Type 1) (L ≤ X_b -X_a ≤ U), (Type 2) (L_1 ≤ X_a ≤ U_1) ∨ (L_2 ≤ X_a ≤ U_2)... (L_(T_i) ≤ X_a ≤ U_(T_i)), (Type 3) (L_1 ≤ X_a ≤ U_1) ∨ (L_2 ≤ X_b ≤ U_2). We will then provide a strongly polynomial-time deterministic algorithm for solving the same problem, and extend the ideas further to provide an even simpler randomized algorithm— the expected running time of which is much less than that of the deterministic algorithm. Our polynomial-time algorithms for solving RDTPs bear important implications on not only being able to handle limited (but very useful) forms of disjunctions in metric temporal reasoning (that would otherwise require an exponential search space), but also in pruning large parts of the search spaces associated with general DTPs.
展开▼
