Transcript PPT - ConSystLab - University of Nebraska–Lincoln

Consistency Methods for Temporal Reasoning
Lin Xu and Berthe Y. Choueiry
Constraint Systems Laboratory • Department of Computer Science and Engineering, University of Nebraska-Lincoln • {lxu|choueiry}@cse.unl.edu
We propose new efficient algorithms for solving Simple Temporal Problems (STPs)
and Temporal Constraint Satisfaction Problems (TCSPs). Our contributions are:
• Answers to three research questions:
1. Is there a better algorithm than Floyd-Warshall (F-W) to ensure consistency
and minimality of the STP?
2. Is there an efficient consistency algorithm to reduce the size of the TCSP?
3. How can we improve the performance of BT-TCSP, an exponential time
procedure for solving the TCSP?
• Design of new generators for random STPs and TCSPs that guarantee the
existence of at least one solution.
• Evaluation & empirical evidence on benchmarks on random problems
For
STPs,
there
are
efficient
procedures for determining:
 Consistency: F-W, DPC [2], PPC [1].
 Minimality: F-W & PPC [1].
Solving TCSPs is an NP-hard problem.
It requires search (BT-TCSP)
1. Formulate TCSP as a meta-CSP
2. Find all solutions to the meta-CSP
1. Is there a better algorithm for solving STP than the Floyd-Warshall algorithm (F-W)?
We propose STP a new closure algorithm for solving STPs, an adaptation of PPC [1] to temporal networks.
Two parameters for improvements:
• Exploiting the topology the graph: decompose the graph according into its bi-connected
component using the articulation points (AP), and solve each component independently
(cost bounded by size of the largest component). Known technique, but never tested
empirically
• Exploiting the semantics of the temporal constraints: which are convex.
Partial path consistency (PPC): PPC is a closure algorithm, applicable to general CSPs.
It requires triangulation of constraint graph. In general, PPC does not result in the minimal
network. But for convex constraints, it guarantees minimality (just like F-W, but much
cheaper in practice).
STP improves on PPC:
• Operates on the constraint graph as if composed of triangles, not edges
• Automatically decomposes the constraint graph into bi-connected components
• Always cheaper than PPC and F-W
• Best known algorithm for solving STP.
2. Is there an efficient algorithm for filtering the TCSP?
We propose AC, a polynomial-time algorithm that approximates
generalized arc-consistency for the TCSP, which is NP-hard.
Edge Ordering (EdgeOrd): We order the edges using ‘triangle adjacency’ property.
The priority list is a by-product of triangulation. EdgeOrd has two advantages: (1)
localized backtracking (2) automatic decomposition of the constraint graph.
AC: The goal of the AC algorithm is to remove inconsistent intervals from the
domain of the variables of the meta-CSP, as a preprocessing step to search. The
meta-CSP has a unique, global constraint of exponential size. Defining this
constraint requires solving the meta-CSP, which is NP-hard. We use polynomial
number of polynomial-size ternary constraints instead of this global constraint. An in
a given interval that does not satisfy any ternary constraints cannot possibly satisfy
the global constraint. Hence, AC safely can removed from the domain of edge.
Validation by empirical evaluations
We test the following combinations of TCSP-solvers.
One global,
exponential
size constraint
Polynomial number of
polynomial-size ternary
constraints
3. How can we improve performance of BT-TCSP?
We propose:
A. to exploit the existence of articulation points (again!)
B. to eliminate unnecessary STP-consistency checks (NewCyc)
C. a good variable ordering heuristic in BT-TCSP (EdgeOrd)
New cycle check:
checks presence of
new cycles, O (|E |).
We check consistency
of STP only if a new
cycle is added.
Experimental results confirm the significance of our approach. The best TCSPsolver is STP-TCSP (based on STP and using AC, EdgeOrd & NewCyc). It
outperforms the old TCSP-solver (DPC-TCSP) by a factor 500 (median) in the
number of constraint checks.
NewCyc restricts update to the newly formed biconnected component, reducing #CC.
Directions for future research
• Ensure optimality of AC
• Use AC in a lookahead strategy
• Use dynamic bundling to allow BT-TCSP to work on large problems.
References
[1] Ch. Bliek and D. Sam-Haroud. Path Consistency for Triangulated Constraint Graphs. In Proc. of the 16th IJCAI , pages
456-461, Stockholm, Sweden, 1999
[2] R. Dechter, I. Meiri, and J. Pearl. Temporal Constraint Networks. Artificial Intelligence,. 49:61-95, 1991
[3] L. Xu & B.Y. Choueiry, A New Efficient Algorithm for Solving the Simple Temporal Problem, to appear, TIME 03.
[4] L. Xu, Consistency Methods for Temporal Reasoning, MS thesis, ConSystLab, UNL, 2003.
This work is supported by a grant from NASA-Nebraska, NSF CAREER Award #0133568, and a gift from Honeywell Laboratories.