An Investigation of Problem Instance Difficulty for Case-Based Reasoning and Heuristic Search

For managing the ever increasing variability of hardware/software interfaces (HSIs), e.g., in automotive systems, there is a need for the reuse of already existing HSIs. This reuse should be automated, and we (meta-)modeled the HSI domain for design space exploration. These models together with additionally defined transformation rules that lead from a model of one specific HSI to another one facilitate automatic adaptations of HSI instances in these models and, hence, both case-based reasoning (CBR) and (heuristic) search. Using these approaches for solving concrete problem instances, estimating their difficulty really matters, but there is not much theory available. This work compares different approaches to estimating problem instance difficulty (similarity metrics, heuristic functions). It also shows that even measuring problem instance difficulty depends on the ground truth available and used. In order to avoid finding only domain-specific insights, we also employed sliding-tile puzzles for our experiments. The experimental results in both domains show how different approaches statistically correlate. Overall, this paper investigates problem instance difficulty for CBR and heuristic search. This investigation led to the insight that admissible functions guiding heuristic search may also be used for retrieving cases for CBR.