文章基本信息

标题：Generating Dominant Strategies for Continuous Two-Player Zero-Sum Games
本地全文：下载
作者：Marcell J. Vazquez-Chanlatte ; Shromona Ghosh ; Vasumathi Raman 等
期刊名称：IFAC PapersOnLine
印刷版ISSN：2405-8963
出版年度：2018
卷号：51
期号：16
页码：7-12
DOI：10.1016/j.ifacol.2018.08.002
语种：English
出版社：Elsevier
摘要：AbstractMotivated by the synthesis of controllers from high-level temporal specifications, we present two algorithms to compute dominant strategies for continuous two-player zero-sum games based on the Counter-Example Guided Inductive Synthesis (CEGIS) paradigm. In CEGIS, we iteratively propose candidate dominant strategies and find counterexamples. For scalability, past work has constrained the number of counterexamples used to generate new candidates, which leads to oscillations and incompleteness, even in very simple examples. The first algorithm combines Satisfiability Modulo Theory (SMT) solving with optimization to efficiently implement CEGIS. The second abstracts previously refuted strategies, while maintaining a finite counterexample set. We characterize sufficient conditions for soundness and termination, and show that both algorithms are sound and terminate. Additionally, the second approach can be made complete to within an arbitrary factor. We conclude by comparing across different variants of CEGIS.
关键词：KeywordsController SynthesisRobust ControlCounter-Example Guided Inductive Synthesis