关键词:
系统综合
形式化方法
程序概率综合
机器学习
摘要:
反应式程序综合是一种通过给定系统行为规约自动生成交互式系统模型的技术。然而,反应式系统通常是在复杂多变的环境中运行的。环境和系统行为均具有复杂性,这导致反应式程序综合问题成为一个棘手的难题。此外,由于描述环境和系统特定的行为存在挑战,使得反应式程序综合的技术和工具的应用变得困难。在传统的程序综合方法中,控制程序不仅需要人为编写代码,而且程序综合过程繁琐且很难保证程序的正确性。虽然程序的正确性很难保证,但其与形式化方法的结合能够提高程序综合的适用性。目前反应式程序综合技术的发展还存在一些问题,主要分为两类:(1)当考虑来自系统行为和环境的不确定性时程序综合的过程变得复杂而困难。系统和环境之间的关系的一个关键特征是,它们在博弈中扮演玩家的角色,相互对立;(2)当程序不能满足规约时规约修复的问题。这通常也是困难的,因为即使找到需要修复的规约,也可能出现不能修复的情况,或者修复后得不到令人满意的控制器。
为了应对以上问题,本文关注基于异步概率博弈的程序综合的理论和技术的研究,即程序概率综合。程序概率综合指在概率环境下,如何概率综合一个满足给定规约需求的程序的问题。论文在对程序概率综合的理论和技术的研究中,系统的需求规约用线性时序逻辑(Linear Temporal Logic,简称LTL)编写,结合形式化方法、马尔可夫决策过程和机器学习等技术,通过分析系统在概率环境下系统获胜的概率、期望累积奖励和期望均值收益,得到系统在概率环境下具有获胜策略的条件,提升系统综合的成功率。本文工作的优势体现在两个方面。一方面,能够应对复杂的环境行为和系统自身行为给程序带来的不确定性,理论和实验结果表明,提升了程序综合成功的可能性;另一方面,提出了一种可以确定何时不能为规约综合程序或何时不能修复规约的技术,从而避免程序不能综合或者规约无法修复时花费时间和精力,还可以减少设计人员在设计协议(用于规约修复)时的工作量。据我们所知,本文的工作是首次针对LTL需求规约的概率综合的理论和方法的研究。具体来说,论文的研究内容和创新如下:
(1)提出一种符号号化的程序概率综合的模型理论。传统的程序综合方法可以保证根据给定的需求规约生成正确的程序,但通常在对系统和环境描述时不能贴切的呈现出不确定性。在实际应用中,系统环境的变化具有复杂的不确定性,也会导致系统行为发生不可预测的变化。为了处理这种变化,本文研究了一种程序概率综合方法,与传统的控制器综合方法相比,程序概率综合方法更注重系统满足给定规约的能力(概率)。程序概率综合方法的提出有两个关键点。一个关键点是建立概率模型将系统与环境的对立与交互关系符号化。为此,以马尔可夫决策过程(Markov Decision Process,简称MDP)为竞技场,定义系统与环境的博弈关系,构建一个异步概率模型来描述系统和环境之间的不确定行为和概率迁移。异步概率模型结合了双人博弈和MDP的特点。基于该概率模型,研究系统如何在博弈过程中提取有效信息,使控制器更容易综合。另一个关键点是提出了一个新的模态演算变体来符号化公平性和可达性。根据系统控制的状态、环境控制的状态和获胜条件之间的关系将状态空间进行划分,以此来优化状态空间。将程序综合问题转化为概率可达问题,通过计算可达概率来解决该问题,得到系统获胜策略的概率和环境失败策略的概率,并用实验说明算法的可行性和有效性。
(2)基于机器学习的LTL规约的程序综合方法。传统的控制程序综合是在动态环境中构造满足给定规约的程序,而程序不断地与环境交互。就系统及其环境之间的交互模型而言,系统和环境是参与者,其关系通常是对立的。因此,一个规约在某些环境下可能存在不可综合的问题。当规约不可综合时,可以采取两种方法去处理。一个是找出程序不能按照规约综合的原因,并将信息反馈给设计者,设计者及时地修改规约。然而,实时性却很难保证。另一个是根据其语法结构修改规约,这可能改变设计者最原始的意图。为了避免程序无法综合的问题,以期望最大化的提升系统满足给定规约的能力,减少修改规约的情况,论文设计了一种奖励机制,来激励玩家通过他们的位置的选择和动作的执行来获得最大的奖励。基于这一机制,应用学习理论的技术将综合问题转化为寻找策略来计算期望累积奖励的问题。此外,还抽取了强化学习算法提供的渐近最大化LTL规约的期望累积奖励的最优策略。通过实例证明了该方法的可行性。
(3)具有均值收益益目标的GR(1)规约的程序综合。将上述模型和方法推广到解决概率环境下具有定量和定性组合需求的程序综合问题。在实际应用中,我们通常更希望以尽可能高的概率综合满足规约的程序,并获得保证程序满足规约时期望的收益。综合问题的目标是在概率环境下,利用行动回报获得期望的均值收益,同时在对抗环境下满足给定的GR(1)条件。换句话说,解决具有获胜概率的系统