（计算机软件与理论专业论文）基于规划图的时态推理与时态规划.pdf

摘要 基于规划图的时态推理与时态规划 专业：计算机软件与理论 博士生：伍丽华 导师：姜云飞教授 摘要 智能规划是人工智能的一个重要研究领域，智能规划的主要思想是根据预定 实现的目标，对若干可供选择动作及所提供的资源限制进行推理，得到实现目标 的动作序列。近几年来，为了表示规划过程中产生的条件因素和动态信息，大量 的研究工作围绕条件效果、不确定性和时态规划等情况展开，同时，一些高效算 法的提出也大大推动了智能规划的研究从经典问题向实际规划问题的转移，智能 规划研究的课题不断地由理论研究领域走向实际应用领域。 在时态规划方面，由于许多现实世界中的规划问题通常希望规划目标能在尽 可能短的时间内实现，并且规划过程中存在大量能并发执行的持续性动作，这些 动作的执行需要考虑时间、资源的消耗。这类规划问题，用经典规划中带瞬间动 作的s t r i p s 模型是无法进行表示的，因此，为表示实际规划问题，需要对时间 信息进行有效表示，并能进行时序约束推理。国际标准规划语言p d d l 2 1 版本即 是在原来规划语言基础上增加了对持续性动作和数值量词的支持，这方面的规划 领域问题在历届国际规划大赛中非常受重视。但目前现有的时态规划算法的效率 以及规划过程中时态推理的技术及其运用都难以令人满意。为此，本文在时态推 理技术和时态规划问题的求解方法两个方面进行了研究。 在时态推理技术研究部分，本文首先介绍了经典规划的概念模型，以及其受 限和扩展模型，指出了时态规划所需要解决的技术问题。规划图是图规划技术中 的数据结构，传统规划领域中难以处理的动作和状态之间可能存在的互斥关系均 能简洁地表示在规划图上，本文在规划图框架下，定义了动作图，并进一步扩展 摘要 为时态动作图，使之能体现时态规划问题中的时态信息。在此基础上，提出了一 种对时态信息进行表示与管理，并且能够进行时态约束推理的时态一致性赋值方 法；约束可满足问题( c s p ) 是一个通用的且功能强大的问题求解的范例，在规 划问题中，时态关系可以用c s p 技术和方法方便地表示和处理。本文利用c s p 技 术对时序约束进行处理，包括过滤、约减及时态信息的一致性检验，使时态推理 技术能更好地应用于时态规划的求解过程中。 在求解时态规划问题实现部分，本文首先综述了经典时态规划的技术方法， 对目前比较受关注的、性能较好的时态规划器从技术方法上进行了研究分析；对 p d d l 2 1 语言所描述的支持持续动作的规划领域问题，利用遗传算法实现求解时 态规划的算法。算法针对基于规划图的遗传规划技术存在局部搜索能力不足的缺 点，提出了在原有遗传操作算子的基础上，引入局部修复算子的混合规划技术， 这种方法的优点在于能够在规划求解中对时态信息进行处理，减少冗余和不一致 的时态信息，提高了求解效率，同时利用遗传规划算法能够避免局部搜索的不足， 实验表明，这种算法能有效地处理一类时态规划问题。 关键词规划图，时态动作图，时态推理技术，c s p 技术，一致性时态赋值，时 态规划，遗传算法，局部修复算子。 摘要 r 一 - 1e m p o r a lr e a s o n i n ga n dp l a n n i n gb a s e do nt h ep l a n n i n gg r a p h 一一一 一 一 m a j o r ： n a m e ： s u p e r v i s o r ： c o m p u t e rs o f t w a r ea n dt h e o r y l i h u a w u p r o f e s s o ry u n f e ij i a n g a b s t r a c t a u t o m a t e dp l a n n i n gi so n eo ft h em o s ta c t i v et o p i c si na ir e s e a r c h i ti st h e r e a s o n i n gp r o c e s st h a tc h o o s e sa n do r g a n i z e sa c t i o n sw h i c hw o u l da c h i e v es o m e p r e s t a t e do b j e c t i v e sb ya n t i c i p a t i n gt h e i re x p e c t e do u t c o m e s i nr e c e n ty e a r sr e s e a r c h i nt h ep l a n n i n gc o m m u n i t yh a sm o v e di n c r e a s i n g l yt o w a r d sa p p l i c a t i o no f p l a n n e r st o r e a l i s t i cp r o b l e m si n v o l v i n gc o n d i t i o n a l e f f e c t ，p l a n n i n g u n d e ru n c e r t a i n t ya n d t e m p o r a lp l a n n i n g ，f o rd e s c r i b i n gt h ec o n d i t i o nf a c t o r sa n dd y n a m i ci n f o r m a t i o n w i ms o m ee f f i c i e n c ya p p r o a c h e so fp l a n n i n gp r e s e n t e d ，m a n yi n t e l l i g e n tp l a n n i n g t o p i c sg ot op r a c t i c a lp l a n n i n gd o m a i nf r o mc l a s s i c a lp l a n n i n ga n dt or e a lp r a c t i c a l d o m a i nf r o mt h e o r e t i c a lr e s e a r c h t e m p o r a lp l a n n i n gi sab r o a dr e s e a r c ha r e ai ni n t e l l i g e n tp l a n n i n g i nm o s t r e a l - w o r l da p p l i c a t i o n s ，m o d e l i n gt e m p o r a la n dn u m e r i c a li n f o r m a t i o ni na u t o m a t e d p l a n n i n gi si m p o r t a n tf o rr e p r e s e n t i n gr e a l w o r l dd o m a i n s ，w h e r em a n yr e a lp l a n n i n g p r o b l e m so f t e nr e q u i r et h ep l a n n i n gg o a l sc a nb es a t i s f i e di ns h o r t e rt i m e ，a n da c t i o n s t a k et i m ea n dc o n s u m er e s o u r c e s ，a n dt h eq u a l i t yo ft h es o l u t i o n ss h o u l dt a k et h e s e a s p e c t si n t oa c c o u n t t h e s ep l a n n i n gd o m a i n sn e e dt ob es p e c i f i e di nt h er e c e n t p d d l 2 1l a n g u a g es u p p o r t i n gd u r a t i v ea c t i o n s ，f o rt h et e m p o r a li n f o r m a t i o na n d t e m p o r a lc o n s t r a i n t sc o u l dn o tb es p e c i f i e di ns t r i p sm o d e lo fc l a s s i c a lp l a n n i n g i n t h i sp a p e r , w ef o c u so np l a n n i n gi nt e m p o r a ld o m a i n sa n ds t u d yt h et e m p o r a l r e a s o n i n gt e c h n i q u e sa n dt e m p o r a lp l a n n i n ga p p r o a c h e s 摘要 i np a r to ft e m p o r a lr e a s o n i n gw ei n t r o d u c eat e m p o r a la c t i o ng r a p hr e p r e s e n t a t i o n a n dam e t h o df o rm a k i n gt i m ee x p l i c i tt r a d e rt h ep l a n n i n gg r a p h ，a n dg i v i n gan e w t e m p o r a l c o n s t r a i n tr e a s o n i n gt e c h n i q u e st oh a n d l ed u r a t i v ea c t i o nd u r i n gt h e c o n s t r u c t i o no fap l a n b yg e n e r a lc s pt e c h n i q u e sw ep r e s e n ts o m ea l g o r i t h m st o m a n a g et e m p o r a li n f o r m a t i o na s s o c i a t e dw i t hf a c t sa n da c t i o n si nat e m p o r a lp l a nf o r f i l t e r i n gt h ed o m a i n sa n dc o n s t r a i n t sa n df o rc o n s i s t e n c yc h e c k i n g t h e s et e c h n i q u e s a l ef u l l yi m p l e m e n t e da n di n t e g r a t e di no u ra p p r o a c h e s i np a r to ft e m p o r a lp l a n n i n gw ef i r s td e v o t et oab r i e fp r e s e n t a t i o no ft h er e l a t e d a p p r o a c h e st ot e m p o r a lp l a n n i n g ，a n dg i v ea na n a l y s i sa b o u ts o m et e m p o r a lp l a n n e r s t h e nw ep r e s e n tat e m p o r a lg e n e t i cp l a n n i n ga l g o r i t h mw h i c he x t r a c tav a l i dp l a n n i n g s o l u t i o nf r o map l a n n i n gg r a p hu s i n gg e n e t i ca l g o r i t h mu n d e rt h ef r a m e w o r ko f t e m p o r a lp l a n n i n gg r a p ha n dc a p a b l eo fr e a s o n i n ga b o u tt h et e m p o r a lc o n s t r a i n t h i s a p p r o a c hc o m b i n et h el o c a lf i xo p e r a t o rw i t ht h et r a d i t i o n a lg e n e t i co p e r a t o r st o s t r e n g t ht h ec a p a b i l i 锣o fi t sl o c a ls e a r c h ，s ot h a tt h ea l g o r i t h m sc a l lc o n v e r g ef a s t e r a n df i n dap l a n n i n gs o l u t i o nf i n a l l y t h ee x p e r i m e n t ss h o wi tc a ns o l v ee f f i c i e n t l ya k i n do fs i m p l et e m p o r a lp l a n n i n gp r o b l e ma n di sm o r ee f f i c i e n c yt h a no t h e rc l a s s i c a l p l a n n i n ga p p r o a c h e s k e yw o r d sp l a n n i n gg r a p h ，t e m p o r a la c t i o ng r a p h ，t e m p o r a lr e a s o n i n gt e c h n i q u e s , c s pt e c h n i q u e s ，c o n s i s t e n c yt e m p o r a l a s s i g n m e n t ，g e n e t i ca l g o r i t h m s ，t e m p o r a l p l a n n i n g ，l o c a lf i xo p e r a t o r i v - 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：红 ， 日期：200 8 年10 月 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规 定，即：学校有权保留学位论文并向国家主管部门或其指定 机构送交论文的电子版和纸质版，有权将学位论文用于非赢 利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文。 学雠文储始飞嘞 日期：200 8 年10 月2 0 日 1 导师签名：蒜乜 日期：200 8 年10 月20 日 第一章引言 第一章引言 1 1 智能规划及其研究课题 智能规划( a ip l a n n i n g ) 是人工智能领域的一个经典问题，它的产生几乎 与人工智能同步。近年来，有关智能规划的研究在问题描述和问题求解两方面有 了新的突破，使得智能规划成为一个热门的人工智能研究领域n 3 。同时，由于智 能规划的研究对象和研究方法的转变，极大地扩展了智能规划的应用领域，目 前智能规划在生产调度、物流管理，甚至宇航技术等很多实际领域中也有着广泛 的应用，因此智能规划的理论研究和应用越来越受到众多研究者的关注。 智能规划在国外有很多专门从事智能规划方面研究的著名的学术机构和组 织，例如欧洲智能规划网p l a n e t 、英国诺丁汉大学a s a p 研究组、美国亚利桑那 州立大学y o c h a n 研究组，以及n i c t a ( n a t i o n a li c ta u s t r a li ac o n s o r t i u m ) 等等，这些协会和联盟从上世纪6 0 年代起就开始探索研究规划领域问题n 0 7 1 。近 年来，国际上对规划的研究越来越热，国际知名期刊a r t i f i c i a li n t e l l i g e n c e 近年来发表了许多篇智能规划方面的文章，并在1 9 9 5 年、2 0 0 3 年及2 0 0 8 年三 次为智能规划研究领域发专刊，可见研究者之多、研究论文之多和研究领域之重 要，此外，人工智能国际联合会议i j c a i 和a a a i 等国际会议中，规划方面的文 章为数不少。 两年一届的国际智能规划系统大赛a i p s 及自动规划和调度的国际会议 i c a p s ，为智能规划研究者提供了一个交流规划新思想、新技术的平台，在此平 台上，研究者们讨论和评测参与竞赛的规划系统，智能规划大赛为智能规划的理 论和应用研究起了很大的推动作用。 在一些大学里，不仅有越来越多的研究人员从事智能规划方面的研究工作， 而且面向大学生和研究生的智能规划方面的课程越来越多。 从文献上来看，智能规划在国内的研究相对还比较少，但近几年来，中山大 学智能规划团队的研究工作成绩斐然“一1 驯，在领域知识自动获取、动作模型学 习，以及不确定规划中扩展目标语义等方面已经进行了深入的研究。 第一章引言 在应用方面，规划技术广泛应用于工厂的作业调度、车辆调度、宇宙航行等 领域。1 9 9 8 年底，美国的n a s a 发射的d e e ps p a c eo n e 宇宙飞船的燃料自动控 制系统使用了基于s a t 的规划方法1 1 3 ，m u r p y 等人1 9 9 6 年为美国联邦太平洋 铁路建立了基于规划的自动调度系统瞳羽，k n o b l o c k 等人用规划方法解决q u e r y p l a n n i n g 问题，是规划技术在i n t e r n e t 上的成功应用n 9 1 。 智能规划研究需要解决的问题是：对周围环境进行认识与分析，根据预定实 现的目标，对若干可供选择的动作及所提供的资源限制进行推理，综合制定出实 现目标的动作序列。简单地说，智能规划就是关于动作的一个推理过程。目前智 能规划研究的课题主要有下面几个方面。 智能规划技术的研究。 规划的搜索技术，求解效率的研究。 领域知识在规划中的应用研究。 在规划中使用机器学习技术。 时态与资源约束规划。 不确定性规划。 基于模型检测的规划。 规划的产生，执行与监视。 规划的应用研究。 近几年来，为了表示规划过程中产生的条件因素和动态信息，大量的研究 工作围绕条件效果( c o n d i c t i o n a le f f e c t ) 口7 8 4 非确定性( u n c e r t a i n t y ) 嘶瑚1 和 时态与资源约束( t e m p o r a la n dr e s o u r c ec o n s t r a i n t s ) 乜卜眠9 1 1 等情况展开，与 此同时，一些高效算法的提出川7 9 h 们h 一1 2 1 也大大推动了智能规划的研究从经 典问题向实际应用问题的转移，智能规划研究的课题不断地由理论研究领域走向 实际应用领域。 1 2 时间和资源约束规划研究现状 时间和资源约束规划是智能规划面向实际应用而产生的一种规划。在现实世 界中，许多规划问题受外部事件和动态信息的影响，时态和资源约束规划问题中 存在着大量能够并发执行的持续性动作n 们，这些动作的执行会消耗相应的时间和 第一章引言 资源，同时这类规划问题通常希望规划目标能在尽可能短的时间内实现h 引。因 此，为表示实际规划问题，需要对时态信息以及资源信息进行有效表示呻3 1 ，并且 规划动作的执行需要考虑时间与资源耗费等多种因素。对时间与资源约束规划的 研究不仅具有理论价值，在实际应用上也具有重大的现实意义。 时间与资源约束规划需要处理包含时态和数值信息，这些规划问题用经典 规划中s t r i p s 模型是无法表示的，因为在s t r i p s 模型中，动作是瞬间的，因此 一般是采用国际标准规划语言p d d l 2 1 进行描述，p d d l 2 1 版本在原来规划语言 基础上，增加了对持续性动作和数值量词的支持。处理包含时态信息的时态规划 主要解决持续动作及相关的时态信息，这也是本文重点研究和讨论的课题。而包 含数值信息的规划中，动作的执行依赖某些数值条件，且动作效果将消耗或重新 增加一些临界的连续性资源，在p d d l 2 1 中可以由数值f l u e n t 表示，这类规划 需要通过一个考虑了各种规划质量的目标函数来评判其规划解。 近年来，研究者们对基于时态和资源约束规划的课题进行了深入研究，并取 得了许多重要的成果口8 1 。智能规划大赛中，时态与资源约束规划是一个很重要的 领域，参赛的规划系统越来越多，其中l p g 规划器啪柏1 、m e t r i c f f 规划器羽和 s g p i a n n 们是众多能处理时态和资源约束规划的规划系统中，表现突出且性能较好 的规划器。 1 3 问题的提出 时态规划问题在实际应用中广泛存在，但它是异常难解的n 钔。因为对于考 虑时间约束的规划问题，其搜索空间远大于经典规划问题的搜索空间n 3 1 ，并且这 类规划问题通常还包含类似目标优化的问题。 在时态规划研究中，虽然在规划竞赛中出现了一些性能良好的时态规划器， 但目前现有的时态规划算法的效率以及规划过程中时态推理的技术及其运用都 难以令人满意。例如l p g 规划器，它是一个基于规划图、采用局部搜索方法的规 划系统，能有效地处理动作带持续时间和存在数值表达式的规划问题。虽然以 l p g 为代表的局部搜索技术被认为是非常有效的领域无关的规划技术，但从实验 结果来看，使用局部搜索技术的规划器，性能均不同程度地受到局部极小值的影 响，局部搜索是为了避免完全搜索的组合爆炸n 别，虽然能找到解时求解的效率非 第一章引言 常高，但局部搜索方法是不完备的，有解存在时它可能找不到解。因此l p g 规划 器不得不采用许多其他策略，比如提高启发式估值的精度、以一定的概率随机选 取邻节点、设立禁忌搜索列表等办法，以试图摆脱局部极小值的影响h 5 1 。 f f 是采用启发式估值的前向状态空间搜索的规划器，m e t r i c f f 是f f 的扩 展版本，增加了对m e t r i c 的处理，但在处理t e m p o r a l 时表现较弱。s g p l a n 是 基于子目标分解技术的规划器，它不对数值信息进行专门处理，数值的处理完全 依赖于底层所采用的m e t r ic f f 规划器。 文献 2 及我们曾撰文1 提出在规划图的基础上，采用遗传算法进行规划解的 搜索，并取得良好的效果。但这种遗传规划算法仅能处理经典规划问题。 1 4 本文研究目的与研究内容 针对时态规划领域普遍存在的问题，本文在时态推理技术和时态规划问题 的求解方法两个方面进行了研究，目的是要解决时态规划过程中时态信息的有效 表示，以及时序约束的推理技术，并提高时态规划求解方法的效率及处理能力。 本文是在p d d l 2 1 语言描述的规划问题的基础上研究时态规划算法，所处理 的时态规划问题遵循p d d l 2 1 领域描述语言中的假定，即动作带有一持续时间， 但不考虑在该持续时间内的中间时间点的情况。动作的前提条件和效果均在持续 时间区间的端点处被说明，并且这些前提条件和效果的取值情况将在持续时间区 间内保持不变。 本文的主要工作是在规划图框架下，对时态规划中的时态信息进行表示，并 提出一种时序约束推理方法，同时，研究了时态规划的一些求解方法，并在基于 规划图的基础上，给出了求解一类时态规划问题的算法，并通过实验验证。 本文的内容结构安排如下： 第二章介绍经典规划的概念模型及其扩展模型，综述规划与时态规划的基 本概念及规划的主要技术方法。 第三章介绍时态推理技术，并在规划图的框架下，进行适当扩展，使之能 有效表示时态规划问题中的时态信息，在此基础上建立了基于时态动作图的时态 信息的表示与管理方法，并研究了时态动作图中一致时态赋值的方法。 1 参见附录中列表【3 】 第一章引言 第四章 引入c s p 技术，并利用c s p 技术对时序约束进行处理，包括过滤、 约减及时态信息的一致性检验，使时态动作图满足一致的时序约束。 第五章综述了经典时态规划的技术方法，并对目前比较受关注的、性能较 好的时态规划器l p g 、m e t r i c f f 等从技术方法上进行了研究分析。 第六章建立基于时态动作图的遗传规划算法的设计，包括染色体的编码、 适应度函数、遗传操作算子，以及为增强遗传规划算法收敛速度而设计的局部修 复算子等，给出实现求解时态规划问题的算法，对实验结果进行收敛性分析，并 给出与相关工作的比较。 最后一章是对本文的总结，并给出对进一步工作的展望。 第二章规划与时态规划概述 第二章规划与时态规划概述 本章将介绍规划与时态规划的一些基本概况，包括规划的概念模型、规划的 技术方法，以及时态规划的相关信息。 2 1 规划的概念模型 规划的概念模型采用动态系统的一般性模型啤1 ，即状态转移系统的模型，又 称为离散事件系统，因为规划关心的是选择和组织改变系统状态的动作，这种模 型在计算机科学的其他领域也是经常使用的。 2 1 1 基本模型 定义2 1 ( 规划的概念模型) 一个规划的概念模型是一个四元组= ( s ，a ，e ，y ) ， 其中： s = - s l ，s 2 ) 是一个有限或递归可数的状态集； 彳= 口l ，q 2 ) 是一个有限或递归可数的动作集； 庐锄，p 2 ) 是一个有限或递归可数的事件集； y ：s a xe 一2 s 是一个状态转移函数。 给定一个状态转移系统，规划的目的是寻找合适的可应用的动作，施加到 某些状态上，使得系统从某些开始状态到达一些目标状态。 一个状态转移系统也可以用有向图表示，有向图的节点表示s 中的状态。如 果s l er ( s ，材) ，其中u 是一个序对( 口，p ) ，a ar e e ，那么图中包含一条从s 到s 的弧，并标记为甜，每条这样的弧被称为一个状态转移。 为方便表示，一般引入一个伪事件e ，说明状态变化仅由动作引起的，这样 r ( s ，口，e ) 可成写r ( s ，a ) ，同样地，引入一个伪动作n o - o p ，表示状态转移是因一 个事件造成的，则k s , n o - o p , e ) 可写成r ( s ，e ) 。 动作和事件都对系统的演化有影响，但动作是规划执行器可以控制的。如果 第二章规划与时态规划概述 口是一个动作且r ( s ，口) 不是空集，则称口是可应用于j 的，而且在5 中执行动作 将使系统转移到r ( s ，a ) 中的某个状态。由于事件是带有偶然性的，规划器可以考 虑事件，但不能控制事件，即无法选择和触发事件。如果e 是一个事件， y ( s ，e ) 非空，则当系统在状态s 时，e 可能发生，事件的发生使系统状态转移到r ( s ，p ) 中 的某个状态。 2 1 2 受限假设与放宽 无论在理论上还是在实际应用中，规划的概念模型都不能直接使用，具体使 用时还要对这个模型增加各种限制。应该说，规划的基本概念模型只是各种不同 的限制性假定的出发点，我们以这个模型为基础，加上各种不同的限制性假定， 将得到各种受限的规划问题。例如，经典规划就是满足8 个受限条件的模型，对 这8 个受限条件中的某个限定进行放宽，可以得到一些扩展的模型，表2 1 列出 了对规划概念模型的8 个受限假设以及相应的放宽。 表2 18 个受限假设及放宽假设 假设 受限假设放宽假设 a 1 是有限的，即是一可以是可数无穷的，放宽这个假设则需要讨论规 个有限的状态集。划的判定性问题和规划的终止问题。 a 2 是完全可观察的，即是部分可观察的，即不能确定地预见的每一个 关于的状态有一个完 动作后的状态。 整的知识。 a 3 是确定的，即如果一在静态而又不确定的系统中，每一个动作可能导致不 个动作或一事件是可应同的状态，因此规划器必须考虑不同的状态。通常不 用于一个状态的，则它确定性也需要放宽假定a 6 ，即规划解不一定是线性 的应用必将使确定性的的动作序列。 系统转移到单一的状态 上。 a 4 是静态的，即事件集是动态系统，在可能事件的一般模型中，状态中 e 为空集，系统没有外部与动作相竞争的事件可能出现，也可能不出现，即使 第二章规划与时态规划概述 动态性；系统处于同一 r ( r ( s ，口) ，u ) i l ，动态系统也是不确定的。在决定 状态，直到控制器施加是否对状态s 使用动作d 不是完全依赖规划器对状态 一些动作。转移的预测。这种情形一般需要考虑条件规划。 a 5 规划目标是受限的，即规划的目标可以扩展，即不仅对最终状态有要求，而 目标描述为一个显式目且对中间经过的状态也有要求，例如，哪些危险状态 标状态或一个目标状 是系统需要避开的，哪些状态是系统必须通过的，哪 态集品。规划器的目标 些状态系统应停留一段时间，约束系统通过的轨迹， 是任何以目标状态之一及要求对效用函数进行优化等。 结束的状态转移序列。 a 6规划解是序列式的，即规划解不仅是简单的动作序列，也可以具有复杂的数 规划的求解结果是有限学结构，例如是部分序集、集合的序列等。在其他假 动作的线性序列。定放宽时也常常要求放宽该假设，例如放宽假设a 3 ( 不确定系统) 时，也要求放宽a 6 。 a 7 隐去时间的表示，即动在很多规划领域中，动作的持续性和同步性是需要考 作和事件没有持续时虑的。当目标具有时态约束并且事件的发生具有绝对 间，都是瞬时的状态转时间参照时，也需要时间表示。但是，在状态转移模 移，模型中不显式地表型中时间被抽掉了，这种模型在把动作和事件时看成 示时间。是瞬时转移。显式的处理时间需要扩展规划的概念模 型，本文将在后面的章节中讨论这种扩展。 a 8 脱机规划，即在规划期当规划器需要考虑实际运行的细节时，它对系统的变 间，规划器不关心发生化就不能一无所知。至少它需要联机检查规划解是否 在系统的变化。只按 仍然是正确的，是否需要修改或重新规划。 给定的初始状态和目标 状态进行规划，不考虑 当前的变化。 在表2 1 中，同时满足所有限制假定a l 至a 8 的状态转移系统是最简单的 情况，我们称之为受限模型，这种系统是确定的、静态的、有限的和完全可观察 的，并且是受限目标和隐藏时间的状态转移系统。这样一个系统用= ( s ，a ，y ) 表示，而不用= ( s ，a ，e ，y ) ， 因为这里没有外部事件e 。其中s 、a 和y 第二章规划与时态规划概述 是有限的，当a 可以应用于状态s 时，r ( s ，a ) 只有一个状态。 一个受限的状态转移系统= ( s ，彳，y ) 的规划问题定义为p = ( ，s 。，g ) ， 其中s 。是初始状态，而g 对应于目标状态集合。p 的解是动作序歹l j ( a l ，a k ) ，对 应于状态转移序n ( s o ，s k ) ，满足： j l = r ( s o ，a 1 ) ，s t = r ( s k - ia i ) 并且s 。是目标状态，规划问题求解就是产生这样一个动作序列。 对某些受限假设进行放宽的模型称为扩展模型，例如本文讨论的时态规划问 题，就是对假设a 7 的放宽，即动作不再是瞬时的，动作的持续时间需要显式地 表示。 2 2 经典规划 经典规划问题是满足上述8 个限制的受限模型，其表示方法有多种，比较典 型的表示方法有集合论表示法、经典表示法和状态变量表示法嗍1 ，这里采用经典 表示法对经典规划作形式化描述。 经典规划表示中，使用了一阶逻辑中的符号体系，状态被表示成逻辑原子集 合，这些原子的真值由解释确定。动作被表示为规划操作，它能够改变这些原子 的真值。 下面是关于经典规划领域、规划问题、规划解的概念。 2 2 1 规划领域 定义2 2 ( 规划领域) 设是一个具有有限多个谓词符号和常量符号的一阶逻辑语 言。在工中，一个规划领域是一个受限的状态转移系统= ( s ，a ，) ，其中满 足： s 2 k ，其中k 表示所有三的基文字； 么= d 中操作的所有基实例 ，其中0 是操作集合； 如果a a 是可应用于s s 的，则r ( s ，a ) = 0 - e f f e c t s + ( 口) ) u ( s - e f f e c t s 一( 口) ) ， 否则r ( s ，a ) 无定义，其中e f f e c t s + ( 口) 为动作口的正效果，e f f e c t s 一0 ) 为动作a 的 负效果。 第二章规划与时态规划概述 s 对，是封闭的，即如果j s ，则对每一个可应用于j 的动作a ，z ( s ，a ) s 。 2 2 2 规划问题 定义2 3 ( 规划问题) 一个规划问题是一个三元组p = ( ，g ) ，其中 初始状态是s 中的任意一个状态； 目标g 是任意一个基文字集； s g = s ss 满足g ) 。 从定义2 2 和定义2 3 我们可以看到，规划领域= ( s ，彳，y ) 与具体的目标 和初始状态是无关的，而规划问题p = ( ，s o ，g ) 包括领域、初始状态和目标状态。 由于显式地给出s 和y 中的所有元素是不实际的，因此我们需要给出一种隐 式定义p 的办法。为此，我们使用尸的陈述( s t a t e m e n t ) 这样一个概念，定义为： 一个规划问题p = ( ，s o ，g ) 的陈述是只= ( 0 ，s o ，g ) ，p 和只可以分别看成是规划问 题的语义描述和语法描述。 规划问题的陈述只是我们将用到的语法规范，用于向计算机程序描述规划问 题尸。多个规划问题可以有相同的陈述，但如果两个经典规划问题具有相同的陈 述句式，则它们有相同的可达状态集和解集。 2 2 3 规划解 经典规划问题一般是给出初始状态集和目标状态集，然后从可操作的动作集 中选出一系列的动作，使要求解的问题通过应用这些动作可以从初始状态转换成 目标状态。 设p = ( ，s o ，g ) 是一个规划问题，如果y ( s o ，兀) 满足g ，则规划兀是尸的一个 解。如果兀的一个真子集也是尸的一个解，则称解兀是有冗余的。如果不存在尸 的一个解，该解所包含的动作比兀少，则称解兀是最小的。显然，最小的解是没 有冗余动作的，且其长度最小。 2 2 4 一个规划的例子 第二章规划与时态规划概述 例2 1图2 1 是一个码头工机器人规划问题( 简称为d w r 规划问题2 ) 。这个系 统包括一个集装箱，一个能抓起和放下集装箱的吊车，一个能把集装箱从一个地 点移到另一个地点的机器人。其中有两个地点( 1 0 c i ，1 0 c 2 ) 、一个机器人拖车( r 1 ) 、 一个吊车( c r a n e ) 、两个堆( p l ，p 2 ) 和三个集装箱( c 1 ，c 2 ，c 3 ) 。 图2 1d w r 规划问题 这里常量符号集是 l o c l ，l o c 2 ，r l ，c r a n e ，p l ，p 2 ，c l ，c 2 ，c 3 ，p a l l e t ) 。 其中p a l l e t 表示在堆的底部的托盘，如果堆p 2 是空的，则t o p ( p a l l e t ，p 2 ) 。 状态集合是 s o ，s l ，观，s 3 ，s 4 ，8 5 ) ，其中d w r 的一个状态s l 为： s l = a t t a c h e d ( p l ，l o c i ) ，a t t a c h e d ( p 2 ，l o c l ) ，i n ( e l ，p 1 ) ，i n ( c 3 ，p 1 ) ，o n ( c 3 ，e 1 ) ， o n ( cl ，p a l l e 0 ，i n ( c 2 ，p 2 ) ，i n ( c 2 ，p 2 ) ，t o p ( c 2 ，p 2 ) ，o n ( c 2 ，p a l l e t ) ，b e l o n g ( c r a n e l ， l o c l ) ，e m p t y ( c r a n e l ) ，a d j a c e n t ( 1 0 c i ，l o c 2 ) ，a d j a c e n t ( 1 0 c 2 ，l o c i ) ，a t ( r l ，1 0 c 2 ) ， o c c u p i e d ( 1 0 c 2 ) ，u n l o a d ( r 1 ) 动作集合是 t a k e ，p u t ，l o a d ，u n l o a d ，m o v e ) ，例如m o v e 、t a k e 的操作为： m o v e ( r ，脚) ；机器人拖车从地点，到相邻的地点m 。 p r e c o n d ：a d j a c e n t ( ，所) ，a t ( r ，d ，- 1 0 c c u p i e d ( m ) e f f e c t ：a t ( r ，肌) ，o c c u p i e d ( m ) ，- - , o c c u p i e d ( ) ，1 a t ( ，d t a k e ( k ，c ，d ，p ) ；在地点，的吊车k 把集装箱c 从堆p 的项部集装箱d 上拿下来。 p r e c o n d ：b e l o n g ( k ，d ，a t t a c h e d ( p ，d ，e m p t y ( k ) ，t o p ( c ，力，o n ( c ，回 e f f e c t ：h o l d i n g ( k ，c ) ，1 e m p t y ( k ) ，- 1 i n ( c ，力，- 、t o p ( c ，力，1 0 n ( c ，回， t o p ( d ，力 2 本文在后面的章节中将多次引用d w r 例子。 l l 第二章规划与时态规划概述 动作t a k e ( c r a n e l ，l o c i ，c l ，c 2 ，p 1 ) 是操作t a k e ( k ，c ，d ，力的例化，即： t a k e ( c r a n e l ，l o c i ，c l ，c 2 ，p 1 ) ；在地点l o c i 的吊车c r a n e l 把集装箱c 1 从 堆p 1 的顶部集装箱c 2 上拿起来 p r e c o n d ：b e l o n g ( c r a n e l ，l o c i ) ，a t t a c h e d ( p l ，l o c l ) ，e m p t y ( c r a n e l ) ，t o p ( c l ， p 1 ) ，o n ( c l ，c 2 ) e f f e c t ：h o l d i n g ( c r a n e l ，c 1 ) ，1 e m p t y ( c r a n e l ) ，- - , i n ( c l ，c 2 ) ，- , t o p ( e l ，p 1 ) ， - - , o n ( c l ，2 ) ，t o p ( c 2 ，p 1 ) 该动作可以应用于状态s l ，得到的结果状态为： s 3 = ) ，( s l ，t a k e ( c r a n e l ，l o c i ，c l ，c 2 ，p 1 ) ) 其中s 3 = a t t a c h e d ( p l ，l o c i ) ，i n ( c l ，p 1 ) ，t o p ( c l ，p 1 ) ，o n ( c l ，p a l l e t ) ，a t t a c h e d ( p 2 ， l o c 2 ) ，i n ( c 2 ，p 2 ) ，o n ( c 2 ，p a l l e t ) ，b e l o n g ( c r a n e l ，l o ci ) ，h o l d i n g ( c r a n e1 ， c 3 ) ，a d j a c e n t ( 1 0 c i ，1 0 c 2 ) ，a d j a c e n t ( 1 0 c 2 ，l o c i ) ，a t ( r l ，l o c 2 ) ，o c c u p i e d ( 1 0 c 2 ) ， u n l o a d ( r 1 ) 。 设d w r 问题p 的初始状态是印，目标公式是： 9 1 2 l o a d e d ( r l ，c 3 ) ，a t ( r l ，l o c i ) ) 则得到规划解为： n = t a k e ( c r a n e l ，l o c i ，c l ，c 2 ，p 1 ) ，m o v e ( r l ，l o c 2 ，l o c i ) ，l o a d ( c r a n e l ，l o c i ， c 3 ，r 1 ) ) 最后产生的状态j 5 为： s 5 = a t t a c h e d ( p 1 ，l o c i ) ，i n ( c l ，p 1 ) ，t o p ( c l ，p 1 ) ，o n ( c l ，p a l l e t ) ，a t t a c h e d ( p 2 ， 1 0 c 2 ) ，i n ( c 2 ，p 2 ) ，o n ( c 2 ，p a l l e t ) ，b e l o n g ( c r a n el ，l o