Applications of the Heuristics Based on Problem Structure to Disjunctive Temporal Problems

Many temporal problems arising in intelligent 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. They are proved to be very powerful in solving DTPs, however, unfortunately little work has been done on utilizing topological information encoded in DTPs to guide the search for solutions. Presented in this paper is a heuristics which is extracted via the analysis of DTPs topological structure. The heuristics tries to design qualitative and quantitative criteria for selecting those “best” values for current variables, and based on that a dynamic variable ordering heuristics is obtained for selecting the next “best” variable to try. The proposed strategy can be called “topology based value selection” strategy （TVS for short） for value selection and “topology based variable ordering” （TVO） for variable ordering. The approach is implemented based on a graphical model of DTPs defined in this paper, the disjunctive temporal network （DTN）. Experimental results show that the both TVS and TVO strategy can effectively reduce the visited nodes for DTP solving. Compared with similar techniques in the literature, TVS behaves comparatively to removal of subsumed variable （RSV）, and TVO performs usually better than minimal remaining values （MRV） heuristics even by one order-of-magnitude. Moreover, experimental results reveal that an efficient DTP solver—DTN-DTP can be obtained which incorporates other CSP techniques with TVO and TVS.