没有合适的资源?快使用搜索试试~ 我知道了~
时间自动机上的最优控制算法及工具分析
理论计算机科学电子札记119(2005)11-31www.elsevier.com/locate/entcs使用HyTechPatricia Bouyer帕特里夏·布耶1,2,3LSV,UMR 8643,CNRS ENS de Cachan,FranceFranck Cassez弗兰克·卡塞兹1,2,4IRCCyN,UMR 6597,CNRS,法国Emmanuel Fleury伊曼纽尔·弗勒里5丹麦奥尔堡大学计算机科学系Kim G. Larsen6丹麦奥尔堡大学计算机科学系摘要定价时间(博弈)自动机扩展了时间(博弈)自动机的位置和转换成本。在文献[6]中,给出了在一定假设条件在本文中,我们提出了一个算法来计算最优成本和合成的最优策略的情况下,存在一个。我们还描述了该算法的实现与工具HyTE cH,并提出了一个例子。关键词:最优控制,定时系统,策略综合1由法国政府的ACI Cortos计划支持的工作。2访问丹麦奥尔堡大学CISS支助的奥尔堡。3电子邮件地址:bouyer@lsv.ens-cachan.fr4 电子邮件地址:cassez@irccyn.ec-nantes.fr5电子邮件地址:fleury@cs.auc.dk6 电子邮件地址:kgl@cs.auc.dk1571-0661 © 2005由Elsevier B. V.出版,CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2004.07.00612P. Bouyer等人/理论计算机科学电子笔记119(2005)111介绍近年来,模型检测技术在调度问题中的应用已经成为一个既定的研究方向。具有时间约束的静态调度问题通常可以表述为时间自动机上的可达性实时模型检查工具,如Kronos和Uppaal,已经应用于许多工业和基准调度问题[1,7,9,12,14,17]。通常,调度策略需要考虑环境上下文行为的不确定性。在这种情况下,调度问题变成了控制器和环境之间的动态(定时)博弈,其中控制器的目标是找到一个动态策略,以保证博弈以目标状态结束[4,8,16]。几年前,已经能够考虑相当一般的性能测量。时间自动机的定价扩展已经被引入[5,3],其中成本c与每个位置l相关联,给出在l中花费的单位时间的成本。在这个框架内,它是可能的,以衡量性能的运行,并给出最优性标准,达到一个给定的一组状态。在文献[6]中,我们结合了博弈和价格的概念,证明了在一定的假设下,定价时间博弈自动机的最优成本是可计算的,最优策略是可以合成的。在本文中,我们提出了一个算法提取最优策略的定价时间博弈自动机。我们还提供了使用工具HyTech[11]的算法的实现。本文的主要内容如下:第二节回顾了定价时间博弈自动机的定义,并给出了一个例子;第三节给出了一个最优成本计算方法;第四节详细介绍了综合最优策略的算法,在第6节中给出一些结论。图 5 和 图 7 中 给 出 的 HyTech 文 件 可 在 网 页 http://www.lsv.ens-cachan.fr/aci-cortos/ptga/上获得。我们提到的定理的详细证明以及补充定义和解释可以在[6]中找到。2定价计时游戏2.1预赛设X是一个称为时钟的实值变量的有限集合。我们将B(X)表示为由文法生成的约束集合:|其中k∈ Z,x,y∈X且<$∈ {<,≤,=,>,≥}。X中变量的赋值P. Bouyer等人/理论计算机科学电子笔记119(2005)1113≥∈∈∪∈∪−→× B × × ×−→Be0级δ1Σ∈∈--≥0--00001111nnnnn+1个n+1个是从X到R ≥0的映射(因此是R X的元素)。对于估值v和一组RX我们表示0v[R]与v在X\R上和在R上为零。 我们将δ记为v+δR≥0的估值s.t. 对于所有xX,(v+δ)(x)=v(x)+δ。2.2(R)PTGA模型定义2.1 [RPTGA]定价时间游戏自动机(PTGA)G是元组(L,l0,Act,X,E,inv,cost),其中:L是位置的有限集合;l0L是初始位置;Act=ActcActu是动作的集合(划分为可控和不可控动作); X是实值时钟的有限集合; EL(十)法2XL是一个有限的转换集;inv:L(X)关联到每个位置的不变量;cost:L EN关联到每个位置具有成本率,并且每个离散转换具有成本值。我们假设PTGA是确定性的w.r.t.可控制的操作(重命名)。可达性PTGA(RPTGA)是具有区分的位置集合的PTGA。2.3成本,成本设G=(L,10,Act,X,E,inv,cost)是RPTGA。G的一个配置是对(l,v)在L× RX中.A游程ρ=(l,v)−−δ0→(lJ,vJ)−−→(l, v)−−→(lJ,vJ)−−e→1· · ·(l, v)−−δn→(lJ,vJ)−−en→(l, v). . . 在G中,是有限的或交替时间(δ i∈ R ≥0)和离散(ei∈Act)步的有限序列,使得对每个i≥0:(li,vi)和(lJi,viJ)是G的配置;对每个ei∈Act,存在一个变迁(lJi,g,ei,Y,li+1)∈E,使得viJ|=g和vi+1=viJ[Y];对于chδi∈R≥0,li=lJi,viJ=vi+δi. 成本为由Cost(t)= α给出离散时间tept=(l,v)−−α→(lJ,vJ)。co st(l)ifαR ≥0且Cost(t)=cost((l,g,α,Y,l)),如果α法 如果沿着ρ的至少一个状态在集合Goal中,则G的游程ρ获胜。我们注意到(G)(分别)。(G))的集合(resp.获胜)在G和G((l,v),G)中运行(分别为Wink((l,v),G)的集合(resp.获胜)在G中运行,从配置(l,v)开始。如果ρ是n=2k步的有限次运行,我们注意到 last ( ρ ) = ( l k , v k ) , 运 行 ρ 的 成 本 定 义 为 : Cost ( ρ )=0≤i≤n−1Cost(t i)。例2.2考虑图2中的RPTGA。1.一、 普通箭头表示可控制的动作(动作c= c1,c2),而虚线箭头表示不可控制的动作(动作u= c 1,c 2)。u)。位置l0、l2和l3的成本率分别为5、10和1。在l1中,环境可以选择移动到l2或l3。然而,由于不变量y= 0,这个选择必须立即做出14P. Bouyer等人/理论计算机科学电子笔记119(2005)11e≥0≥∈0l2x2;c2;cost=1ulx≤2;c1;y:= 0lcost(l2)=10u目标cost(l0)=5[y=0]l3x≥2;c2;cost= 7cost(l3)= 1Fig. 1. 可达定价时间博弈自动机A2.4战略,战略定义2.3[策略]设G是(R)PTGA。G上的一个策略f是一个从G到Actc<${λ}的部分函数。定义2.4[结果]设G=(L, 10,Act,X,E,inv,cost)是(R)PTGA,f是G上的策略。f在G中的配置(l,v)的结果Outcome((l,v),f)是由下式归纳定义的n((l,v),G)的子集• (l,v)∈Outcome((l,v),f),• 如果ρ∈Outcome((l,v),f)则ρJ=ρ−→(lJ,vJ)∈Outcome((l,v),f)如果ρJ∈N((l,v),G)且下列三个条件之一成立:(i) e∈Actu,(ii) e∈Actc且e=f(ρ),eJ(iii) e∈R≥0且d∈0≤EJE<,则<$(LJJ,VJJ)∈(L×RX)s. t. last(ρ)−−→(lJJ,vJJ)<$f(ρ−−e→J (lJJ,vJJ))=λ。• 如果ρ的所有有限前缀都在结果((l,v),f)中,则无限次运行ρ在结果((l,v),f)中。在RPTGAG上的策略f是从(l,v)中获胜,只要结果((l,v) , f ) 中 的 所 有 max-max-1 运 行 都 是 获 胜 的 。 我 们 将 WinStrat((l,v),G)表示为G中来自(l,v)的获胜策略的集合。设f是一个来自配置(l,v)的获胜策略。ffrom(l,v)的成本定义为:成本((l,v),f)= sup{成本(ρ)|ρ ∈ Outcome((l,v),f)}2.5最优控制问题设(10,0)表示RPTGAG的初始配置。我们在本文中解决的三个主要问题是:[1]粗略地说,如果一个游程在未来不能通过一个可控的动作被延长,那么它就是最大的(见[6]第6页,2.2节);这一点将在3.2节的后续部分中讨论。1P. Bouyer等人/理论计算机科学电子笔记119(2005)1115∈≤≤ −−最优成本计算问题:我们想要从(l0,0)计算在RPTGAG中可以期望的最优成本,即计算OptCost((10,0),G)= inf{Cost((10,0),f)|f ∈WinStrat((l0,0),G)}最优策略存在性问题:我们要确定是否可以达到最优成本,即。 如果存在最优策略fWinStrat((l0,0),G)使得:成本((10,0),f)=OptCost((10,0),G)最优策略合成问题:如果存在最优策略,我们需要计算一个见证。如下面的例子所示,PTGA没有最佳的获胜策略。在这种情况下,存在一族策略fε,使得|ε|<ε因此,另一个问题是,给定ε,计算这样的fε策略。这后一个综合问题是不处理在本文中。实施例2.5 [无最佳策略]对于图2A的PTGA, 2没有最优策略。C是一个可控的动作。 然而,我们可以定义一个策略族f ε,其中0< ε 1为:f(l0,x<1ε)=λ,f(l0,x= 1ε)=c和f(l1,x1)=c。这种策略的成本是1+ε。所以我们可以尽可能接近1,但没有最佳获胜策略。cost(l0)= 1cost(l1)= 2l0x1;cL1x= 1;c目标[x1][x≤1]图二. 没有可达的最优成本的PTGA。例2.6我们再次考虑图1。我们希望从初始配置计算控制器显然,一旦达到l2或l3,控制器的最佳策略是尽快移动到目标(采取c2行动)。关键的(也是唯一剩下的)问题是,控制器在转换到l1(执行c1)之前应该在l0中等待多长时间显然,为了使控制器赢得这一持续时间必须没有更多的超过两个时间单位。然而,在达到目标的总成本最小的意义上,持续时间的最佳选择是什么 用t表示在l 0中选择的延迟。 那么5t +10(2-t)+1是通过l 2的最小成本,16P. Bouyer等人/理论计算机科学电子笔记119(2005)11Æ0→ Æ143333一DT5t+(2−t)+7是通过l 3的最小成本。当环境在这两条路径之间选择时,控制器的最佳选择是延迟t≤2使得max(21-5t,9+ 4t)是最小值,即t=4,给出最小值成本141 在图3中,我们说明了所有可达从我们的HyTech实现提供的初始状态,将在第3.4节中描述。y y224302x02xl0li,i∈{2,3}图三. 图1的RPTGA的最佳策略。最佳成本为141。3最优成本计算在本节中,我们将说明计算RPTGA的最优成本相当于在线性混合博弈自动机上解决一个简单的2控制问题[19]。因此,用于计算可达性混合游戏的获胜状态的众所周知的算法[19,8]使我们能够计算RPTGA的最优成本然后,我们展示了如何使用HyTech工具来实现RPTGA的最优成本的计算。3.1从定价时间博弈到线性混合博弈假设我们要计算图1中给出的RPTGA的最优成本1.一、我们把这个自动机转换成线性混合博弈自动机(简称LHGA)H(见图1)。4)其中成本函数被编码为变量Cost的LHGA。在H中,变量成本在位置l中以速率k减小(即,d如果A中的Cost(l)= k,则Cost(l)= −k。对于离散变迁,如果A中相应变迁的成本为k,则变量Cost由H中的成本J=成本− k更新。让CompWin是一个半算法(例如[19,8]),它计算可达性混合游戏的最大获胜状态集。使用CompWin,我们可以计算H的获胜状态的最大集合,目标状态由下式给出:2 不计成本。Æi→Goal延迟P. Bouyer等人/理论计算机科学电子笔记119(2005)1117uL2l0x≤2;c1;y:= 0L1开发成本DTu=-10x≥2;c2成本′=成本−1目标d成本tDT=-5[y=0]L3x≥2;c2DT≥0一≥∧≥H≥≥ H≥H>∈{≥}联系我们∈>∈{≥}d成本t=−1成本′=成本−7见图4。 线性混合博弈自动机H。目标成本0.这个新的可达性博弈的意义是,我们希望在不花费所有资源(成本)的情况下获胜。假设获胜状态的对应(最大)集合被表示为CompWin(,目标成本0)。 集合W=CompWin(,目标成本0)的含义是,为了获胜,必须在W给定的区域中开始,并且如果开始,则必须在W给定的区域中开始。在W之外,对手有获胜的策略,即我们输了。 我们可以证明(见[6],定理5和引理6)获胜状态的(最大)集合W是形式为(l,R)的区域的并集成本h)其中l是位置,RRX,h是R上的分段α-齐次函数,. 因此我们有最优可达性博弈的答案:我们将初始状态集与获胜状态集W相交,如果它不为空, 在成本轴上的投影产生对成本的约束,如成本>k与kQ ≥0且>,. 通过定义获胜的一组状态,在可达性博弈中,这是我们可以获胜的最大集合,没有成本低于或等于k是获胜的,我们可以推断出k是最优成本。我们还可以判断是否存在最优策略:如果>等于没有最优策略,如果>是≥,则有一个。因此,计算CompWin(,Goal Cost0)是用于计算RPTGA的最优成本的半算法。此外,我们可以决定(如果CompWin终止)是否存在最优策略:如果初始获胜成本集的形式为Cost> k,则不存在最优策略,而是存在成本低于k + ε的策略族f ε(对于ε >0)。 当这个集合的形式为成本k时(假设CompWin终止),我们可以计算出一个最优策略(这一点将在下一节4中讨论)。这种归约的形式定义和证明在[6]中给出(定义12,引理5,定理4和5,推论1和2)。3.2π算子获胜状态的计算(使用CompWin)基于可控前驱算子的定义[16,8]。设G=(L,10,Act,X,E,inv,18P. Bouyer等人/理论计算机科学电子笔记119(2005)11∈t≥0.Σ.Σ{}成本)是RPTGA,Q是其配置集。 对于集合X∈Q,一a∈Actwe定义ePreda(X) ={q∈Q|q−−→qJ,qJ∈X}。控制-X的可标记和不可控制的离散前导由cPred(X)定义=c∈Actc Predc(X),uPred(X)=u∈Actu Predu(X). 我们还需要一个一个集合X的安全定时前趋的概念。a集合Y。 直觉上,状态q在Predt(X,Y)中,如果从q我们可以通过时间流逝到达qJX,并且沿着从q到qJ的路径我们避开Y。正式定义为:Pred(X,Y)={q∈Q|δ∈Rs。t. q−→δ qJ,qJ∈X<$Post(q)<$Y}(1)[0,δ]在Post[0,δ] (q)={qJ∈Q|t∈[0,δ]|q−→tqJ}。 然后我们可以定义可控的前趋算子π如下:π(X)=PredtXcPred(X),uPred(X)(2)π的这个定义抓住了不可控行为不能用来获胜的选择(这个选择在[13]和[6]中做出事实上,在图1的RPTGA中,使用π的这种定义是没有办法获胜的:如果我们从目标开始迭代π的计算,那么l1不可能是获胜状态,因为π只添加可以通过可控转换到达获胜状态的前导另一种选择是可能的:如果无法控制的行为是被迫发生的,那么它们可能会被用来赢得胜利。当人们想在一般情况下给π下一个新定义时,这第二个选择是相当复杂的。我们采取的立场介于前两个极端之间:如果一个无法控制的行为从一个时间不能流逝的状态q开始,并导致一个胜利。状态QJ,并且在q处启用的不可控转换可以导致非在获胜的状态下,我们宣布q获胜。设G的一组时间不能流逝的构形记为STOP。然后,π的一个新定义,其中不可控的行动可以用来赢得:πJ(X)=PredtXcPred(X)(uPred(X)STOP),uPred(X)(3)请注意,此选择不会改变[6]中给出的结果。在图1的示例中,1,从位置l1仅启用不可控的转换,但是它们必然在有界时间量内发生(在这种情况下,由于不变量y=0,我们一到达l1就发生)。πJ将添加配置(l1,x≥0<$y=0)的一组获胜状态。半算法CompWin计算函数λX的最小不动点W。X0πJ(X)作为状态集合 Wi(从集合 W0=X0开始)的递增序列的极限,其中 Wi+1=πJ(Wi))。如果G是RPTGA,则从目标成本≥ 0开始的相关LHGA H上的CompWin的计算结果为W = µX。{Goal <$Cost ≥ 0}<$πJ(X)。这P. Bouyer等人/理论计算机科学电子笔记119(2005)1119∧≥∧≥HH结果也表示为CompWin(H,目标 成本0),并给出最大的获胜状态集。3.3终职问题CompWin半算法的一个重要问题是它是否终止。我们已经确定了一类RPTGA,CompWin终止于相关的混合游戏。设G是RPTGA,满足:• G是有界的,即G中的所有时钟都是有界的;• G的代价函数是严格非zeno的,即存在某个κ >0,使得与G相关联的区域自动机中每个循环的累积代价至少为κ。请注意,可以检查此条件。更详细的解释请参见[6]。然后半算法CompWin(H,Goal Cost0)终止(H是上一节中由G定义的混合博弈)。文[6]中的定理6给出了这一主张的形式陈述和证明。因此,我们得到:定理3.1设G是满足上述假设(代价有界性和严格非零性)的RPTGA。则G的最优成本是可计算的。3.4CompWin在HyTech中的实现HyTech[10,11]是一个为线性混合自动机实现“前”和“后”操作符的工具。此外,还可以编写程序,在多面体上使用这些运算符(以及许多其他运算符)来计算状态集。图5第7- 20 行给出了我们的图4的LHGA 在HyTech我们在续集中详细说明了这一点。可控和不可控的前体。HyTech提供了预运算符,它可以同时计算一组状态的时间前导和离散前导。由于我们需要区分时间前导、离散可控前导和离散不可控前导,我们使用以下技巧:在LHA的HyTech源代码中,我们添加两个布尔变量u和c(图5,第4行),它们在每个离散不可控标签上被取反(分别为:可控)转换(图5,第10在HyTech中,可以通过使用隐藏运算符对变量t进行然后,可控制的前驱可以通过在c上存在量化来计算3 这个假设不是一个限制,见[15]。20P. Bouyer等人/理论计算机科学电子笔记119(2005)11−不不不−H−在一个速率为41的变量t上我们可以用存在量化器和两个变量t和c来表示cPred(和uPred)算子,如下所示:CcPred(X) ={q|c∈Actcs. t. q→−qJ,qJ∈X}={q|特劳特科洛姆茨体育场t=0c=0(q,t,c)∈pre(X<$t= 0<$c= 1)}其中pre是HyTech的前身运营商。我们强制t的值保持不变,以确保我们只是采取离散的前任(图。5,第39行)。对于不可控的先行者,我们用u代替c(图5,第41行)。注意,STOP状态的计算(图5,第32行)也可以使用我们的额外变量t,c,u来完成。安全时间的先行者。另一个算子Predt(Z,Y)稍微复杂一些。我们只需要用存在性量化来表达它,这样就很容易用HyTech来计算它。此外,我们假设我们有时间决定性自动机,因为在这种情况下Predt(Z,Y)相当简单(如果我们没有时间决定性,则必须进行更复杂的编码,我们请读者参考[19]以获得详细解释。从等式(1)我们得到:前d(Z,Y) ={q|t≥0s。t. q→−tqJ,qJ∈Z,<$0≤t1≤t,q→−qJJ=<$qJJ/∈Y}={q|t≥0s。t. q→−tqJ,qJ∈Z,<$(<$0≤t1≤t,q→−qJ J<$qJJ∈Y)}后一个公式可以在HyTech中使用hide操作符进行编码(图1)。5,第47.)最后如果πJ的计算终止(图11)。5,第35然后,它开始计算成本的投影,初始状态,以获得最佳成本(图。5,第61行)。这样我们就解决了前两个问题:计算最优成本和确定是否存在最优策略。4最优策略计算在本节中,我们将展示如何在存在最优策略时计算最优策略。然后我们给出了这种计算的HyTech实现,并讨论了这些策略的一些性质。4任何与0不同的速率也可以,但我们需要另一个速率为1的变量t,然后使用这个变量。P. Bouyer等人/理论计算机科学电子笔记119(2005)1121−−−−−−−−−−−−−−−−−−−−−−−− ∪ ∪∩varx,y:时钟;成本:模拟;−−成本变量c,u:离散的;−−用于表示可控和不可控的过渡5:t,t1:模拟;−−用于存在性量化自动机Hsynclabs:;最初L0 &x=0时 &return 0;10:锁定 L0:当 x>=0&y>=0 等待{dcost=-5,dt =-1,dt1 =-1}当x>=0x =2时,{&locl1: whiley=0 wait{dcost=0,dt=-1,dt1 =-1} whenTrue do{十五:locl3: whilex>=0y>=0 wait{dcost=-10,dt =-1,dt1 =-1}&当nx>=2do{locl4: whilex>=0y>=0 wait{dcost=-1,dt =-1,dt1 =-1}&当nx>=2do{locWin:当Truewit{dcost=0,dt=-1,dt1=-1}时,二十:端varinit_reg,winningg,fix,setsofstatesSTOP, STOPstatuPreX、uPrebarX、cPreX、X、Y、Z:相关;二十五:首先确定初始和获胜区域init_reg:=loc[H]=10x=0;winning:=loc[H]=Wincost>=0;&&−−fix是我们要计算的定点,即获胜状态W的集合30日上午10:fix:= winning;停止状态STOP:= ~(hidet,c,uint>0c=0u=0pre(Truet=0c=0u=0)endhide);计算πJ的定点三点五:X:=iterateXfromwinninggusing{不可控的X的前身:uPred(X)uPrebarX:=hidet,uin t=0 u=0pre(~X u=1 t=0)endhide;&&&&X的可控前代:cPred(X)cPreX:=hidet,cint=0c=0pre(Xt=0c=1)endhide;40:无法控制的前辈导致获胜状态:uPred(X)uPreX:=hidet,uint=0u=0pre(Xu=1t=0)endhide;Z是πJ的第一个自变量;Z=XcPred(X)(上升(X)停止)Z:=(X |cPreX|&);45:−−Z的时间先行者,从这里我们可以到达Z并且始终避免uPred(X);X:=Predt(Z,uPred(X))X:=隐藏在(hidec,uint>=0c=0u=0pre(Zt=0c=0u=0)endhide)&50:~(将t1隐藏在(hidec,uint1>=0t1 =tc=0u=0&前(uPrebarX & t1=0 & c=0 &(u=0)结束隐藏)结束隐藏)55:隐藏结束;将新计算的区域添加到已经计算的区域固定:=固定|X的;}的情况;60:打印结果print省略所有位置hidex,y infixinit_reg endhide;&图五. 计算最优成本。−−−−22P. Bouyer等人/理论计算机科学电子笔记119(2005)11∈∀∈{}≤22l0x >1;c目标4.1RPTGA的策略综合首先,我们回顾一些基本性质的策略(无价格)时间博弈自动机(TGA)。策略f是• 基于状态的,只要ρ,ρJ<$(G),last(ρ)=last(ρJ)就意味着f(ρ)=f(ρJ)。基于状态的策略在博弈论中也被称为无记忆策略[18,8];• 多面体,如果对所有的Actcλ,f−1(a)是一个凸多面体的有限并集,对于博弈的每个位置;• 可实现的,当以下情况成立时:对于所有ρ Outcome(q,f)s. t。F定义在ρ上,且f(ρ)=λ,则存在某些δ >0,使得对于所有0≤t<δ,其中f(ρ − → t q j)= λ,t ∈ tsqJ,hρ−→tqJ∈Outcome(q,f).不可实现的策略是没有意思的,因为它们会产生空的结果集然而,从[16,4]中还不清楚如何提取RPTGA的策略并确保其可实现性,如以下示例所示见图6。 一个定时博弈自动机例4.1考虑图4.1的PTGA。其中c是可控动作。游戏的目的是实现国家目标。最自然的策略f是在x >1时执行c,并等待x达到大于1的值。形式上这产生f(l0,x 1)=λ和f(l0,x >1)=c。 这一战略是不可能实现的。 在此基础上,我们构造了一个策略f(l0, 0 |q + t ∈ X 0≤ tJ≤ t,q + tJ∈ X}(4)Tagged Sets 为了合成策略,我们在计算W的过程中迭代地计算一组扩展的“标记”状态W +(这从[ 6 ]的定理2和引理6得出)。标签将包含关于如何获得获胜状态Wi+1=πJ(Wi)的新集合的信息我们从W+=和W0=目标成本≥0开始。假设Wi和W+0是πJ的i次迭代后得到的集合,我们定义W+我如下所示[1] 设Y=Wi+1\Wi,其中Wi+1=πJ(Wi);[2]对于每个c∈Act,我们定义标记集。YcPredc(W)[c],预期含义:[3]定义另一个标记集不间断(Y)[λ]具有预期的含义:[4]定义W++一期+1通过:+[λ]我c∈Actc.YcPredc(W)[c]计算一个最优策略。如果CompWin在j次迭代中终止,我们最终得到W+=W+。 注意,通过构造,W的状态q可以属于几个标记集合X[λ],X[c1],., X[cn](其中c∈Actfor eachi∈[1,n])。 如果满足定理4.3的假设,则所有Xi具有形式XiJ<$Cost≥hi,其中对于某个位置li,XiJ<${li}×RX≥和 hi:XiJ→0R≥0是一个分段连续函数。 所以,H的最小值是超过XiJ是可达的,且等于hi的最小值。[6]的定理7指出,在这种情况下,基于状态的最优策略对于q,G的获胜状态(无成本)将通过取局部WP. Bouyer等人/理论计算机科学电子笔记119(2005)1125∈{1}|}[丙]W=我[丙]≥≤∈{}≤[c1]∀α|(q,α)∈W ,α≤α}[c]2[c1]{}最优选择:设m=mini∈[0,n]hi(q),则定义f∈(q)=ci,如果hi(q)=m给出了最优策略。由于可以是hi(q)=hj(q)=m的情况,其中i j,我们施加a在Act c中的事件集合上的全序,并定义f(q)=c i,其中i=maxjh j(q)=m。为了避免在集合X i的边界上的可实现性问题(参见[ 6 ]中引理6的证明),如果h0(q)= m(这意味着最优成本可以通过时间流逝来实现)并且对于某些i[1,n],hi(q)=m,我们定义f(q)=ci。 这可以很容易地定义在我们的设置,通过扩展我到行动c <${λ},并使λ的最小元素。在这些算法解释之后,我们可以总结一下如何合成一个最优的、成本无关的策略。 我们记为W+定义的集合通过:+[丙]中国(5)S[c]∈W+对于每个c∈Actc<${λ},W+是形式为Xc<$Cost≥hc的集合,其中hc是Xc(Xc是凸多面体的并)上的分段α-函数.注意,约束Costhc是约束Cost变量和时钟的多面体。在下文中,对(q,α)将表示H的状态(α是Cost变量的值)。对于G的每个获胜状态q,我们要计算获胜的最小成本,以及如果我们想以最优成本获胜,我们应该采取什么行动。让我们考虑两个行动c1,c2c法λ。 我们表示[c1c2]G的获胜状态的集合,其中最好执行动作c1而不是动作c2(hc1(q)hc2(q))。此集合定义为通过:[c1≤ c2]={q ∈ X c1 |∃α1|(q,α1)∈ W+,(六)+2 2 12=. q∈ X c1 |∃α1|(q,α1)∈ W +π[c2](七)嗯。∃α2|(q,α2)∈ W+和α2<α1∈ W +每个集合[c1≤c2]是一个多面体集合。对于每个c∈Actc<${λ}定义,选项(c)=[c≤cJ](8)cJ/=cOpt(c)是一组状态,其中c是给出最优成本的动作。W=法案cλ 因此,Opt(c)等于我们需要的状态集确定最优策略。 给定Actc{λ}上26P. Bouyer等人/理论计算机科学电子笔记119(2005)11的总顺序,λ<$c1<$··<$cn,我们可以定义一个最优策略f如下:P. Bouyer等人/理论计算机科学电子笔记119(2005)1127.Σ∈∈ −\≤我[0,n1],设Bi=W(k>iB k)Opt(ci)和Bn=Wnint n(n);定义f∈(q)=c i,如果q B i。f是一个最优策略,它是获胜的、基于状态的、可实现的、多面体的。4.3在HyTech可控标记集。我们首先展示如何计算标记的状态集。我们的HyTech编码包括将离散变量a添加到图1的HyTech模型5并将其用于可控转换的保护中:图5的可控动作ck4对应于HyTech模型中的防护a=k图5的HyTech模型被丰富如下:到第11行,a= 2到第16和18行。以这种方式,我们实现了对可控前导的标记,因为现在cPred的计算(图7的第39行)将计算标记区域,该标记区域将是具有一些特征的多面体的并集a=k约束。注意,我们还修改了图5的行44并将其替换为图7中的行20,其中a对新cPreX隐藏,因为不需要a来计算获胜状态集。新的不间断状态。 为了计算NonStop(Y),我们再次使用额外的变量t,c,u,并将标签a = 0添加到结果集。第357做到这一点。W+存储在HyTech代码中的fix_strat区域计算+一期+1我们更新fix_strat,如图3中第38行所述。7 .第一次会议。最优策略的计算。为 了 比较每个动作的成本并确定最优的一个,我们使用了上一小节中描述的技巧。每个标记集通过Cost变量和其余状态变量之间的约束给出函数hci为了计算hci,我们需要根据每个动作ci分割状态空间:这通过第44对于每对动作(c1,c2)(c i可以是λ),仍然需要计算集合[c1c2]的状态。在HyTech中,等式(7)给出的公式的编码非常简单,使用了对应于存在量化的隐藏算子。然后,如本文末尾所述计算策略第545实验使用本文所描述的HyTech代码,我们做了更多的实验。我们处理过的最重要的例子是一个带有两个天线的移动电话模型,它试图连接到一个基站,W28P. Bouyer等人/理论计算机科学电子笔记119(2005)110−−−−−−−−−−≤− −{}var与图22 - 24行中的变量相同。 5加上一些新的变量:a:离散;成本0,成本1,成本2:anal og;5:fix_strat,nonstop,Y,r0,r1,r2,B0,B1,B2,inf_0_1,inf_0_2,inf_1_0,inf_1_2,inf_2_0,inf_2_1:rgion;第十章:init_reg:=loc[H]=l0x=0;winning:=loc[H]=Wincost>=0; fix:=winning;&&STOP:=~(hidet,c,uint>0c=0u=0pre(Truet=0c=0u=0)endhide); fix_strat:= False;−−这是新的,对应于W+=0&&&&&&十五:X:=iterateXfromwinninggusing{uPrebarX:=hidet,uint=0u=0pre(~Xu=1t=0)endhide; cPreX:=hidet,cint=0c=0pre(Xt=0c=1)endhide;uPreX:=hideet,uint=0u=0pre(Xu=1t=0)endhidee;20:Z:=(X|(隐藏eincPreX结束隐藏e)|(uPreX&~uPrebarX&STOP));X:=隐藏在(hidec,uint>=0c=0u=0pre(Zt=0c=0u=0)endhide)&~(hide 中的t125:(hidec,uint1>=0t1 =tc=0u=0&前(uPrebarX & t1=0 & c=0 &(u=0)结束隐藏)结束隐藏)endhide;30日上午10:Y:=X ~fix;−−st
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- GO婚礼设计创业计划:技术驱动的婚庆服务
- 微信行业发展现状及未来发展趋势分析
- 信息技术在教育中的融合与应用策略
- 微信小程序设计规范:友好、清晰的用户体验指南
- 联鼎医疗:三级甲等医院全面容灾备份方案设计
- 构建数据指标体系:电商、社区、金融APP案例分析
- 信息技术:六年级学生制作多媒体配乐古诗教程
- 六年级学生PowerPoint音乐动画实战:制作配乐古诗演示
- 信息技术教学设计:特点与策略
- Word中制作课程表:信息技术教学设计
- Word教学:制作课程表,掌握表格基础知识
- 信息技术教研活动年度总结与成果
- 香格里拉旅游网设计解读:机遇与挑战并存
- 助理电子商务师模拟试题:设计与技术详解
- 计算机网络技术专业教学资源库建设与深圳IT产业结合
- 微信小程序开发:网络与媒体API详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功