Introduction
Automated planning often faces a fundamental trade-off between completeness and efficiency. Restricted planning methods use search biases—such as assuming goals remain satisfied once achieved—to find solutions quickly. However, these methods often fail on complex problems. Conversely, general nonlinear planners are complete but suffer from significant computational overhead due to the massive search space.
Previous multi-method systems attempted to bridge this gap using a "coarse-grained" approach: attempting a fast, restricted method on an entire problem and restarting with a more general method upon failure. This approach is inefficient as it discards progress made by the restricted method. This paper proposes a "fine-grained" alternative that switches strategies at the level of individual subgoals.
Methodology: Fine-Grained Multi-Method Planning
The proposed system is implemented within the Soar architecture, utilizing six planning methods ($M_1$ through $M_6$) that vary across two dimensions of bias:
- Goal-Protection: Restricts the planner from undoing previously satisfied goals.
- Goal-Flexibility: Includes "Directness" (focusing only on top-level goals) and "Linearity" (solving goals sequentially without interleaving).
The core innovation is the ability to relax these biases "surgically." When a restricted method reaches an impasse, the system formulates a new set of subgoals and relaxes the bias only for that specific sub-region. This "Strongly Monotonic" approach ensures the planner always utilizes the most efficient viable strategy first, recovering from failures without a full restart.
Experimental Evaluation
The approach was evaluated in two domains:
- Blocks-World: 100 problems involving 3- and 4-conjunct goals.
- Machine Shop Scheduling: 100 problems with 5-conjunct goals, characterized by high operator interaction where goal-protection is the primary bias.
Results in Blocks-World
In the Blocks-World domain, the fine-grained approach significantly outperformed both single-method and coarse-grained strategies in terms of both efficiency (decisions) and plan quality (length).
As shown in the data, fine-grained planners averaged 16.44 decisions, a substantial improvement over the 29.98 decisions for coarse-grained and 38.58 for single-method planners. Furthermore, the resulting plan lengths were shorter, averaging 3.04 operators compared to 3.98 for single-method approaches.
Results in Scheduling Domain
The advantages of fine-grained planning were also evident in the Scheduling domain.
In this domain, the fine-grained approach required approximately 19 decisions, whereas standard single-method planners required between 31 and 34 decisions.
Conclusion and Future Work
Fine-grained multi-method planning demonstrates that biases are powerful search-space filters that should be managed dynamically. By allowing recovery without restart, the system maintains high efficiency while ensuring completeness. Future research could explore automated, run-time learning of bias sequences and the integration of additional bias types, such as those related to execution time or goal hierarchy depth.
Summary updated