The Roles of Adaptation in Case-Based Design

Thomas R. Hinrichs, Janet L. KolodnerAAAI 1991

Abstract

This paper presents a model for high-level design that utilizes "plausible design adaptation" to navigate vague and ill-defined search spaces. Implemented in the JULIA meal-planning system, the model demonstrates that adapting previous solutions—rather than starting from scratch or relying on extensive backtracking—enables AI to handle late-arriving constraints and conflicting requirements more efficiently.

Introduction

Design tasks are frequently "ill-defined," characterized by vast search spaces, subjective evaluation criteria, and requirements that evolve mid-process. Traditional AI approaches often struggle with this fluidity, relying on rigid classifications like "selection" or "configuration." This paper addresses the limitations of these rigid systems, focusing on three primary challenges: overcoming fixed design classifications, improving search efficiency in vague spaces, and handling late-arriving constraints without the need for exhaustive backtracking.

Methods

The authors propose a model centered on Case-Based Reasoning (CBR) integrated with constraint posting and problem reduction. The core mechanism is plausible design adaptation, a heuristic debugging process that repairs source concepts to satisfy new or violated constraints. The system, JULIA, utilizes several transformation types:

  • Component Transformations: Replacing parts via specialization, generalization, or functional substitution (e.g., substituting meat with a vegetarian alternative).
  • Structural Transformations: Re-organizing the design through function sharing (one component serving two roles) or function splitting (dividing a goal between two components).
  • Constraint Adaptation: Weakening offending constraints by enlarging their domain or generalizing their range when values cannot be changed.

Results and Evaluation

The model was tested on a meal-planning knowledge base across four problem cases designed to trigger different reasoning behaviors, ranging from under-constrained Italian meals to over-constrained plans with conflicting guest requirements. Efficiency was measured by the number of constraints checked during the problem-solving process.

Table 1: Comparative performance metrics (number of constraints checked) across different problem scenarios.

As shown in Table 1, adaptation significantly improved efficiency in under-constrained scenarios (Problem 1), reducing the computational workload by approximately 65% compared to non-adaptive methods. In over-constrained scenarios (Problem 2), adaptation was the only method capable of reaching a solution, specifically by splitting functions to satisfy conflicting requirements. However, Problem 4 highlighted a potential "hidden cost": adaptation can be slower if the system spends excessive time attempting to repair a fundamentally flawed initial case (a "blind alley") before moving on to a better one.

Discussion

Adaptation serves as a "vocabulary extension," allowing the system to synthesize new solutions by modifying existing ones. It operates on the "nearby" heuristic—the principle that a satisficing solution is often close to a previous case in the search space. By adapting specific decisions rather than retracting them, the system maintains stability and preserves downstream consequences, making the design process more coherent and easier for human users to follow.

Conclusion

While adaptation offers significant flexibility and enables solutions in complex, over-constrained spaces, it introduces a tradeoff between flexibility and efficiency. The authors suggest that future research should explore how the density of the solution space affects the utility of deep adaptation. In sparse spaces, deep adaptation is essential; in dense spaces where many solutions exist, simple retrieval of alternative cases may be more computationally efficient.

Summary updated

BibTeX
@inproceedings{hinrichs1991roles,
  author = {Thomas R. Hinrichs and Janet L. Kolodner},
  title = {{The Roles of Adaptation in Case-Based Design}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure