Long-distance mutual exclusion for planning

Mutual exclusion (mutex) is a powerful mechanism for search space pruning in planning. However, a serious limitation of mutex is that it cannot specify constraints relating actions and facts across different time steps. In this paper, we propose a new class of mutual exclusions that significantly generalizes mutex and can be efficiently computed. The proposed long-distance mutual exclusion (londex) can capture constraints over actions and facts not only at the same time step but also across multiple steps. As a generalization, londex is much stronger than mutex, and provides a general and effective tool for developing efficient planners. We propose two levels of londex. The first level, londex"1, is derived from individual domain transition graphs (DTGs), and the second level, londex"m, is derived from multiple DTGs by taking into account the interactions among them. Londex constraints provide stronger pruning power but also require a large amount of memory. To address the memory problem, we further develop a virtual realization mechanism in which only a small proportion of londex constraints are dynamically generated as needed during the search. This scheme can save a huge amount of memory without sacrificing the pruning power of londex. For evaluation purposes, we incorporate londex into SATPlan04 and SATPlan06, two efficient SAT-based planners. Our experimental results show that londex"m can significantly improve over londex"1 since the former exploits causal dependencies among DTGs. Our experimental results for various planning domains also show significant advantages of using londex constraints for reducing planning time.