Introduction
In complex problem-solving domains, state-space search often suffers from a "combinatorial explosion." Traditional Explanation-Based Learning (EBL) systems, such as PRODIGY or STATIC, attempt to mitigate this by learning search control rules. However, these systems face significant hurdles: learning often occurs too late in the search tree, explaining failures requires computationally expensive exhaustive proofs (the utility problem), and recursive explanations can lead to an explosion of low-utility rules.
The authors of FAILSAFE-2 (FS2) argue that search inefficiency is primarily driven by actions leading to "obvious" failures. They propose a system that learns quickly by focusing on "heuristic censors"—negative control rules that identify paths to avoid—even if the learning process occasionally involves over-generalization.
The FAILSAFE-2 Approach
FS2 operates using a base-level forward-chaining search and a meta-level learner. Its novel approach relies on three key components:
- Heuristic Censors: These are negative rules that block specific operators. Instead of discarding a state when an operator is blocked, the state is "suspended," allowing for potential recovery if the search becomes over-constrained.
- Preservable Constraints & Over-generalization: Rather than proving a failure is absolute, FS2 assumes that certain constraints (e.g., a goal once achieved) should remain true throughout the solution. This allows the construction of "incomplete" but extremely fast explanations of failure.
- Censor Relaxation: To handle cases where over-generalization blocks all valid solution paths, FS2 employs a relaxation mechanism. When progress stalls, it uses Weak Backward Chaining (WBC) to find a way to achieve the goal by "overruling" a censor. If a solution is found, the offending censor is specialized to prevent future errors.
Experimental Evaluation
The authors evaluated FS2 on three classic AI planning domains:
- Standard Blocks World: The classic task of stacking blocks.
- Modified Blocks World: A version with an increased branching factor, including an operator to grasp a block second from the top of a tower.
- STRIPS Robot World: A domain involving a robot moving blocks between different rooms.
Key Results
FS2 demonstrated significant efficiency gains across all tested domains. In the standard Blocks World, the system solved problems after expanding only 60 states (learning 14 censors), compared to 99 states without learning. Furthermore, censors learned on small problems (3-6 blocks) successfully transferred to larger problems (7-15 blocks), where the system solved 23 out of 27 problems that were unsolvable without learning.
In the Modified Blocks World—a domain where previous systems like PRODIGY struggled—FS2 successfully acquired effective control rules. Its performance remained robust despite the increased branching factor, proving that "incomplete" explanations can effectively manage search space complexity.
Discussion and Future Work
The core insight of FS2 is that "fast and wrong" can be superior to "slow and right." By building incomplete explanations, the system avoids the "intractable theory" problem. Learning what not to do prunes the search space more aggressively than learning what to do.
However, some limitations remain. The utility analysis of censors assumes probabilistic independence, which may not hold in all domains. Future work should include a more detailed accounting of the computational overhead of the learning and relaxation phases. Additionally, refining the heuristics used to choose which suspended states to relax remains an area for further study.
Summary updated