Two-Layered Falsification of Hybrid Systems guided by Monte Carlo Tree Search
For engineers testing complex hybrid systems, this method offers a more effective falsification approach by combining global exploration with local optimization.
The paper introduces a two-layered falsification framework for hybrid systems that uses Monte Carlo tree search (MCTS) to guide local hill-climbing optimization, balancing exploration and exploitation. Experimental results show that the approach improves falsification rates compared to existing methods.
Few real-world hybrid systems are amenable to formal verification, due to their complexity and black box components. Optimization-based falsification---a methodology of search-based testing that employs stochastic optimization---is attracting attention as an alternative quality assurance method. Inspired by the recent works that advocate coverage and exploration in falsification, we introduce a two-layered optimization framework that uses Monte Carlo tree search (MCTS), a popular machine learning technique with solid mathematical and empirical foundations. MCTS is used in the upper layer of our framework; it guides the lower layer of local hill-climbing optimization, thus balancing exploration and exploitation in a disciplined manner.