16· 智能系统学报 第2卷 可用前提集中)的元件Cs,如果它不与SC.!中己选 Pro.I com.I Pro.2 com.2 Pro.3 元件互斥，且不在SC.1中，则把Cs加入SC.1,并 alive 把Cs的效果加入i-1层可用前提集SP.1中 actl aliveB act.I aliveC act:1. act2 alive D 3)对于SC.1中的每一个元件Cs和Ct,考察 -In4 B alive Cs的引致元件Cm和Ct的引致元件Cn,如果Cm 与Cn互斥，则要选Cm和Cn之一进行抵制 component Proposition component Proposition 4)如果i=1,则SC.1,SC2,…,SC构成规 划解，否则i-1重复上面的步骤。 图1逆向传播互斥 3.5例子 Fig 1 Mutex inference backward 在A地有2个卡车车身(body),一组单排轮轮 胎(single tire,ST),一组双排轮轮胎(double tires, 描述如下 DT),一批木材(wood)和一批钢材(steel)还有一批 1)所有目标命题构成第1层命题层 2)构建第1层元件层 石板(flagstone),木材只需单排轮卡车就能运输，而 对于元件集中每一个元件，如果它的效果在目 钢材和石板则需双排轮的卡车才能运输，目标是把 木材和钢材运到C地 标集中出现，则把该元件实例化，并用上面判定互斥 的方法检查互斥，然后用效果边把元件和其对应的 给出一些操作：move,truck(创建一辆卡车)， 效果相连 load,unload 3)构建第1层命题层 对应的元件 ①向第1层中添加普通命题 movel:表示移动单排轮的卡车 首先通过持续边把i-1层的普通命题加入到i move2:表示移动双排轮的卡车 命题层，然后考察1-1层动作元件的前提，如果不 truck1:表示组装单排轮的卡车 在i命题层则加入，用上面判定互斥的方法检查互 truck2:表示组装双排轮的卡车 斥，并用前提条件边把元件和其对应的前提相连 loadl:表示装木材 ②往第i层添加对象命题 load2:表示装钢材 首先通过持续边把i-1层的对象命题加入到i load3:表示装石板 命题层，然后考察，当1层已添加的普通命题涉及到 unload1:表示卸木材 新对象A时，如果对象命题A不在i命题层则在i unload2:表示卸钢材 命题层中添加对象命题alive A. unload3:表示卸石板 ③如果在ⅰ命题层初始目标出现且不互斥，则 initial condition:(alive bodyl,alive body2, 开始搜索有效规划，否则继续扩展规划图 alive ST,alive DT,alive wood,alive steel,a- 4)构建第1层元件层 live flagstoneat bodyl A,at body2 A,at ST A. 对于元件集中每一个可行元件，如果它的效果 at DT A,at wood A,at steel A,at flagstone A} 在1层命题层出现，则实例化该元件，并用上面判定 components:movel,move2,truckl,truck2, 互斥的方法检查互斥，并根据本层的互斥确定1层 loadl,load2 load3,unloadl,unload2,unload3) 命题层中与对象命题有关的互斥，然后用效果边把 goals:at wood C,at steel C) 元件和其对应的效果相连 规划图如图2. 3.42搜索有效规划 其中truckS表示单排轮卡车，truckD表示双排 与以前的后向搜索有效规划不同，文中采用的 轮卡车 是前向搜索有效规划，算法如下： 到第5层时，初始目标出现且不互斥，开始前向 )i层为初始命题层，SP-{},其中SP,是i 搜索有效规划，最后的规划解是： 层可用前提集，初始时，把初始命题加入SP,中 step1 truckl 2)SC1},其中SC,-1是i-1层可执行元 truck2 件集，对于i·1层可实例化（元件的前提在i层的 step2:loadl 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net图 1 逆向传播互斥 Fig11 Mutex inference backward 描述如下 : 1) 所有目标命题构成第 1 层命题层 2) 构建第 1 层元件层 对于元件集中每一个元件 ,如果它的效果在目 标集中出现 ,则把该元件实例化 ,并用上面判定互斥 的方法检查互斥 ,然后用效果边把元件和其对应的 效果相连. 3) 构建第 i 层命题层 ①向第 i 层中添加普通命题 首先通过持续边把 i - 1 层的普通命题加入到 i 命题层 ,然后考察 i - 1 层动作元件的前提 ,如果不 在 i 命题层则加入 ,用上面判定互斥的方法检查互 斥 ,并用前提条件边把元件和其对应的前提相连. ②往第 i 层添加对象命题 首先通过持续边把 i - 1 层的对象命题加入到 i 命题层 ,然后考察 ,当 i 层已添加的普通命题涉及到 新对象 A 时 ,如果对象命题 A 不在 i 命题层则在 i 命题层中添加对象命题 alive A . ③如果在 i 命题层初始目标出现且不互斥 ,则 开始搜索有效规划 ,否则继续扩展规划图. 4) 构建第 i 层元件层 对于元件集中每一个可行元件 ,如果它的效果 在 i 层命题层出现 ,则实例化该元件 ,并用上面判定 互斥的方法检查互斥 ,并根据本层的互斥确定 i 层 命题层中与对象命题有关的互斥 ,然后用效果边把 元件和其对应的效果相连. 31412 搜索有效规划 与以前的后向搜索有效规划不同 ,文中采用的 是前向搜索有效规划 ,算法如下 : 1) i 层为初始命题层 , SPi ←{ } ,其中 SPi 是 i 层可用前提集 ,初始时 ,把初始命题加入 SPi 中. 2) SCi - 1 ←{} , 其中 SCi - 1 是 i - 1 层可执行元 件集 ,对于 i - 1 层可实例化 (元件的前提在 i 层的 可用前提集中) 的元件 Cs ,如果它不与 SCi - 1中已选 元件互斥 ,且不在 SCi - 1 中 ,则把 Cs 加入 SCi - 1 ,并 把 Cs 的效果加入 i - 1 层可用前提集 SPi - 1中. 3) 对于 SCi - 1 中的每一个元件 Cs 和 Ct ,考察 Cs 的引致元件 Cm 和 Ct 的引致元件 Cn ,如果 Cm 与 Cn 互斥 ,则要选 Cm 和 Cn 之一进行抵制. 4) 如果 i = 1 ,则 SCi - 1 ,SCi - 2 , ……,SC1 构成规 划解 ,否则 i - 1 重复上面的步骤. 315 例子 在 A 地有 2 个卡车车身(body) ,一组单排轮轮 胎(single tire ,ST) ,一组双排轮轮胎 (double tires , D T) ,一批木材(wood) 和一批钢材 (steel) 还有一批 石板(flagstone) ,木材只需单排轮卡车就能运输 ,而 钢材和石板则需双排轮的卡车才能运输 ,目标是把 木材和钢材运到 C 地. 给出一些操作 : move ,truck (创建一辆卡车) , load ,unload 对应的元件 : move1 :表示移动单排轮的卡车 move2 :表示移动双排轮的卡车 truck1 :表示组装单排轮的卡车 truck2 :表示组装双排轮的卡车 load1 :表示装木材 load2 :表示装钢材 load3 :表示装石板 unload1 :表示卸木材 unload2 :表示卸钢材 unload3 :表示卸石板 initial condition :{alive body1 ,alive body2 , alive ST , alive D T , alive wood , alive steel , a2 live flagstone ,at body1 A , at body2 A , at ST A , at D T A , at wood A , at steel A , at flagstone A} components: { move1 , move2 , truck1 , truck2 , load1 ,load2 ,load3 ,unload1 ,unload2 , unload3} goals:{at wood C ,at steel C} 规划图如图 2. 其中 truckS 表示单排轮卡车 ,truckD 表示双排 轮卡车. 到第 5 层时 ,初始目标出现且不互斥 ,开始前向 搜索有效规划 ,最后的规划解是 : step1 :truck1 truck2 step2 :load1 ·16 · 智 能 系 统 学 报 第 2 卷