[Back]

H. Kaindl, R. Hoch, R. Popp:
"Estimating Problem Instance Difficulty";
Talk: ICEIS 2020, Internet; 2020-05-05 - 2020-05-07; in: "ICEIS 2020 - Proceedings of the 22nd International Conference on Enterprise Information Systems", Scitepress, Volume 1 (2020), ISBN: 978-989-758-423-7; 359 - 369.

Even though for solving concrete problem instances, e.g., through case-based reasoning (CBR) or heuristic search, estimating their difficulty really matters, there is not much theory available. In a prototypical realworld application of CBR for reuse of hardware/software interfaces (HSIs) in automotive systems, where the
problem adaptation has been done through heuristic search, we have been facing this problem. Hence, 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. A few different approaches are investigated on how they statistically correlate. Overall, this paper compares different approaches to both estimating and measuring problem instance difficulty with respect to CBR and heuristic search. In addition to the given real-world domain, experiments were made using sliding-tile puzzles. As a consequence, this paper points out that admissible heuristic functions h guiding search (normally used for estimating minimal costs to a given goal state or condition) may be used for retrieving cases for CBR as well.

Case-based Reasoning, Similarity Metric, Heuristic Search, Admissible Heuristic, Problem Difficulty

http://dx.doi.org/10.5220/0009390003590369