Applying Local Search To Disjunctive Temporal Problems

Reasoning with temporal information is an important research field of Artificial Intelligence. The Disjunctive Temporal Problem has emerged as a more expressive language for temporal reasoning and scheduling, but because of its disjunctive constraints over events, it has proved difficult to generate feasible solutions efficiently. Thus solving DTP in as little time as possible has captured many researchers’focus: some techniques convert the DTP to a Constraint Satisfaction Problem and solve it by the standard CSP techniques, while the others resort to encoding and solving algorithms for the Propositional Satisfaction Problem. However, there is still room for improvement in conversion, heuristic strategy and searching.Local search techniques have attracted considerable concern in AI, especially the appearance of GSAT demonstrated again that such techniques can be the most effective methods for solving satisfiable problems. However, local search has not yet to be successfully employed in solving DTP. This thesis studies how to generate feasible solutions with local search techniques. Therefore we implement a new constraint weighting algorithm - TSAT, and make some changes to it to solve DTP. We also propose an improved TSAT algorithm to solve DTP-mTSAT, which combines TSAT and DPC. In order to improve the performance, we convert the original problem to a meta-CSP, and generate Simple Temporal Problem with mTSAT in the domain value of each variable.To assess the performance of TSAT, in this thesis we design a series of experiments that run on potassco and TSAT. Based on the random problem generation model, we implement the DTP generator and produce experimental sets. The results finally prove the effectiveness and correctness of TSAT. In the end, we design experiments that run on TSAT and mTSAT, the follows turns out to be more effective, and it also provides a new research direction for DTP solving.