（计算机软件与理论专业论文）不确定规划中的扩展目标语义比较和观测信息约简.pdf

摘要 不确定规划中的扩展目标语义比较和观测信息约简 专业：计算机软件与理论 博上生：黄巍 导师：姜云飞 摘要 不确定规划是目阮人工智能研究领域的一个热点。在完令叮观察性的条件f 对扩展目标作规划，以及在完全可观察性( 或部分可观察性) 的条件下对可达性 目标求握规划解( 简称强解) 是其中的两个重要的不确定规划问题。 在完全可观察性的条件下对扩展f 1 标作规划时，扩展目标常常体现为时态逻 辑公式，特别是c t l 公式或e a g l e 公式。虽然e a g l e 与c t l 相比具有口t 以表示 “规划意图”和“对子目标的失败处理机制”的特点；但是，在表示扩疑目标的 语义层次上，有关c t l 和e a g l e 之间比较的研究还不多。本文根据有关c t l 目 标公式和e a g l e 目标公式的严格的语义描述，证明了：对于许多e a g l e 目标公 式而苦，都存在着一个与之语义等价的c t l 目标公式( 在这些e a g l e 日标公式 当中，还包括了一些原来被认为不可以用c t l 目标公式表达的e a g l ee i 标公式) 。 另外，本文还分析指出了e a g l e 目标公式与c t l 目标公式相比在表达能力卜的 一些局限性。 在目前所有的关于求强规划解( 无论是在完全可观察性还足郜分可观察性的 条件下) 的研究中，观测变鼍的集合都被认为足固定的而且足强制性的。然而， 在许多现实的规划领域里，观测变釜的集合是变化的或者是，可选择的：另外， 某些观测信息对强解的执行也许是毫无用处的，但获得这哆观测信息却需要似 出一定的代价。为强解作观测信息约简( 即在不影响相应的动作执行过程的情 况下，尽量简化伴随其阍的信息观测工作) 是一个很有意义的研究内容，因为它 可以改善强解的质量并使其执行的代价减少。就我目前所知，这仍然是个待解决 的m 题。本文首次提出了卡 i 关门j 题，并给出了第一个对状态动作表形式的强 解作观测信息约简的算法s t r o n g f o p o 。输入某个状态动作表形式的强解 尢f ，算法s t r o n g f o p o 会首先计算一个近似最小的在兀f 执行期问可能有用的 摘要 观测变量集r 。，然后把丌f 转化为一个建立在峙上的条件规划7 t p 。另外，本 文还证明了该算法是可终止的和合理的。 关键词：扩展目标，强规划解，完全可观察性，部分可观察性 a b s t r a n t s e m a n t i cc o m p a r i s o no fe x t e n d e dg o a l sa n d o b s e r v a t i o nr e d u c t i o nf o rs t r o n gp l a n s m a j o r ： c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：w e ih u a n g s u p e r v i s o r ：y u n f e ij i a n g a b s t r a c t i nr e c e n t y e a r s , i n c r e a s i n g i n t c l e s th a sb e e nd e v o t e dt o p l a n n i n gu n d e r u n c e r t a i n t y a n dd i f f e r e n tr e s e a r c hl i n e sh a v eb e c ad e v e l o p e d p l a n n i n gw i t he x t e n d e d g o a l su n d e rf u l lo b s e r v a b i l i t y ，a n ds t r o n gp l a n n i n gu n d e rf u l lo b s e r v a b i l i t y ( o rp a r t i a l o b s e r v a b i l i t y ) a r et w oo f t h em o s ts i g n i f i c a n tp r o b l e m si nt h i sr e s e a r c hf i e l d i np l a n n i n gw i t he x t e n d e dg o a l su n d e rf u l lo b s e r v a b i l i t y t h ee x t e n d e dg o a l sa r e o f t e ne x p r e s s e di nt e m p o r a ll o g i c ，p a r t i c u l a r l yi nc t la n de a g l e n ow o r kh a sg i v e n af o r m a lc o m p a r i s o nb e t w e e ne a g i ea n dc t lo ns e m a n t i c s ，t h o u g hi ti ss a i dt h a tt h e c a p a b i l i t yo fr e p r e s e n t i n gt h e i n t e n t i o n a l a s p e c t so fg o a l sa n dt h ep o s s i b i l i t yo f d e a l i n gw i t hf a i l u r ea r et h em a i nn e wf e a t u r e so fe a g l ew r t c t l i nt h i sp a p e r , a c c o r d i n gt ot h ef o r m a ls e m a n t i c sf o re a g l ea n dc t l ，c t li sp r o v e dt ob ea b l et o e x p r e s sm a n ye a g l ef o r m u l a sw i t h o u ta n yc h a n g eo ns e m a n t i c s 。t h o u g h ti th a sb e e n b e l i e v e dt h a ts o m eo ft h ee a g l ef o r m u l a sa l eu n e x p r e s s i b l ei nc t l i ti sa l s of o u n d t h a ts o m eb a s i ca n di m p o r t a n tg o a l si nn o n - d e t e r m i n i s t i cd o m a i n se x c e e dt h e e x p r e s s i v ea b i l i t yo fe a g l e s t r o n gp l a n n i n gu n d e rf u uo rp a r t i a lo b s e r v a b i l i t yh a sb e e na d d r e s s e di nt h e 】i t e r a t u r e b u tt h i sr e s e a r c hl i n ei sc a r r i e do u tu n d e rt h eh y p o t h e s i st h a tt h es e to f o b s e r v a t i o nv a r i a b l e si sf i x e da n dc o m p u l s o r y i nm o s tl e a lw o r l dd o m a i n s h o w e v e r o b s e r v a t i o nv a r i a b l e sa r eo p t i o n a la n dm a n yo ft 1 1 e ma l eu s e l e s si nt h ee x e c u t i o no fa p l a n ；o nt h eo t h e rs i d e i n f o r m a t i o na c q u i s i t i o nm a yr e q u i r es o m ek i n do fc o s t s oi t i s s i g n i f i c a n tt of i n dam i n i m a ls e to fo b s e r v a t i o nv a r i a b l e sw h i c ha l en e c e s s a r yf o rt h e e x e c u t i o no fap l a n a n dt ob e s to fm yk n o w l e d g e i ti ss t i l la no p e np r o b l e m t h j s p a p e rp r e s e n t saf i r s ta t t e m p tt os o l v et h ep r o b l e m ，n a m e l y ，i td e f i n e sa na l g o r i t h m t h a tf i n d sa l l , a p p r o x i m a t em i n i m a ls e to fo b s e r v a t i o nv a r i a b l e sw h i c ha r en e c e s s a r y f o rt h ee x e c u t i o no fas t r o n gp l a nu n d e rf u o b s e r v a b i l i t yn e as t a t e - a c t i o nt a b l e ) ； a n dt r a n s f o i t n st h e p l a n i n t oas t r o n g p l a nu n d e rp a r t i a lo b s e r v a b i l i t y ( i e a c o n d i t i o n a lp l a nb r a n c h i n go f | t h eo b s e r v a t i o n sb u i l to nt h e s eo b s e r v a t i o nv a r i a b l e s ) k e yw o r d s ：e x t e n d e dg o a l ，s t r o n gp l a n ，f u l lo b s e r v a b i l i t y , p a r t i a lo b s e r v a b i l i t y l l l 第1 亭引占 第1 章引言 在日常生活中，人们作规划的过程其实就是一种动作推理的过程。在这个过 程中，人们需要首先颅期各种动作的效果，然后制定一个可以满足某个规划目标 的动作执行策略。智能规划就是人工智能坦专门研究如何利用计算理论和计算机 技术实现自动规划的领域。 不确定规划是智能规划里的一个分支。在其所研究的规划问题中，各个动作 的效粜也许是不确定的，控制器在执行规划时也许不能得到关于系统状态的全部 信息( 即规划领域町能是部分可观察的) ，并且规划的目标也可能不是可达性目 标( 即仅仅要求系统最终到达某个指定的状态) 而是扩展目标( 即要求系统的状 态演变符合某种时态性质) 。与要求动作效果必须是确定的、控制器在执行规划 时必须能得到关于系统状态的全部信息( 即规划领域必须足完全可观察的) 并且 仅仅面向可达性目标的经典规划相比，不确定规划所研究的问题更复杂并且更贴 近现实。从经典规划发展到不确定规划既是理论研究上的自然扩展和延伸，也是 自动规划技术应用于实际的必然要求与趋势。 不确定规划l 三经成为目前人工智能研究领域的一个热点。现在对它的研究主 要集中在两个方向上：( 1 ) 在动作效果不确定以及规划领域完全可观察的条件下 对扩展目标作规划，和( 2 ) 在动作效果不确定以及规划领域啬| f 分可观察( 或完全 可观察) 的条件下对可达性目标作规划。 本文的研究工作正是在上述两个方向上展开的： 1 在目前面向扩展目标的不确定规划研究中，c t l 7 6 公式和e a g l e 7 7 公式是 两种藿要的扩展r t 标表示形式。t 升是，在表示扩展目标的语义层次上，有关 二者之目比较的研究还不纠1 1 3 l 。本文根据有关c t l 目标公式和e a g l e 目标 公式的严格的语义描述，证明了：对于许多e a g l e 目标公式而言，都存在着 一个弓之语义等价的c t l h 标公式( 在这些e a g l e 目标公式当中，还包括了【1 】 和【7 7 】所列出的不能用c t l h 标公式表示的e a g l e 目标公式的全部例子) ；并 分析指出了e a g l e 目标公式与c t l 目标公式相比在表达能力上的一些局限 性。 2 在目前面向可达性目标的不确定规划研究中，求强解( 即呵以保证系统在有 第1 亭引言 限的步数内到达目标状态的规划) 一直是一个基本丽重要的l 口j 题。无沦在 规划领域完全可观察还是部分可观察的条件下，目前相关的研究部假设控 制器在执行规划时所获得的观测信息是固定的而且是强制性的。然面，在 许多现实的规划领域里，观测信息是可变可选并附有代价要求的。为了改 善强解的质量并减少其执行的代价，本文提出了第一个对状态动作表形 式的强解作观测信息约简( 即在不影响相应的动作执行过程的情况下，尽量 简化伴随其问的信息观测工作) 的算法s t r o n g - f o p o 1 0 4 。该算法是可终 止的和合理的。实际上，其观测信息约简的工作包含两个层次：一是尽量地 减少在控制器执行强解的全过程中都没有用处的观测信息，二是尽鼍地减少 在控制器执行强解的各个具体的步骤中无意义的观测信息。 本文后面的内容组织如下：第2 章从发展历史、不确定性的多个维度以及规 划方法等方面对不确定规划的研究作了综合论述；第3 章给出了在不确定规划中 关于规划领域、规划、规划1 u j 题和规划解等摹本概念的严格定义，并介绍了控制 器执行规划的抽象过程以及一些基本的规划算法思想：第4 章则在执行结构这一 语义框架下严格比较了c t l 目标和e a g l e 目标的语义，并在其中证明了许多 e a g l e 目标( 包括一些原来被认为不能用c t l 表达的目标) 其实是可以被语义等 价地表示成c t l 目标的；第5 章给出了第一个对状态动作表形式的强解作观 测信息约简的算法，并证明了该算法是可终止的和合理的：最后的第6 章则是全 文的总结和对未来研究工作的展望。 第2 章不确；七枷划综述 第2 章不确定规划综述 直观地讲，规划就是指人们在日常生活和工作中为了完成某个任务或实现某 个目标而预先制定一套行动疔案。其实，规划过程是一种涉及动作推理的理性思 维过程：在作规划前，规螂者需要首先了解各种可选动作的期迥效果，然后根据 当时所涉及的领域的情况选择和组织一套动作执i 亍方案使得控制器( 即规划 执行者) 在执行该方案后可以令预先给定的h 标得以实现。 智能规划就是人工智能里专门研究如何利用计算理论和计算机技术实现自 动规划的领域。由于规划是人类理性行为的重要组成部分( 特别是推理的一个重 要方面) ，所以在智能规划领域的研究对f 人工智能甚至整个计算机科学都有很 重要的理论意义【1 1 。另外，随着现代社会的不断发展，人类在生活和工作中要完 成越来越复杂的任务和实现越来越复杂的目标，而各种任务和目标所涉及的领域 也显得越来越庞杂和多变，靠于工作规划已愈来愈耗费时间和精力。这就使有关 智能规划的研究越来越具有现实意义和应用前景。如今，智能规划已成为人工智 能里一个重要的研究领域【2 】，而其中面向复杂目标和不确定性领域的研究分支即 不确定规划更成为当前人工智能研究的一个热点。 本章后面的内容安排如f 。2 1 节从智能规划研究的发展历史( 从经典规划 到不确定规划) 这一角度阐述了不确定规划的研究背景；2 2 符介绍了在目前的 不确定规划研究中所谓不确定性的三个维度( 即动作效果的不确定性、对系统状 态观测的不完全性和规划目标的复杂程度) ；2 3 节则简要地介绍了目前几种最 主要的不确定规划方法。 2 1 研究背景 智能规划这一研究领域最早出现于上世纪五十年代，发展至今已有半个多世 纪的历史了。其最初所研究的规划| u j 题是经典规划问题。经典规划问题的形式为： 如何在动作集合月中选择和组织一个动作序# l j ，使得控制器在执行完 该动作序列后町以令相应的系统从某个初始状态s 0 演变到指定的目标状态s g 。 第2 章不确定规划综述 这类规划l 口j 题都含有以下三个重要的假设： 1 确定的动作效果：所有动作的执行结果郜是唯一的确定的。即若动作 a 在状态sf 可执行，那么在s 下执行a 所得到的结果状态s 足确定的。 2 完全可观察性：控制器总是能获得足以唯一确定系统j 与前状态的信息， 即控制器所获得的观测信息总是只对应f 一个状态。 3 可达性目标：只是要求系统在控制器执行完某一动作序列后能到达某一 目标状态。 以下就举一个非常简单的在码头工人领域( 简称d w r 领域) 里的经典规划问题 的例子。 例2 1 假设在一个d w r 领域里有一个拖车r ，两个码头区域a r e a l 和 a r e a 2 ，以及四个集装箱a 、8 、c 和d 。在a r e a l 里有一个吊臀c r a n e l 和一个 集装箱i f 台p 1 ，而在a r e a 2 里有一个吊臂c r a n e 2 以及两个集装箱甲台p 2 和p 3 。 其中r 可以在a r e a l 和a r e a 2 之间移动，它既可以是空的也可以装载一个集装 箱。各个集装箱甲台的面积只能放一个集装箱，所以其上的所有集装箱都被放成 一堆。各个吊臂可以从拖车上或任一集装箱甲台的顶部抓取一个集装箱，这里要 求相关的吊臂和拖车或集装箱甲台必需在同一个码头区域内；各个吊臂也呵以将 其所抓的集装箱放到拖车上或任一集装箱甲台的项部，这里也同样要求相关的吊 臂和拖车或集装箱甲台必需在同个码头区域内。在任何时候，任一集装箱都只 能位于拖车卜，或处在某一集装箱甲台卜，或被某一吊臂抓着。 在这个d w r 领域里，r 的移动以及各个吊臂的抓起操作和放下操作的效果 都是确定的，即不存在任何操作失败或异常的情况：规划的执行者( 人或机器人) 可以始终观察到r 以及各个集装箱的具体位置，即可以始终观察到该领域具体 处在什么状态下( 体现了完全可观察性) 。假设我们只希望该领域能从某一初始 状态( 例如图2 1 所显示的状态) 出发，通过执行某一序列的操作( 即规划解) 能到达某个目标状态集合( 例如所有的满足集装箱a 位于甲台p 1 且集装箱c 位 于甲台p 3 的状态集合) 中的一个状态( 即只考虑简单的可达性目标) 。 4 第2 章不确定规划综述 图2 1 一个简单的d w r 规划领域 如今，关于经典规划问题的研究已经取得了许多重要的理论成果。例如，在 问题描述方面，有基于情景演算的方法【3 卅( 其代表性的规划系统为q a 3 1 4 】) 和s t r i p s 方法【5 1 ( 其代表性的规划系统为s t r i p s 5 】) 。特别是s t r i p s 方法， 由于它使用了( 前提条件，增加表，删除表 的形式来表示动作，所以用它来作 动作推理时我们可以只考虑状态中被改变的部分而不考虑其未改变的部分 这就很好地解决了框架问题【3 】。在规划方法方面，有基于分层思想的规划方法 【6 - 8 1 ( 其代表性的规划系统有s i p e - 2 1 1 4 1 、u m c p 1 5 1 、s h o p 2 1 6 1 和 o p t a n 2 0 2 1j ，等等) 。图规划方法f 9 1 0 1 ( 其代表性的规划系统有 g r a p h p l a n 9 - 1 0 、i p p 2 2 、s t a n 1 7 和l p g 1 8 ，等等) ，基于s a t 技术的规 划方法【1 1 1 3 】( 其代表性的规划系统有b l a c k b o x 1 9 等) ，基于启发式搜索的规 划方法 2 3 2 5 ( 其代表性的规划系统有h s p 2 6 、f f 2 7 - 2 8 和m i p s 2 9 3 0 ， 等等) 和基于p e t r i 网展开的规划方法 3 1 1 ，等等。 其实，经典规划问题是一类非常难解决的问题，人们在理论上已经证明了这 类问题是n p 完全的或者更难的问题 3 2 3 3 。这就使得早期的经典规划器只能够解 决类似于一些像积木块世界这样的小问题领域，对于实际应用中的一些大规模的 第2 章不确定规划综述 复杂的规划问题则显得无能为力。随着相关理论研究的深入和编程技术的发展， 目前的规划器所能处理的规划问题的规模和复杂程度都大大增加了，些经典规 划的技术更加被成功地应用鲥了现实生活里的多个领域。例如，在航天航空领域 里的应用有人空穿梭机的整修1 3 4 1 、太空穿梭机上的有效负载操作【3 5 1 和航空器 的控傣i 3 6 3 7 等等：在科学数据分析中的应用有埘气象数据和生物数据的实时处 理【3 8 、地图修订【3 9 l 和图像分析m o 等等；在机器人领域里的应用有机器人控制 【4 1 0 2 l 和机器人感h 4 3 - 4 4 等。自动规划技术在其它领域里的应用可参考欧洲 智能 规划网p l a n e t ( 见h t t p ：w w w p l a n e t - n o e o r g 和 h l p ：s c o m h u d a c u k p l a n e t r e p o s i t o r y 。当然，实际的应用显然不止这些) 。 在经典规划口j 题里，规划领域必须是确定的和完全可观察的。但在很多情况 下这两个要求显得过于苛刻和理想化，并不符合现实。另外，经典规划问题只考 虑了简单的可达性规划目标，而可达性目标并不能表达实际生活中更为普遍存在 的更复杂的规划目标( 如带有不同意愿强度、概率和时态要求的目标) 。考虑到 现实的系统可能是不确定的和部分可观察的，以及为了处理比一般的可达性目标 更普遍且更复杂的扩展目标，因此人们开始了对不确定规划问题的研究。从经典 规划发展到不确定规划既是理论研究上的自然扩展和延伸，也是自动规划技术应 用于实际的必然要求与趋势。 对于不确定规划问题的研究起步较晚，最早的相关研究大概出现于上世纪九 十年代，即是将原来处珲经典规划问题的基于规划空间的规划方法【4 5 4 7 】作一些 扩展4 8 4 9 。这类方法后来被称为条件规划方法，由于条件规划方法采用了一种 被称为条件动作的扩展的s t r i p s 算子( 即一个动作可以含有多个不同的相互排 斥的效果) ，所以它可以处理一定形式的不确定规划i j 题。条件规划方法的主要 缺点在于其效率非常低，无法应用于实际( 甚至也无法用于求解一些非常简单的 规划i 口j 题 。但在从上世纪九十年代至今的十几年问，已经出现了不少的新的更 有希望的不确定规划方法，如基于模世检测的规划方i l 5 0 - 5 2 l ( 其代表性的规划 系统有m b p 5 3 、s i m p l a n 5 4 、y k a 5 5 、j u s s i p o p 5 6 和u m o p 5 7 - 5 8 等等) ，基于m a r k o v 决策过程的规划方法( 简称为m d p 规划方法) 【5 9 - 6 1 l ( 其 代表性的规划系统有s p u d d 6 2 和g p t 6 3 等等) ，扩展的基于s a t 技术的规 划方法 6 4 - 6 5 1 ( 其代表性的规划系统有q b f p l a n 6 6 ) ，扩展的图规划方法 6 7 - 6 8 6 第2 亭不确定规划综述 ( 其代表性的规划系统有s g p 6 8 1 ) ，基于知识的规划方法【6 争7 0 】( 其代表性 的规划系统有p k s 7 0 ) 和基于启发式搜索的规划方法 7 1 7 2 ，等等。 由于不确定规划问题在原本七三经柑当复杂的经典规划b d 题上又添加了新的 难度，所以它是一类相当难的问题 7 3 7 5 。无论是研究其表示方法还是规划求解 算法鄙柏当富有挑战性。近年来，多种迹象表明不确定规划已渐渐成为人工智能 研究领域蛉个热点，例如：多本围际权威期刊( 如j o u r n a lo f a r t i f i c i a li n t e l l i g e n c e r e s e a r c h 和a r t i f i c i a li n t e l l i g e n c e 等) 近几年发表了多篇有关不确定规划的文章； 多个国际权威会议( 如i n t e r n a t i o n a lj o i n tc o n f e r e n c eo na r t i f i c i a li n t e l l i g e n c e 即 i j c a i 和n a t i o n a lc o n f e r e n c eo na r t i f i c i a li n t e l l i g e n c e 即a a a i 等) 在最近的几届 都设有专门的不确定规划s e s s i o n ：而由i c a p s ( i n t e r n a t i o n a lc o n f e r e n c eo n a u t o m a t e dp l a n n i n ga n ds c h e d u l i n g ，它是目前智能规划方面最好的会议) 所主办 的最近两次国际规划大赛即i n t e r n a t i o n a lp l a n n i n gc o m p e t j t i o n ( i p c ) 则增设了在不 确定领域作规划的比赛部分。 目前，对不确定规划问题的研究还主要停留在理论阶段，相关的应用并不多。 但由于不确定规划是处理许多现实中重要问题的基础( 这些问题包括机器人感知 与控制、生产或运输方面的规划2 j 调度、网络路由和金融商业方面的决策支持等 等) ，所以我们有理由相信：随着其理论研究的发展和相关软件技术的成熟，有 关不确定规划的应用将越来越多。 2 2 不确定性的三个维度 简单地讲，将前面所捉到的经典规划问题里的三个限制假设作一定地放宽， 经典规划i u j 题就演变成不确定规划口j 题。对应着确定的动作效果、完全可观察性 和町达性目标这三个限制，相应的放宽构成了不确定规划里不确定性的三个维度 ( 见图2 2 ) ：不确定的动作效果、部分可观察性和扩展目标。其中，对于不确 定的动作效果而言，各种可能的效果既可以带有概率也可以不带概率；而对于部 分可观察性而言，完全不可观察性( 即完全可观察性的对立面) 是其一个极端的 特例。在规划领域完全不可观察条件下的规划问题被称为一致性规划l 口j 题。 现在对不确定规划问题的研究主要集中在( 1 ) 在动作效果不确定及完全町观 第2 章不确定规划综述 察性的条件下对可达性目标和扩展目标作规划，以及( 2 ) 在动作效果不确定及部 分可观察性( 包括完全不可观察性) 的条件下对可达性目标作规划。 克会小；t j + 观察 规划目拇 扩眨l i 标 澍2 24 、确j o r l i f l 勺二个络? 芟 2 2 1 不确定的动作效果 ： ：姻效鬈 效果 确定的动作效果其实是对客观世界演化的种简化描述，它假设客观世界是 沿着某个固定的轨道发展的。这种单一演化路径形式的系统模型有时的确行之有 效，例如在只考虑系统一般的或正常的动作效果的时候。然而，为此我们往往需 要建立一个可以完全确定系统何时会发生何种情况的完美模型。有时这并不符合 实际，因为我们知道并不是所有事情都是可以预测的：有时一些不可知的因素会 导致不同的动作效果( 如操作异常或失败) ，而有时并不存在一般的或正常的动 作效果( 例如在掷骰子或抛硬币的时候) 。 丰甘比之下，不确定的动作效果往往更贴近于现实。所以，我们在为系统建模 8 第2 亭不确定规划综述 时就应该考虑各种。f 能的情况以便之后对其作推理。 例2 2 图2 3 显示了一个简单的机器人导航领域，其中的直线代表墙壁、 带阴影的椭嘲代表旋转门。在该领域琨，机器人r 总是处在一个4 x 4 的区域里 的某个位置上，各个位置由( x 唑标值，y 坐标值) 表示。除非在柏应方向七有 墙壁遮挡甭则r 可以往东、南、西和北四个方向移动。若位置a 和b 相邻且 二者问没有墙壁或旋转门，r 处于a 且b 位于a 的东( 南、两或北) 面，那么 r 往东( 南、西或北) 方向移动一次就可以到达位置b 。t 只是，当r 处于( o ，1 ) 并往东移动时，r 可能因旋转i j 的影响而不确定地来到( 1 ，o ) 、( 1 1 ) 或( 1 ，2 ) 。同 样地，当r 处于( 1 ，1 ) 并往西移动时，其会不确定地到达位置( 0 ，1 ) 或( 0 ，2 ) ：当r 处于( 2 ，2 并往东移动时，其会因门是否关闭f i i 不确定地到达( 3 ，2 ) 或留在( 2 ，2 ) ； 当r 处于( 3 ，2 并往西移动时，其会不确定地到达( 2 2 ) 或( 2 ，1 ) 。所以该领域星 的四种动作具有不确定的效果。 羟2 3个旋单的禽4 i 确定爹l ： j i 嚣久皆魏镢域 对动作效果不确定的领域作规划，其主要难点在于规划的执行可能对应于多 条不同的执行路径。这就要求相应的规划算法能高效地分析所有动作各种可能的 执行结果，邸奠产生的规划应该具有条件判断的能力。 另外，不确定的动作效果还可以体现为各种可能的结果状态的概率分布。即 用概率值的大小来反映铀关的结果状态出现的可能性的大小( 一般是正常结果的 概率会较大) 。例如，在例2 2 所描述的领域里，若r 处在( o ，1 ) 并向东移动一步， 那么它来至l j ( 1 ，o ) 、( 1 ，1 ) 和( 1 ，2 ) 的概率可以分别是o 2 5 、0 5 和o 2 5 。 9 第2 章不确定规划综述 2 2 2 部分可观察性 其实在许多实际的情况下，规划的执行者只能够观察到领域状态的部分信 息，即对其而言许多领域状态是不可分辨的。确切地讲，在许多应用场合里，规 划的执行者在执行规划时不能得到某些领域状态的信息，而一些信息只有在某些 领域状态下或控制器通过执行某些“感知”操作后才可以得到。 例2 3 假设在例2 2 所描述的机器人导航领域里，机器人r 只能通过自身 所带的传感器检测其所在位置的口q 周有无墙蹙。图2 4 显示了各个位置所对应的 观测信息，其中的各个三角符号分别表示相应的方向上有墙。根据这些脱测信息， 所有的位置被划分成了若干个等价类：( ( 0 ，o ) ，( 1 ，3 ) ， 0 ，l 】来模拟。 其中，e 。( o l s ) 表示系统在执行动作a 并到达状态s 的情况下控制器观察剑。 的概率( a 月，s s ，o , e o ) 。对于任意a e f l 以及s e s 都有。o 尸a ( o i s ) ：l 。在 部分可观察性的条件下，规划解的形式是7 【：回寸月。在这里，c b 是关丁二s 的 概率分布的集合。因此即使5 是有限的，c b 也是无限且连续的。 一 在规划领域完全可观察的条件f ，m d p 规划方法有两种基本的规划求解算 法：镱略迭代和值迭代。仍它们都只能用于解决规模非常小的问题，状态空间的 爆炸令它们没有什么实用价值( 有关它们的复杂性讨论可看 8 9 ，9 1 1 ) 。为了缓解 状态空间爆炸所带来的问题，b b o n e t 和h g e f f n e r 提出了实时值迭代算法【9 2 】。 该算法并不能保证找到最优解，甚至不能保证其执行一定可以终止，但实验证明 它可以解决规模大得多的规划m 题。【6 1 ，9 3 9 4 等文章讨论了如何在m d p 的框 架下表示时态逻辑公式形式的扩展目标。 在规划领域部分可观察的条件下，m d p 规划方法和规划问题分男l j 被称为 p o m d p 规划方法和规划问题。在p o m d p 规划j n j 题中，控制器可以观测到的是 系统的信任状态( 即系统状态集上的概率分布) 而不是系统状态本身。从理论上 讲，同样可以采用策略迭代或值迭代算法求解p o m d p 规划问题。但由于系统 状态集j 本身的规模就可能很大，加之在它上面的概率分布就更是无穷且连续 第2 章不确定规划综述 的，所以这两种肇本算法也没有什么实用价值。现在已有多种不同的求解 p o m d p 规划问题的方法 6 0 9 5 , 9 6 和相关的缓解状态空间爆炸的方法 【9 7 1 0 0 】。 2 3 3 扩展的基于s a t 技术的规划方法 基于s a t 技术的规划方法原本是一种求解经典规划问题的有效于段 【1 1 1 2 。经过扩展( 如f 6 4 ，6 5 ，1 0 1 ，1 0 2 】) ，这种方法也可用于求解动作效果不 确定的一致惟规划问题( 即在规划领域完全不可观察的条件下对可达性日标作规 划的l u j 题) 。其基本思想有： 首先限定规划问题要在n 步动作内解决。 对于所有诞i s n 一1 ，甩命题公式描述在第i 步情况下的： 1 动作集合( 包括表示各动作在第i 步执行时的前提条件、执行后的必然 效果和偶然效果( 即不确定效果) 的命题公式) ； 2 各个状态命题变元的值改变的原因( 即其改变可能源自第i 步动作的必 然效果或偶然效果) ，这类公式被称为解释性框架公理； 3 不同动作间的互斥( 即在同一步内只能有一个动作被执行) ，这类公式被 称为完全互斥公理； 4 规划领域，就是卜3 步所产生的所有公式的合取电( ) 。 用公式中( ) = 蓦嘲( ) 来表示n 步以内的规划领域。设钏始状态集s o 和目 标状态集s g 被分别表示成命题公式巾( s o ) 和m ( s g ) 。相关的限定步长为n 的 一致性规划问题u p ( p , n ) 被表示成命题公式中( p ) = m ( ) 中( s o ) m ( s g ) 。然 后将叫p ) 作为s a t 问题求解。 设模璎“是任意一个关于公式叫p ) 的s a ti j 题的解。从p f f , 翻译得到的规划 解只能保证系统从s o 里的某个( 而不是任意) 状态出发最终可能会到达s 。里的 某个状态。所以，这类规划解在强度上比在摹于模型检测的规划方法中定义的弱 解还要弱，它们被称为弱一致性解。 为了求得强解( 其含义与在基于模型枪测的规划方法中定义的强解相同) ， 需将原规划领域做一些修改：对每一状态s 增加新状态s ( 新的状态命题变元 第2 亭不确定规划综述 f a i l 在s 上成立而在s 上不成立，除此之外s 与s 完全年目同) ，让所有动作在所 有状态下都是町执行的( 原来不可执行的动作将导致f a i l 成立的状态) 。记这样 得到的规划领域为。从模型翻译得到的规划解也可表示成命题公式，设其为 v ( “) 。若v ( ”) 是强解，则( 、i ，( p ) 似s o ) 中( ) ) 一( m ( s g ) 一f a i l n ) ( 该公式就 是日j 题( p n ) 的强编码形式) 是可满足的。所以，基于s a t 技术的求强解的算法 一般是：( 1 ) 先用s a t 技术找出满足中( p ) 的一个模型及其相应的弱一致性解 v ( 肛) ：( 2 ) 然后用v ( ) 求得相应的规划问题( p n ) 的强编码形式；( 3 ) 再利用s a t 技 术判断( p n ) 的强编码形式是否可满足，若可满足则将v ( ) 作为强解返回，甭则就 r 冉找和试下一个弱一致性解( 即回到第( 1 ) 步) 。 2 3 4 扩展的图规划方法 图规划方法也原本是一种求解经典规划i 日j 题的有效于段【9 - 1 0 。经过扩展( 如 【6 7 1 ) ，这种方法可用于求解动作效果不确定的一致性规划问题。其基本思想有： 对初始状态集s 0 里的每一个状态及其每一个可能执行的动作产生一规划图。 在求弱一致性解时，只需每次在一个规划图上按照与求解经典规划刚题时相 同的方法求解。只要在其中一个规划图上找到解，该解就是弱一致性解。 在求强解时，不仅要在一个规划图里还要在不同的规划图之间检查互斥关 系。相应的解抽取过程是一个反向搜索过程：在所有规划图里的每一层枪查 各动作的执行效果。 另外，扩展的图规划方法还可以求解一些在规划领域部分可观察的条件下带 有某些约束的规划问题【6 8 】。 2 3 5 以上各种不确定规划方法之间的比较 壮| 对于基于模型检测的规划方法和m d p 规划方法，扩展的基于s a t 技术的 规划方法和扩展的图规划方法在求解不确定规划问题方面有很大的局限性：它们 只能用于求解一致性规划l u j 题( 扩展的图规划方法还可以解决一些带匀某些约束 6 第2 审不确；规划综述 的规划领域部分可观察的规划问题) ，而这哆问题只是不确定规划问题警很小的 一部分。 目前，既可以处理扩展瞄标又可以处理部分可观察惟的不确定规划方法有 m d p 规划方法和展于模璎检测的规划方法。对于它们的研究一直以来郡很活跃。 现在，随着研究的深入，它们所能解决的i 口j 题的规模和复杂程度正不断扩大和提 高。它们之间比较可以主要概括为以f 几点： m d p 规划方法利用概率来表示动作效果的不确定，并使用动作一状态一观 测值上的概率赋值来表示规划领域的部分可观察性；而展于模型检测的方法 则使用结果状态集合来表示动作效果的不确定，并用状态一观测变量上的布 尔赋值来表示规划领域的部分可观察性。所以，在表示规划领域的方面，m d p 规划方法比基于模型检测的规划方法能衷达更卞富的领域信息。 它们都与传统的规划疗法在看待规划问题的方式上很不一样。m d p 规划方 法用效能函数来表示规划目标，并将柏应的规划| j 题转化为最优化问题来解 决：而基于模犁榆测的规划方法则采删时态逻辑公式来表示规划e j 标，并利 用模型检测的技术来进行规划求解。目前本人还没有找到自j 关比较这两种目 标表示方法的表达能力的文献。 m d p 规划方法可以采用概；筝来表示在动作选择过程中各状态和各动作| 日】的 优先关系，这种方法简单而自然；但是基于模氆检测的规划方法( 特别是在 用c t l 公式来表示规划日标的情况下) 则缺少这种优先关系的表示机制，有 关的研究也不多。虽然使用概率可以得到一定的问题表达能力，但这蝗概率 值可能都是来自于统计估算，所以它们町能有偏差甚至不能坡获得这样 将对规划求解带来严晕影响。 m d p 规划方法可以采j j 效能函数( 即代价函数与奖惩值) 来刻画f i 同选择 标准之问的竞争( 动作代价最小弓状态奖惩值最大之间的竞争) ，而属于模 型检测的规射方法则没有表示标准竞争的机制。然而在另一方面，设定代价 函数与奖惩值很需要技巧( 例如，将某状态的奖惩值从一l o o 改为- 9 9 就可能 使规划算法找到解完全不同) ；而且在某些情形下，这些设定并不自然。对 于那些已经表示成逻辑公式的规划 标，效能函数不好表达( 有时甚至不能 表达) 。 7 第2 蒂不确定规划综述 在规划领域完全可观察的条件下， 规划解是7 【：j 寸月形式的全函数， 对于可达性目标，m d p 规划方法找到的 而基于模型检测的规划方法找到的规划解 则是兀：s 斗a 形式的部分函数。后者的表达能力要强于前者，因为后者的执 行路径可以是有限的l f i j 前者的执行路径则必须是无限的。 在规划领域完全可观察的条件下，对于扩展目标，m d p 规划方法找到的规 划解也是冗：j 一月形式的全函数，而堆于模型检测的规划方法找到的规划解 则是既考虑到当前的领域状态又考虑到当前的执行上下文的部分函数。后者 的表达能力也要强于前者。 在规划领域部分可观察的条件下，对于可达性目标，m d p 规划方法找到的 规划解是7 【：圆- 9 月形式的函数( b 是j 上的概率分布的集合) ，而基于模型检 测的规划方法找到的规划解则足以观测变量为分支点的条件规划。目前本人 还没有找到有关比较这两者表达能力的文献。 目前，基于模型检测的规划厅法由于可以利用符号模型检测技术来以状态集 合和状态转换集合为单位进行规划解的搜索，所以其求解效率有了很大的提 高。m d p 规划方法则耍逊色一蝗。但是，要注意到它们所侧霞解决的规划 i 口j 题是不同的。 总而言之，基于模型检测的规划方法是一种拥有巨大潜力的不确定规划方 法：它具有牢固的理论撼础，能够处理多种不确定规划问题；它拥有很好的技术 优化手段，其应用前景很广阔。在为现实的系统建模时，若动作效果的不确定性 无法避免( 例如为网络服务作规划) 或者动作效果的不确定性对规划问题本身很 重要( 例如在一些要求绝对满足安全原则的应用里) ，那么，使用基于模型检测 的规划方法将是一个不错的选择。 第3 荜规划领域、规划和规划6 d 题 第3 章规划领域、规划和规划问题 本章的目的是给出在不确定规划问题哩有关规划领域、规划和规划问题等一 系列定义，并介绍柑关的基本