没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记149(2006)3-18www.elsevier.com/locate/entcs行动计划Petri网Stefan Edelkamp1德国多特蒙德大学计算机科学系沙希德·贾巴尔德国多特蒙德大学计算机科学系摘要Petri网是分析分布式系统的基础,特别是在有限状态系统中。在Petri网中寻找一个特定的标记对应于一个属性的侵犯,可以减少到探索一个状态空间诱导的可达标记的集合。典型的探索(可达性分析)方法是无向的,不考虑任何有关Petri网结构的知识。本文提出了启发式搜索的增强探索,以加快搜索。对于系统开发过程中的不同需求,我们区分了不同类型的估计。将转换的触发视为应用于由Petri网结构和标记引起的一组谓词的动作,可达性分析可以简化为为寻找AI规划问题的计划。这样的约简为人工智能启发式搜索规划技术的应用拓宽了视野。本文讨论了Petri网到PDDL的转换方案。我们在Level 2 PDDL2.2中展示了一般位置转换网的简洁编码,并在ADL/BSPS中展示了有界位置转换网的规范。与现有的规划器的初步实验。保留字:Petri网,PDDL,行动规划,有向模型检测1 电子邮件:stefan. cs.uni-dortmund.de2 电子邮件:shahid. cs.uni-dortmund.de1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.07.0234S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)31引言计算机科学中的一些问题可以归结为状态探索问题:给定一个状态空间和一对起始状态s和目标状态t,搜索一条起始于s,终止于t的路径。有时,状态空间是预先提供的,例如在路由系统中-我们将这种状态空间称为显式状态空间。另一方面,状态空间也可以由初始状态提供,并补充一组规则以生成其余状态。这种状态空间被称为隐式状态空间。有几种方法来表示帮助生成空间的规则集(也称为模型)。广泛使用的有:布希自动机、克里普克结构、Petri网等。Petri网是特殊的,因为它们可以很容易地用来表示无限状态空间。 模型检查[9]和人工智能搜索[36]是两个经常遇到隐式状态空间的学科。粗略地说,模型检查是一个验证给定模型中属性正确性的过程模型检查的成功主要是由于在大型设计中检测到细微的错误,同时提供反例作为错误的一般来说,并发系统中的正确性属性在某些时态逻辑中指定通常,要发现的错误是单个状态上的相当简单的条件,例如死锁外观或不变的违规。人工智能搜索,特别是行动计划,旨在找到一系列行动,从初始情况到满足预期目标条件的状态。如今,规划域描述语言(如PDDL2.1 [23]和PDDL2.2 [16])可以简洁地描述非常不同的探索问题,并且当前的AI规划系统能够探索这些问题域中的状态空间通过模型检查进行规划的方法列表包括使用控制规则进行规划[29,1,30]和应用于AI规划问题的符号模型检查[14,8,7,35,6]。在过去的几年里,有一个上升的趋势,统一的探索方法,已经开发的模型检查和人工智能搜索。最有效的方法之一,称为定向模型检查[19],使用A*[32]等 AI启发式搜索算法探索状态空间基本上,这个想法是应用算法,利用正在解决的问题的信息,以指导探索过程。这样做的好处是双重的:减少了搜索时间(更快地发现错误),提高了解决方案的质量(反例更短)。Petri网[34]反映了一种简单但有效的图形建模形式,用于模型检查的限制形式,适用于测试离散分布S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)35系统的功能正确性。一旦建模为Petri网,就可以分析系统以发现死锁,并验证活性和有界性。在本文中,我们贡献不同的算法,增强错误检测的Petri网。我们专注于发现位置转换网络中的死锁。此外,我们提供了一个合适的编码PDDL。这允许通过当前规划系统的内置算法直接应用定向搜索,绕过现有模型检查器中的大量修改。本文件的结构如下。首先,我们介绍了Petri网及其分析。接下来,我们通过定义不同的启发式估计来指导分析。我们区分可用于故障查找的一般估计和用于减少点火序列的状态到状态估计。然后,我们转向域的可能的PDDL编码。我们分离的数值域编码的命题之一,因为后者是有限的编码有界Petri网。基于这样的规划域模型,我们提出的实验和结果,我们已经得到了一个启发式搜索规划的基准集。最后,对相关工作进行了讨论并得出结论.2Petri网及其分析Petri网是由[34]发明的,作为描述分布式系统中并发和同步的一种手段。Petrinet是4元组(P,T,I-,I+),其中P ={p1,.,p n}是位置的集合,T={t1,.,t m}是具有1 ≤n,m<∞且P<$T= ∞的转移的集合。后向和前向关联映射I−和I+分别将P × T和T × P的元素映射到自然数集合,并固定Petri网的链接结构和变迁标签。3.一个Petri网是一个普通的库所变迁网,如果标签集仅限于0(省略弧)和1(存在弧)。 缓解在本文中,我们假设所有的位转移网都是普通的。在一个位置转换网络中的一个标记将P的元素映射到一个自然数,ber. 我们用M(p)表示位置p处的标记数。 是很自然假设M以向量表示提供标记对应于状态空间中的状态。 Petri网通常被提供初始标记M0,初始状态。如果转换t的所有输入位置都包含至少一个标记,则启用转换t,即,M(p)≥I−(p,t)对所有p∈P。 如果触发了转换,它从它的每个输入位置删除一个标记,并在它的每个输出位置上生成一个标记在标记m处使能的转变t可以触发并生成新的markingMJ(p) =M(p)−I−(p,t)+I+(p,t),对于所有p∈P,3.本文同时使用了Petri网和位置变迁网这两个术语6S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)3、Q、→→→Ⓧ·.....Ⓧ·你好,Ⓧ.....Ⓧ......Ⓧ,,,,,,,Ⓧ. . .你好,、、、ııı、、、、、、....... .、、但是,、、、、,,。,。、、、Q,ıııQQ,Q,Q. .Q,,、、、、 . .. .、、,,,、、...... ,。、、,你...你好。.. .、、,,别这样,别这样,... .... .,,、、、好 吧,好吧,,,。. . 、、、、、、你好,. . .、、、、、、、、、Q, 你好,但是,奎尔,Q,r,.、、、、、、但是,、、、、、、Qrr,、、、、、、Qrr,,你好,,,你好,,你好,但是,、、、、、、、、、、、、、、、、、、Q,Q,QQQ,Q,Fig. 1. 2个和4个用餐哲学家的位置转移Petri网。M→MJ。 一个标记MJ是从M可达的,如果M≠MJ,其中是的自同构和传递闭包。 地方的可达集R(N)转移网N是从M0可到达的所有标记M的集合。一个库所变迁网N是有界的,如果对所有库所p存在一个自然数k,使得对R(N)中的所有M,我们有M(p)≤k。 一个过渡t是活的,如果在R(N)中的所有M都有一个MJ,其中M∗ MJ和t在M j中使能。如果所有的变迁t都是活的,则一个位置变迁网N是活的。 一个射击序列σ = t1,.,t n从M0开始是一个有限的跃迁序列,使得t i在M i−1中使能,M i是在M i−1中激发t i的结果。在复杂系统的分析中,放置模型条件或对象(如程序变量),改变条件和对象的值的转换模型活动,以及表示条件或对象的特定值(如程序变量的值)的标记Petri网的图形表示包括用于位置的圆圈、用于标记的点、用于转换的矩形以及用于位置和转换之间的弧的箭头图1中给出了一个普通的地点变迁Petri网的例子,用于有2个和4个哲学家的哲学家用餐的例子。不同的哲学家对应不同的列,而行中的位置表示他们的状态:思考,等待和进食。对于2个哲学家的情况,标记对应于系统的初始状态,而对于4个哲学家的情况,我们显示了导致死锁的标记。Petri网有两种不同的分析方法,可达集分析和不变量分析。后一种方法更多地集中在Petri网结构本身。不幸的是,不变量分析仅适用于研究|P| × |S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)37不|是容易处理的本文主要研究可达集的分析召回8S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)3在一个位置变迁网络中,一个节点的标记数不是先验有界的,所以可能的状态数是无限的。尽管如此,存在即使在无界位置转换网的情况下也终止的状态空间探索算法。主要思想是包括部分标记,将该算法从一个由标记M0组成的可达集R开始,生成一个可覆盖集树 非确定性地,在叶处选择R中的部分标记M,并且对于所有启用的转换t,通过触发t来生成新的部分标记Mj,并将其包括在树中。如果在从M0到MJ的路上有一个标记Mjj,其中MJJ≤MJ且M(p)MJ(p),则我们将MJ(p)设为ω。<显然,如果没有节点包含ω,则位置-变迁网是有界的。在我们开始讨论Petri网中的逻辑学之前,我们需要澄清在Petri网的上下文中,人们对目标条件目标条件基本上是表示Petri网建模的系统的某些属性的标记我们区分了两种目标条件:specific-表示网络中的显式标记,或general-表示一组不同的标记,例如,系统中的僵局3Petri网启发式是估计实现目标条件所在Petri网的上下文中,评估函数将数值与每个标记相关联,以便优先考虑一些后继者的探索。网N中的最短路径距离δN(M,MJ)定义为M和MJ之间的最短射击序列的长度。距离是无限的,如果在M和MJ之间不存在发射序列。此外,δ N(M,N)是从M开始的到达满足条件N的标记的最短路径,即,δN(M,Mj)=min{δN(M,MJ)|MJ|{\fn黑体\fs19\bord1\shad1\1cHD8AFAF\4cHC08000\b0}.随 后 , 利 用 M 估 计 δN(M,λ).它是容许的,如果h(M)≤δN(M,n),并且单调的,如果h(M)−h(MJ)≤1,对于M的后继标记MJ。对所有Mj满足h(MJ)= 0的单调算法|#21453;,是可以接受的。我们区分两种搜索场景。在解释模式中,我们探索的可达标记的集合,只有什么样的错误φ的知识,我们的目标。在这个阶段,我们只对快速找到这样的错误感兴趣,而不是针对简洁的反例触发序列。对于故障查找模式,我们假设我们知道错误发生的标记这种知识可以通过模拟、测试或解释模式下的先前运行来推断。为了减少射击序列,S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)39需要两个标记。由于算法及其属性与Promela [19,20]中为通信协议设计的算法及其属性具有相似性,因此3.1汉明距离一个非常简单的启发式估计是汉明距离启发式Σh H(M,MJ)= [M(p)MJ(p)].p∈ P这里,[M(p)]的真理MJ(p)]是在{0,1}中的一个整数。As转换可以一次添加/删除多于一个令牌既不可信也不一致然而,如果我们将hH(M,MJ)除以变迁的最大感染位置数,我们就得到了一个可接受的值。在4个哲学家用餐的例子中,我们得到了一个初步估计,4,它与死锁的最短触发距离3.2子网距离近似M和MJ之间的距离的更详细的启发式算法如下工作。它通过抽象函数φ将库所变迁网络N投影到φ(N)上,省略了一些库所、变迁和相应的弧。此外,标记M和MJ的初始集合被简化为φ(M)和φ(MJ)。例如,图1实际上是其右侧的4-Dining Philosophers位置转换网络的抽象子网距离启发式现在可以定义为从φ(M)到达φ(MJ)所需的最短路径距离,形式上hφ(M,MJ)=δφ(N)(φ(M),φ(MJ)).在4个哲学家用餐的例子中,我们得到的初始估计为2。不难看出,由此获得的启发式估计是可接受的,即。,δN(M,MJ)≥δφ(N )(φ(M),φ(MJ)). 设M为当前标记,MJJ为它的直接后继者。为了证明启发式hφ是相容的,我们需要证明hφ(M)−hφ(MJJ)≤1。利用hφ的定义,我们可以说,δφ(N)(φ(M),φ(MJ))≤1 +δφ(N)(φ(MJJ),φ(MJ))上述不等式总是成立的,因为从φ(M)到φ(MJ)的最短路径成本不能大于穿过φ(MJ J)的最短路径成本(三角性质)。为了避免重新计算,在搜索之前预先计算距离并使用表查找来指导探索是合适的。的10S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)3子网距离启发式完全探索了φ(N)的可覆盖图,并在其上运行最短路径算法。这种想法被称为模式数据库构建,可以追溯到[11]。如果我们应用两个不同的抽象φ1和φ2来保持可容许性,我们只能取它们的最大值,即,HMax (M,M J)= max {h φ(M,M J),h φ(M,MJ)}.φ1,φ21 2然而,如果φ1和φ2的支撑不相交,即, 对应的位置集和转移集是不相交的φ1(P)<$φ2(P)=<$和φ1(T)<$φ2(T)=<$,两个独立的矩阵h添加 (M,MJ)=hφ(M,MJ)+hφ(M,MJ)φ1,φ21 2还是可以接受的如果我们对前两个和后两个哲学家使用抽象,我们得到4个点火转移的完美估计。3.3主动启发式虽然上述两种算法测量从一个标记到另一个标记的距离,但通过取当前状态到满足期望目标的所有可能标记的距离的最小值来将它们扩展到目标并不困难。然而,当我们专注于死锁时,可以建立绕过目标集枚举的专门在Petri网中,如果没有转换可以触发,就会发生死锁。因此,对死锁的简单距离估计就是计算活动转换的数量。换句话说,ΣhA(M)=t∈Tenabled(t).与汉明距离一样,启发式既不一致也不可接受,因为一个触发转换可以改变多个转换的启用。对于我们的运行示例,我们在初始状态中发现了4个活跃的转换4Petri网PDDL为规划领域及其相应问题提供了一种建模形式基于PDDL的计划器采用PDDL编写的域文件和在域文件中,提供了对象类型、谓词和动作,而问题文件包含对象本身、初始状态和目标指定。在下文中,我们推导出Petri网的2级PDDL 2.2模型[16],S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)311(:action fire-transition:参数(?t -跃迁):先决条件(forall(?p -位置)(or(不(传入?p?(t))(>)代币数量?p)0):影响(forall(?p-place)(when(incoming?p?t)的范围内(减少(代币数量?p)(forall(?p -位置)(when(outgoing?是吗?p)的范围内(增加(代币数量?(p)图二、Petri网变迁的数值规划算子然后将其简化为与命题规划形式主义兼容[22]。4.1数字编码在PDDL2.2编码中,我们声明了两种对象类型place和transition。 来描述网络的拓扑结构谓词(传入?地点?t - transition)和(outgoing?地点?t -跃迁),表示为I−和I+。如果所有隐式转换的权重为1,则所有隐式转换的权重都为1。 唯一需要的数字信息是一个地方的代币数量。这种标记映射是通过标记谓词(标记数?p-位置)。图2显示了转换触发操作符。初始状态对网络拓扑和初始标记进行编码。 它将实例指定为传入和传出的谓词以及指定M0的数值谓词(令牌数)。转换被阻塞的情况可以在PDDL2.2中使用派生谓词建模,如下所示(:派生块(?t -跃迁)(存在(?p -位置)(and(传入?p?t)(=(令牌数?p)0)因此,要指定为目标条件的死锁推导如下(:派生死锁(forall(?t -跃迁)(阻塞?(t)很明显,PDDL编码继承了与原始位置转换网络的一一对应关系。4.2命题编码ADL [33]描述是灵活的规划形式主义,允许更多涉及的命题运算符声明,包括否定和析取12S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)3(:action fire-transition:参数(?t -跃迁):前提条件(forall(?p -位置)(or(不(传入?p?t))(存在(?n-数字)(and(代币数量?p?n)(is-not-zero?(n):效果(和(forall(?地点?n1?n2-数字)(当(and(传入?p?t)(inc?n1?n2)(令牌数?p?n2))(and(不是(令牌数?p?n2))(令牌数?p?n1)(forall(?地点?n1?n2-数字)(当(and(outgoing?是吗?p)(inc?n1?n2)(令牌数?p?n1))(and(不是(令牌数?p?n1))(令牌数?p?n2))图三. Petri网变迁的命题规划算子。前提条件、条件效应和对象的普遍/存在量化。它们包含在1级PDDL2.1/2.2中。为了将上述编码简化为命题编码,我们可以在一个位置使用标记的一元编码,其中对象为0,1,2等,类型为number,谓词(is-not-zero?n-数字),(inc?n1?n2-number),具有明显的语义。触发操作符如图3所示。4.3隐式规划启发法将Petri网建模为规划问题的最大优点是能够利用为规划问题提出的大量知识组合最新的前向链规划器应用松弛规划器的变体[27]。(STRIPS)作用a=(pre(a),add(a),de l(a))定义为dasa+=(p re(a),ad d(a),n)。 规划的再解释问题是通过用放松的对应物替换所有动作来完成的。任何解决方案,解决了原来的计划,也解决了放松的一个;和所有的先决条件和目标可以实现,当且仅当他们可以在reelaxedtask。Valueh+被定义为解决松弛问题的最短计划的长度最优地求解松弛计划在计算上仍然是困难的[5],但是要确定的决策问题,如果松弛计划问题至少有一个解,则在计算上是易于处理的。估计是扩展到具有数值状态变量的规划问题[25],并进一步扩展到非线性任务[15]。上述所有证据都是不可接受的。一致启发式的替代设计是HSP启发式[4]和规划模式数据库S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)313启发式[12],将5实验我们进行了我们的实验上奔腾4,3.2 GHz的2 GB的主内存运行Linux操作系统。作为规划器,我们使用的propo- sitional启发式搜索前向规划系统FF。它应用松弛规划启发式来指导搜索。该系统不支持派生谓词,我们用普通的操作符编码阻塞和死锁条件,派生谓词作为唯一的结果。我们首先在2和4个哲学家的案例中测试了规划器规划器使用最小数量的触发转换立即发现了死锁。为了进行广泛的测试,我们使用了Corbett [10]收集的一组死锁检查基准。这些是从通信状态机转换而来的1-安全位置转换网[31]。回想一下,一个网络被称为1-安全的,如果M(p)≤1,对于所有p。同样的基准已经用answer set解决在[24]中基于有界模型检查(BMC)的编程1-安全网的射击动作的编码在附录中给出。表1显示了我们的实验结果。除了网络的大小,我们还显示了检测死锁的触发序列的长度,以秒为单位的CPU时间和探索状态的数量。在最后一列中,我们展示了[24]中使用BMC方法产生的运行时间。这种比较必须小心处理,因为他们使用的计算机是运行Linux的450 Mhz Pentium III。与[24]相比,我们的结果显示建立踪迹的CPU时间有了显着的增加。我们还发现,由规划器产生的反例与模型检查器产生的反例相当6相关工作为了得到更小的网络结构,文献中已经提出了不同的变换如果一个变换保持活性和有界性,则称它是相容的。没有一组规则是完整的,因为应用这些规则可以生成一个有限的小的原型位置转换网集,并且知道它的活性和有界性。约简规则通常删除网络中的节点及其所有传入和传出弧以及随后的孤立节点。约简规则修改Petri网结构和存在于网中的标记。例如,简单的规则如下:删除所有没有传入位置的转换,与所有传出位置一起删除所有没有传入转换的位置14S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)3问题#地点#Trans.Sol. Len.时间FF失效编号时间BMCDARTES(1)33125720.286.5DP(6)362460.08110.1DP(8)483280.08150.3中文(简体)6040100.08193.3中文(简体)7248120.0823617.4电梯(1)6399110.03450.4电梯(2)146299160.2743.9电梯(3)327783182.08106139.0中文(简体)12777260.11271.0HART(50)252152510.28525.7HART(75)377227760.717715.5HART(100)5023021011.4510245.9中文(简体)122172100.131587.2MMGT(4)7361,939120.2241,874.1Q(1)163194210.252582,733.7发送(25)1045530.0950.0发送(50)1798030.150.0发送(75)25410530.1450.0发送(100)32913030.1850.0SPD(1)333940.0850.0表1Petri网基准问题的规划结果以及所有传出转换,并且如果存在两个不同的并行位置(相同的连接结S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)315构),则删除具有更多令牌的那个不难看出,所有这些规则都是一致的[2]。在Petri网实践中,已经提出了其他几个局部规则[3]。与抽象算法的工作相反,我们关注的是激发序列的长度,而不是保持活性和有界性。16S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)3所提出的PDDL建模方法与其他将模型检查问题规范转换为规划者输入的方法集成良好第一种方法是将通信协议规范从Promela(模型检查器SPIN[28]的输入语言)转换为PDDL [13]。通过两个可扩展的协议设计,即哲学家用餐问题的死锁解决方案和光学电报协议,该领域被作为国际规划竞赛IPC-4的基准 [26]。下一个方法是将可能是最灵活的模型检查场景转换为PDDL:图转换系统[17]。在图转换系统(GTS)中,状态本身就是图,状态转换对应于(部分)图态射。目标可以是精确匹配、子图或子图的图同构。利用命题和动作的参数化描述以及当前PDDL的量化选项,GTS的语法和不同的目标可以保持在一个紧凑的形式中。该场景限制于解决关于某些成本代数的优化问题[18]。在PDDL编码的两种情况下,遇到的一个限制是静态状态描述符,这是PDDL当前表达能力所固有的。尽管如此,限制到有限模型对于模型检查实践中出现的许多情况是足够的。[21]在规划器To- kenPlan中,它是应用现有的Petri网技术来解决PDDL中的命题规划问题的逆方法转录是自动化的,每个谓词由一个位置表示,每个动作作为一个转换来实现。运算符的加法项通过在命题的对应位置处具有标记集来匹配Petri网语义对于被删除的命题,不需要修改,而对于被保留的命题,插入从过渡到前提条件列表的向后弧。TokenPlan中的规划过程模拟了Graphplan的工作,并构建了一个分层的搜索空间,其中包含命题和运算符层第一次的实验结果是有希望的,但在第三届国际规划竞赛中,该方法是不够有效的,比较possible与国家的最先进的启发式搜索规划。7结论我们已经展示了一个灵活的方法来分析Petri网的有向搜索方法和人工智能规划技术。这是相当简单的,但作为S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)317在有向模型检验中用其它方法示出,即使简单的估计也可以导致状态空间大小的急剧减小。与通过模型检查结合改进规划的方法相比,我们考虑通过规划进行模型检查据作者在介绍逻辑学时,我们将注意力限制在死锁性质上。然而,包括关于在特定位置p处的to-kens数量m的断言并不复杂。对于数字编码,我们只需在目标描述中添加一个条件(<=(number-of-tokensp)m)。 在命题编码中,我们简单地用(number-of-tokensp mark)代替这个条件,其中mark是表示m的number类型的对象。虽然仅限于简单的位置转换网,但将我们的设置扩展到着色Petri网并不困难,在着色Petri网中,位置处的每个标记都有一种特定的颜色。现在,转换会根据颜色进行发射。每一个着色Petri网都可以唯一地展开为一个库所变迁网,而库所变迁网的颜色编码有不同的选择。引用[1] Bacchus,F.和F. Kabanza,使用时间逻辑来表达搜索控制知识的规划,人工智能116(2000),pp。123-191。[2] Berthelot , G. , 使 用 转 换 检 查 网 的 属 性 , 在 : Advances in Petri Nets 1985 , LNCS222(1985),pp. 19比40[3] Berthelot,G.,网的变换和分解,在:Petri网的进展1986,LNCS254(1987),pp. 359-376.[4] 博内湾和H. 12. Geenner,Planning as heuristic search,Arti Ficial Intelligence129(2001),pp. 5-33[5] Bylander,T.,《命题规划的计算复杂性》(The Computational Complexity of PropositionalPractice Planning),《人工智能》(Arti Ficial Intelligence),1994年。165-204.[6] Cimatti,A.,E. Giunchiglia,F. Giunchiglia和P. Traverso,通过模型检查进行规划:AR的决策程序,在:欧洲规划会议(ECP),1997年,pp.130-142[7] Cimatti,A.和M. Roveri,Conformant planning via model checking,in:European Conferenceon Planning(ECP),1999,pp. 21比33[8] Cimatti,A.,M. Roveri和P. Traverso,基于OBDD的非确定性域通用计划的自动生成,在:国家人工智能会议(AAAI),1998年,第100页。875-881[9] Clarke,E.,O. Grumberg和D.Peled,[10] 科 贝 特 , J. , Evaluating deadlock detection methods for concurrent software , IEEETransactions on Software Engineering22(1996),pp. 161-180[11] Culberson ,J. C.和J. Schae Schuyer,Pattern databases,Computational Intelligence14(1998),pp. 318-33418S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)3[12] Edelkamp,S.,规划模式数据库,在:欧洲规划会议(ECP),2001年,页。13-24[13] Edelkamp,S.,Promela规划,在:模型检查软件研讨会(SPIN),2003年。[14] Edelkamp,S.,驯服数字和持续时间在模型检查综合规划系统,期刊的人工研究(JAIR)20(2003),页。195-238[15] Edelkamp,S.,将放松规划启发式推广到非线性任务,见:德国人工智能会议(KI),2004年,198[16] Edelkamp,S. J. Ho Jummann,The classical part of ipc-4:An Overview,Journal of Artificial Research(2005),special Track on the 4th International Planning Competition.[17] Edelkamp,S.,S. Jabbar和A. Lluch-Lafuente,图转换系统的行动规划,在:自动规划和调度国际会议(ICAPS)。2005年,基于模型的计划和调度系统的验证和确认研讨会。[18] Edelkamp , S. , S. Jabbar 和 A. Lluch-Lafuente , Cost-algebraic heuristic search , NationalConference on Arti-ficial Intelligence(AAAI),2005年,pp. 1362-1367年。[19] Edelkamp , S. , S. Leue 和 A. L. Lafuente , Directed explicit-state model checking in thevalidation of communication protocols , International Journal on Software Tools forTechnology Transfer(STTT)5(2003),pp. 247-267[20] Edelkamp,S.和A. Lluch-Lafuente,有向模型检验中的抽象,载于:ICAPS-将规划理论与实践相,2004年。[21] Fabiani,P.和Y. Meiller,用代币规划:满意度和优化之间的方法,在:欧洲人工智能会议。2000年“规划、时间安排和设计的新成果”讲习班。[22] 菲克斯河和N. Nilsson,Strips:A New Approach to the Application of Theorem Proofing toProblem Solving,Arti Ficial Intelligence2(1971).189-208.[23] 福克斯,M。和D. Long,PDDL2.1:PDDL的扩展,用于表达时间规划域,Journal of Arti FicialResearch(2003),第三届国际规划竞赛特刊。[24] 他是一个很好的朋友。 和我。陈文龙,陈文龙,等.知识表示与推理.北京:计算机科学出版社,2001.90比96[25] Ho Bertmann,J.,Metric FF规划系统:将“忽略删除列表”翻译291-341.[26] 我 是 J. 、 R.E n g lert , F.Liporace , S.这 是 一 个 很 好 的 例 子 。 Tru? g ,Engineeringbenchmarksfororplanning : The domains used in the classical part of IPC-4(2005),draft.[27] Ho Bertmann,J.和B. Nebel,Fast plan generation through heuristic search,Journal of Artificial Intelligence Research(JAIR)14(2001),pp.253-302.[28] Holzmann,G.,“The Spin Model Checker: Primer and Reference Manual,” Addison-Wesley,[29] Kabanza,F.,M. Barbeau和R. St-Denis,Planning control rules for reachtive agents,Artificial Intelligence95(1997),pp. 67比113[30] Kvarnstrm,J.,P.你好,我是P。Haslum,ExtendingTALplannerwithconcurrencyandresources , in : European Conference on Arti fficialIntelligence(ECAI),2000,pp.501-505[31] Melzer , S.和 S 。 R ? omer , Deadlockcheckingusinnetunfoldings , in:InternationalConferenceon Computer Aided Verification(CAV),1997,pp.172-183.[32] Pearl,J.,S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)319[33] Pednault,E. 警 察局 ,ADL :Exploring the Middleground between WARNPS and SituationCalculus,in:Knowledge Representation and Reasoning(KR)(1989),pp.324-332.[34] Pettri,C. A. ,“K om mum un i ka t i o n mi t A u toma t e n,“Ph. D. 她的妹妹,《一个孩子》(1962年)。[35] Pistore,M.和p.Traverso,Planning as model checking for extended goals in non-deterministicdomains,in:International Joint Conference on Arti ficial Intelligence(IJCAI),2001,pp.479- 486[36] 罗素,S。和p.Norvig,20S. Edelkamp,S.Jabbar/Electronic Notes in Theoretical Computer Science 149(2006)3附录(:action fire-transition:参数(?t-跃迁):前提条件(forall(?p -位置)(or(不(传入?p?(t))(标记?(p)):效果(和(forall(?p -位置)(when(和(传入?p?t)(标记?p))(不(标记?(p)(forall(?p -位置)(when(和(outgoing?是吗?p)(没有
下载后可阅读完整内容,剩余1页未读,立即下载
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)