Monte Carlo Tree Search for Feature Model Analyses: a General Framework for Decision-Making

Abstract

The colossal solution spaces of most configurable systems make intractable their exhaustive exploration. Accordingly, relevant anal-yses remain open research problems. There exist analyses alterna-tives such as SAT solving or constraint programming. However, none of them have explored simulation-based methods. Monte Carlo-based decision making is a simulation based method for deal-ing with colossal solution spaces using randomness. This paper proposes a conceptual framework that tackles various of those anal-yses using Monte Carlo methods, which have proven to succeed in vast search spaces (e.g., game theory). Our general framework is described formally, and its flexibility to cope with a diversity of analysis problemsis discussed (e.g., finding defective configurations, feature model reverse engineering or getting optimal performance configurations). Additionally, we present a Python implementation of the framework that shows the feasibility of our proposal. With this contribution, we envision that different problems can be ad dressed using Monte Carlo simulations and that our framework can be used to advance the state of the art a step forward.