Efficiently Finding Optimal Solutions to Easy Problems in Design Space Exploration: A* Tie-breaking

摘要

Using design space exploration (DSE), certain real-world problems can be made solvable through (heuristic) search. A meta-model of the domain and transformation rules defined on top of it specify the search space. For example, we previously (meta-)modeled specific problems in the context of reusing hardware/software interfaces (HSIs) in automotive systems, and defined transformation rules that lead from a model of one specific HSI to another one. Based on that, a minimal number of adaptation steps can be found using best-first A* searches that lead from a given HSI to another one fulfilling new requirements. A closer look revealed that these problems involved a few reconfigurations, but often no reconfiguration is necessary at all. For such trivial problem instances, no real search should be necessary, but in general, it is. After it became clear that a good tie-breaker for the many nodes with the same minimal value of the evaluation function of A* was the key to success, we performed experiments with the tie-breakers recently found best in the literature, all based on a last-in-first-out (LIFO) strategy in contrast to the previous belief that using minimal h-values would be the best tie-breakers. However, our experiments provide empirical evidence in our real-world domain that tie-breakers based on minimal h-values can indeed be (statistically significantly) better than a tie-breaker based on LIFO. In addition, they show that the best tie-breakers for the more difficult problems are also best for the trivial problem instances without reconfigurations, where they really make a difference.