Two-layered Falsification of Hybrid Systems Guided by Monte Carlo Tree Search
Two-layered Falsification of Hybrid Systems Guided by Monte Carlo Tree Search
复制标题
蒙特卡罗树搜索引导的混合系统两层证伪
DOI：
10.1109/tcad.2018.2858463
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ichiro Hasuo
中科院分区：
文献类型：
--
作者：
Zhenya Zhang;Gidon Ernst;Sean Sedwards;Paolo Arcaini;Ichiro Hasuo
由于混杂系统的复杂性和黑盒成分，很少有真实世界的混杂系统可以进行形式验证。基于优化的证伪--一种采用随机优化的基于搜索的测试方法--因此作为一种替代的质量保证方法而受到关注。受最近倡导覆盖和演绎证伪的工作的启发，我们引入了一个使用蒙特卡洛树搜索(MCTS)的双层优化框架，MCTS是一种流行的机器学习技术，具有坚实的数学和经验基础(例如在计算机围棋中)。MCTS用于框架的上层；它指导下层的局部爬山优化，从而以一种有纪律的方式平衡勘探和开发。我们通过汽车领域的基准测试对所提出的框架进行了验证。
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 thus attracting attention as an alternative quality assurance method. Inspired by the recent work that advocatescoverageandexplorationin 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 (e.g., in computer Go). 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. We demonstrate the proposed framework through experiments with benchmarks from the automotive domain.