Backtracking Algorithms for Disjunctions of Temporal Constraints

AAAI 1998

TL;DR

This paper introduces and evaluates a suite of backtracking algorithms for a generalized form of temporal constraint satisfaction problems (TCSPs) that include disjunctions. They demonstrate that a forward checking with backjumping (FC-BJ) algorithm, combined with a minimum remaining values heuristic, significantly outperforms simpler methods, especially in identifying "hard" problem instances.

What Problem Does This Paper Address?

Temporal constraint satisfaction problems (TCSPs) are crucial for tasks like planning, scheduling, and managing spatio-temporal data. Traditional TCSPs often deal with simple constraints like "event A must happen before event B plus a delay." However, real-world scenarios frequently involve more complex, disjunctive constraints, such as "either event A must happen before event B plus a delay, OR event C must happen before event D plus another delay." These disjunctions make the problem significantly harder to solve. This paper tackles the challenge of efficiently checking the consistency of sets of these generalized temporal constraints, which involve disjunctions of inequalities between variables.

Methods

The authors extend the framework of Simple Temporal Problems (STPs) to handle disjunctive temporal constraints of the form $x_1 - y_1 \le r_1 \lor \dots \lor x_n - y_n \le r_n$. They implement and compare four backtracking algorithms: basic backtracking (BT), backjumping (BJ), forward checking (FC), and forward checking with backjumping (FC-BJ). A key innovation is the adaptation of FC-BJ to this temporal domain, which involves maintaining dependency pointers to identify the root causes of inconsistencies during constraint propagation. They also incorporate the Minimum Remaining Values (MRV) heuristic, which prioritizes variables with the fewest available options, to guide the search.

Datasets

The authors generated random sets of temporal constraint problems for their experiments. These problems are characterized by four parameters: the number of constrained variables ($n$), the number of disjuncts per disjunction ($k$), the number of disjunctions ($m$), and the maximum integer value ($L$) for constants. They specifically focused on problems with $k=2$ disjuncts per disjunction, as this class is known to be NP-complete and relevant to planning and scheduling.

Key Insights and Ideas

  • Disjunctions are the bottleneck: The introduction of disjunctive constraints significantly increases the complexity of temporal reasoning.
  • FC-BJ shines with temporal disjunctions: The FC-BJ algorithm, particularly when combined with the MRV heuristic, proves to be the most efficient for this problem class, outperforming simpler backtracking and backjumping approaches.
  • Dependency tracking is crucial: To effectively implement backjumping in the presence of constraint propagation (like forward checking), it's essential to track dependencies between constraints to identify the true source of inconsistencies.
  • The "hard region" is key: Similar to other NP-complete problems, temporal constraint satisfaction exhibits a "phase transition" where problems become significantly harder to solve. This "hard region" is not where problems are perfectly balanced between having solutions and no solutions, but rather where there are very few, if any, solutions.

Key Results

  • Algorithm Performance: FC-BJ+MRV consistently performed the fewest consistency checks and visited the fewest search nodes across various problem sizes. Basic backtracking (BT) was the least efficient.
  • Hard Region Identification: The hardest problems were found to occur when the ratio of disjunctions to variables ($r$) is between 6 and 7. This "hard region" is where the proportion of satisfiable problems drops sharply from nearly 100% to near 0%.
  • Narrowing Hard Region: The hard region becomes narrower as the number of variables increases.
  • Transition to Insoluble: For ratios $r > 7$, problems tend to be almost entirely unsatisfiable, and algorithms can efficiently detect dead-ends.

Limitations and Future Work

  • Limitations: The paper notes that while FC-BJ+MRV is effective, the difference between it and FC+MRV was marginal in their experiments. The theoretical analysis of consistency checks between FC and FC-BJ could not establish a definitive ordering.
  • Future Work: The authors plan to explore local search algorithms (like min-conflicts and GSAT) for this problem class. They also aim to develop more sophisticated tie-breaking heuristics for variable ordering and discover even more efficient algorithms for determining the consistency of disjunctive temporal constraints.

Summary updated

BibTeX
@inproceedings{1998backtracking,
  title = {{Backtracking Algorithms for Disjunctions of Temporal Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure