Simplifying Planning Tasks with Fact-Level Relevance Analysis

Abstract

Planning problems described in formal languages often contain information that is irrelevant to reaching the specified goal, either by design (to account for multiple possible goals) or as a result of partially automated construction. Consequently, modern planners prune (some) extraneous information by performing safe relevance analysis of state variables prior to search, improving search performance. We show that much more aggressive pruning is possible by reasoning about relevance not at the level of variables, but rather variable *values*, i.e. *facts*. Our approach iteratively identifies relevant facts whenever they appear in the task goal or in the precondition of a relevant action, and identifies relevant actions whenever they achieve a relevant fact (rather than when they simply modify a relevant variable). This already reduces task size relative to variable-level analysis, but it also offers several opportunities for further algorithmic improvements. We formally prove that fact-level relevance analysis, and each subsequent algorithmic improvement we introduce, preserves all shortest optimal plans, without introducing new ones. We show empirically that our approach significantly reduces task size and consequently planning time across a wide range of planning tasks.