RIFO revisited: Detecting relaxed irrelevance

RIFO, as has been proposed by Nebel et al. (Nebel, Di-mopoulos, and Koehler 1997), is a method that can auto-matically detect irrelevant information in planning tasks. The idea is to remove such irrelevant information as a pre-process to planning. While RIFO has been shown to be useful in a number of domains, its main disadvantage is that it is not completeness preserving. Furthermore, the pre-process of-ten takes more running time than nowadays state-of-the-art planners, like FF, need for solving the entire planning task. We introduce the notion of relaxed irrelevance, concerning actions which are never needed within the relaxation that heuristic planners like FF and HSP use for computing their heuristic values. The idea is to speed up the heuristic func-tions by reducing the action sets considered within the relax-ation. Starting from a sufficient condition for relaxed irrele-vance, we introduce two preprocessing methods for filtering action sets. The first preprocessing method is proven to be completeness-preserving, and is empirically shown to termi-nate fast on most of our testing examples. The second method is fast on all our testing examples, and is empirically safe. Both methods have drastic pruning impacts in some domains, speeding up FF’s heuristic function, and in effect the planning process