Abstract: Automating complex synthesis tasks like project planning typically requires a comprehensive, formal domain theory. However, in many real-world industries, such theories are unavailable, while libraries of past project plans are abundant. This paper introduces DInCaD (Domain-Independent System for Case-Based Task Decomposition), a novel system that performs task decomposition using only past examples. By employing a case-refinement process that balances generalization with specific preferences, DInCaD achieves high precision and maintains soundness without requiring pre-defined logical rules.
Introduction
Case-Based Reasoning (CBR) has traditionally excelled at analysis tasks, such as diagnostic systems that match current symptoms to past cases. However, synthesis tasks—like planning a construction project or a manufacturing sequence—present a significant challenge. These tasks usually rely on Hierarchical Task Network (HTN) planning, which requires a "domain theory": a complete set of logical rules defining every possible action and constraint.
In many practical fields, such as project management, these formal theories are non-existent. Instead, organizations possess vast repositories of past Work Breakdown Structures (WBS). The core challenge addressed by DInCaD is how to effectively reuse these past plans to solve new problems without a formal rulebook, ensuring the generated plans are both useful and "legal."
Methodology: The DInCaD Approach
DInCaD operates on HTN principles but replaces traditional rule-based methods with "generalized cases." To transform a specific past case into a reusable template, the system utilizes a three-phase refinement process:
- Simple Case Generalization: Specific constants (e.g., "Warehouse A") are replaced with variables (e.g., "?location"), allowing the case to be applied to novel situations.
- Constant Preference Phase: To prevent the system from producing invalid plans through over-generalization, original bindings are recorded as preferences. If a new problem matches the original case exactly, it receives a higher similarity score, anchoring the system to known-good solutions.
- Type Preference Phase: This "secret sauce" prevents over-generalization where a broad case might be selected over a more specific, better-fitting one. By adding negative type preferences, the system learns to prioritize specific cases (e.g., "shipping perishable liquid") over general ones (e.g., "shipping liquid") when appropriate.
These refinements are integrated into a weighted Similarity Criterion that ranks cases based on how well they satisfy both conditions and preferences.
Evaluation and Results
The researchers evaluated DInCaD using two complex synthetic domains: UM Translog (a logistics domain with strict object-type constraints) and a Process Planning Domain (focused on manufacturing rotary symmetrical workpieces).
The performance was compared across three system iterations:
- CB-S: Simple generalization only.
- CB-CP: Simple generalization plus Constant Preferences.
- CB-CTP: The full DInCaD system including Type Preferences.
As shown in the results, the full DInCaD system (CB-CTP) significantly outperformed the simpler versions. In the UM Translog domain, precision reached nearly 90%, a substantial jump from the 50-60% seen in CB-S and CB-CP. In the manufacturing domain, CB-CTP achieved 80% precision while maintaining a superior balance between precision and recall.
Discussion: The Soundness-Coverage Tradeoff
A central insight of this work is the management of the soundness-coverage tradeoff. While exact case reuse ensures soundness (correctness), it offers very low coverage. Conversely, aggressive generalization increases coverage but often results in "unsound" or illegal plans. DInCaD’s preference system allows for high coverage while using preferences to "pull" the system toward sound decisions.
Furthermore, DInCaD achieves domain independence. Unlike earlier systems that required human-authored adaptation rules, DInCaD learns to adapt based on the case structure and a basic type ontology. The use of negative preferences as a precision tool is particularly noteworthy, as it naturally guides the system toward the most accurate available solution.
Conclusion
DInCaD demonstrates that high-quality task decomposition is possible without exhaustive domain theories. While the system currently requires a type ontology and manual tuning of the similarity threshold ($\alpha$), it provides a robust framework for leveraging historical data in complex planning tasks. Future research will focus on automatically determining the optimal similarity threshold to further enhance the system's autonomy and cross-domain applicability.
Reference: Xu, K., & Muñoz-Avila, H. (2005). A Domain-Independent System for Case-Based Task Decomposition without Domain Theories. Proceedings of AAAI-05.
Summary updated