Topology-based Variable Ordering Strategy for Solving Disjunctive Temporal Problems

Many temporal problems arising in automated planning and scheduling can be expressed as disjunctive temporal problems (DTPs). Most of DTP solvers in the literature treat DTPs as constraint satisfaction problems (CSPs) or satisfiability problems (SATs), and solve them using standard CSP (SAT) techniques. Basically DTPs are represented through logically related topological relations between temporal variables, however, unfortunately little work has been done on exploiting the topological information to direct the search for DTP resolving. According to the "fail-first "(FF) principle for dynamic variable ordering (DVO) heuristics in CSP literature, this paper proposes a DVO which is based on the topological structure of DTP (which is defined to be Disjunctive Temporal Network). Experimental results reveal that the proposed DVO outperforms Minimal Remaining Values heuristics-a DVO that is widely used in existing DTP solvers, especially for the hard and large-scale problems. And, a CSP based procedure with the best of the heuristics wins TSAT++ on most of the test problems.

Authors

• Yuechang Liu
• Yunfei Jiang
• Hong Qian

Keywords

• Desktop publishing
• Job shop scheduling
• Large-scale systems
• Sun
• Strategic planning
• System testing
• Manufacturing processes
• Telescopes
• Orbital robotics
• Robotics and automation
• Heuristic
• Large-scale Problems
• Planning Algorithm
• Constraint Satisfaction Problem
• Planning And Scheduling
• Exact Solution
• Graphical Model
• Current Solution
• Disjunction
• Tree Search
• Consistency Checks
• Negative Cycle
• Graph Metrics
• Number Of Checks
• Current Graph
• temporal reasoning
• disjunctive temporal problem