第3期 谷文祥，等：基于条件效果的对象动态可变图规划 ·15 the set of object added 动作的前提或“有效结果”（在规划图中动作的结果 the set of object deleted) 被用来支持命题)；②沱们的有效结果集合完全相 the effect propositions) 同；③一个动作支持的命题与另一个动作支持的命 题两两互斥 2)两个命题逆向互斥，如果一个命题支持的所 Common component 有动作与另一个命题支持的所有动作两两互斥 Component number 由于文中采用目标驱动图扩展方法，规划图由 :the set of parameter{ 目标开始逆向产生，因此也要进行逆向推理和传播 :the set of precondition 互斥.但是与文献[11]不同，文中将处理3种互斥关 :the set of effect the effect proposition! 系：动作元件互斥，对象互斥，命题互斥 1)动作元件逆向互斥 2.3 CECDOP中对象的表达方式 2个动作元件Cm与Cn互斥： 在CDUOP中，一些动作能够创建新的对象或 ①静态互斥：2个元件Cm与Cn是无关元件， 删除已经存在的对象，对象在规划图中可动态地变 且元件Cm/Cn的结果删除另一个元件Cn/Cm的 化，在图规划中命题也有这样的性质，因此文中将延 前提或“有效结果”（在规划图中元件的结果被用来 用对象命题化8]思想，即用命题表示对象在某些规 支持命题)或②它们有效结果集合完全相同，或③ 划层的存在形式，采用alive+“对象名”表示方式. Cm与Cn支持的命题两两互斥，或④引致互斥：如 命题被分成了普通命题和对象命题， 果Cn引致Ck,Ck与Cm互斥，则Cn与Cm也互 斥 3 CECDOP规划 2)与对象命题有关的逆向互斥 3.1 CECDOP问题的组成 因为对象命题不支持元件，所以它们的互斥关 元件集包括普通元件和创建/删除对象元件 系不能通过后向传播得到，因此可以退前一步，当产 对象集 生1层动作元件时再判定1层的对象命题的互斥关 初始条件集由命题组成 系（目标出现的层是第1命题层，从目标往前扩展 目标集由命题组成，经过一系列操作，在规划 接着是第1元件层，以此类推)，1层与对象命题A 结束时这些命题为真 和B有关的逆向互斥，如果： 3.2 CECDOP规划图 ①层创建对象命题A的元件与创建对象命题 文中研究的CECDOP的规划图与图规划的规 B的元件通过逆向传播标记为互斥，则i层对象命 划图不同，它是由2种边和2种结点组成.CECDOP 题A与B互斥 的规划图的边由前提条件边、添加效果边组成，因为 ②如果i层中二对象命题A与B标记为互斥 是基于目标驱动构建规划图，所以图中没有删除效 且名字分别出现在i层的普通命题P和Q中，则普 果边.命题结点是由普通命题结点和对象命题结点 通命题P与Q互斥 组成，元件结点是由普通元件结点和创建/删除对象 3)普通命题逆向互斥 的元件结点组成.边把命题结点和元件结点相连，表 如果ⅰ层命题P支持的所有动作元件与命题Q 示了它们之间的关系.添加效果边把元件在前一层 支持的所有动作元件两两互斥，则普通命题P与Q 命题列的效果和元件相连，前提条件边把元件和下 互斥.互斥关系如图1所示 一层的命题列的前提相连 3.4图扩展算法 3.3逆向传播互斥 CECDOP算法包括扩展规划图和搜索有效规 以目标驱动方法扩展规划图时，规划图逆向产 划，这两部分交替进行.文中的规划图是从目标开始 生，这就要求逆向推理和传播互斥关系.在文献[11] 的，逐步向前扩展.这种扩展方法可以去除许多与目 中给出了逆向传播互斥关系的定义 标无关的命题与动作，规划图比较简单 1)2个动作逆向互斥，如果2个动作 3.4.1图扩展 ①静态互斥：如果一个动作的结果删除另一个 文中是以目标为导向进行规划图扩展的，算法 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net{the set of object added} {the set of object deleted} {the effect propositions} } } Common component : Component + number{ :t he set of parameter{ …} :t he set of precondition{ …} :t he set of effect{t he effect proposition} } 213 CECDOP 中对象的表达方式 在 CDUOP 中 ,一些动作能够创建新的对象或 删除已经存在的对象 ,对象在规划图中可动态地变 化 ,在图规划中命题也有这样的性质 ,因此文中将延 用对象命题化[8 ] 思想 ,即用命题表示对象在某些规 划层的存在形式 ,采用 alive +“对象名”表示方式. 命题被分成了普通命题和对象命题. 3 CECDOP 规划 311 CECDOP 问题的组成 元件集 包括普通元件和创建/ 删除对象元件 对象集 初始条件集 由命题组成 目标集 由命题组成 ,经过一系列操作 ,在规划 结束时这些命题为真 312 CECDOP 规划图 文中研究的 CECDOP 的规划图与图规划的规 划图不同 ,它是由 2 种边和 2 种结点组成. CECDOP 的规划图的边由前提条件边、添加效果边组成 ,因为 是基于目标驱动构建规划图 ,所以图中没有删除效 果边. 命题结点是由普通命题结点和对象命题结点 组成 ,元件结点是由普通元件结点和创建/ 删除对象 的元件结点组成. 边把命题结点和元件结点相连 ,表 示了它们之间的关系. 添加效果边把元件在前一层 命题列的效果和元件相连 ,前提条件边把元件和下 一层的命题列的前提相连. 313 逆向传播互斥 以目标驱动方法扩展规划图时 ,规划图逆向产 生 ,这就要求逆向推理和传播互斥关系. 在文献[11 ] 中给出了逆向传播互斥关系的定义. 1) 2 个动作逆向互斥 ,如果 2 个动作 : ①静态互斥 :如果一个动作的结果删除另一个 动作的前提或“有效结果”(在规划图中动作的结果 被用来支持命题) ; ②它们的有效结果集合完全相 同 ; ③一个动作支持的命题与另一个动作支持的命 题两两互斥. 2) 两个命题逆向互斥 ,如果一个命题支持的所 有动作与另一个命题支持的所有动作两两互斥. 由于文中采用目标驱动图扩展方法 ,规划图由 目标开始逆向产生 ,因此也要进行逆向推理和传播 互斥. 但是与文献[11 ]不同 ,文中将处理 3 种互斥关 系 :动作元件互斥 ,对象互斥 ,命题互斥. 1) 动作元件逆向互斥 2 个动作元件 Cm 与 Cn 互斥 : ①静态互斥 :2 个元件 Cm 与 Cn 是无关元件 , 且元件 Cm/ Cn 的结果删除另一个元件 Cn/ Cm 的 前提或“有效结果”(在规划图中元件的结果被用来 支持命题) 或 ②它们有效结果集合完全相同 ,或 ③ Cm 与 Cn 支持的命题两两互斥 ,或 ④引致互斥 :如 果 Cn 引致 Ck ,Ck 与 Cm 互斥 ,则 Cn 与 Cm 也互 斥. 2) 与对象命题有关的逆向互斥 因为对象命题不支持元件 ,所以它们的互斥关 系不能通过后向传播得到 ,因此可以退前一步 ,当产 生 i 层动作元件时再判定 i 层的对象命题的互斥关 系(目标出现的层是第 1 命题层 ,从目标往前扩展 , 接着是第 1 元件层 ,以此类推) , i 层与对象命题 A 和 B 有关的逆向互斥 ,如果 : ①i 层创建对象命题 A 的元件与创建对象命题 B 的元件通过逆向传播标记为互斥 ,则 i 层对象命 题 A 与 B 互斥 ②如果 i 层中二对象命题 A 与 B 标记为互斥 , 且名字分别出现在 i 层的普通命题 P 和 Q 中 ,则普 通命题 P 与 Q 互斥. 3) 普通命题逆向互斥 如果 i 层命题 P 支持的所有动作元件与命题 Q 支持的所有动作元件两两互斥 ,则普通命题 P 与 Q 互斥. 互斥关系如图 1 所示. 314 图扩展算法 CECDOP 算法包括扩展规划图和搜索有效规 划 ,这两部分交替进行. 文中的规划图是从目标开始 的 ,逐步向前扩展. 这种扩展方法可以去除许多与目 标无关的命题与动作 ,规划图比较简单. 31411 图扩展 文中是以目标为导向进行规划图扩展的 ,算法 第 3 期 谷文祥 ,等 :基于条件效果的对象动态可变图规划 ·15 ·