Improving Competence by Integrating

Case-Based Reasoning and Heuristic Search

Zdenek Zdrahal, Enrico Motta

Knowledge Media Institute
The Open University
Walton Hall,
Milton Keynes, MK7 6AA
United Kingdom
{z.zdrahal, e.motta}@open.ac.uk

Abstract. We analyse the behaviour of a Propose & Revise architecture in the VT elevator design problem and we show that this problem solving method cannot solve all possible cases covered by the available domain knowledge. We investigate this problem and we show that this limitation is caused by the restricted search regime employed by the method and that the competence of the method cannot be improved by acquiring additional domain knowledge. We therefore propose an alternative design problem solver, which integrates case-based reasoning and heuristic search techniques and overcomes the competence-related limitations exhibited by the Propose & Revise architecture, while maintaining the same level of efficiency. We describe four algorithms for case-based design, which exploit both general properties of parametric design tasks and application specific heuristic knowledge.

1 INTRODUCTION

Design problems are hard due to the potentially combinatorial explosion of the design space. Designers, both human and artificial, tackle the complexity of the design process by making use of both task-specific heuristics as well as case-based knowledge. The Propose & Revise (P&R) problem solving method (Marcus and McDermott, 1989; Yost and Rothenfluh, 1996; Zdrahal and Motta, 1995) is a well known example of an approach to design problem solving which uses heuristic knowledge to reduce the complexity of the search space. In this paper we critically review the competence of this method by analysing the behaviour of a Propose & Revise problem solver in the VT elevator design domain (Yost and Rothenfluh, 1996) and we show that such a problem solver could not solve all the ?obvious? cases made possible by the available domain knowledge. The reason for this limitation is that the problem solving model (not the domain knowledge!) provided by domain experts and described in (Yost and Rothenfluh, 1996) is incomplete. In particular, the search algorithm used by the model is a greedy, local search procedure and therefore it rejects any search step which does not decrease the number of constraint violations, even in cases where such a search step is part of a path leading to a solution design. A similar pattern of behaviour was reported by (Selman et al., 1992) when carrying out experiments on the satisfiability of a set of propositional clauses. Selman shows that by introducing ?sideway moves? into the search algorithm the competence of the algorithm improves from about 40 ? 60% to 100% and the time consumed by the algorithm dropped to about 10% of the original value. In our example, we cannot produce statistically meaningful results as we have not evaluated a large enough data sample, but we can instead provide a real-world interpretation of the troublesome cases. They seem to arise when solving the machinery subsystem of the elevator. This is indeed