《处理条件效果的互斥延迟算法的研究.pdf》由会员分享，可在线阅读，更多相关《处理条件效果的互斥延迟算法的研究.pdf（4页珍藏版）》请在三一文库上搜索。
1、第40 卷第1 期 2 (X)8 年 3月 东 北 师 大 学 报 (自然 科 学 版 ) J ou川 目ofN o rt h east N ol 袱 园U ni ty( N a t ur al豁ence E 冶 i t io n ) 、 乞 1 . 40 Nb . 1 March 2 0() 8 文章编号 l 0( X 卜 1 8 3 2 ( 2 0()8 0 1 一 (X)3 2 一 04 处理条件效果的互斥延迟算法的研究 刘日 仙 ， 苏卫华 “ ， 谷文祥“ ， 袁利永3 ( 1 . 金华职业技术学院， 浙江金华驼1 017; 2 . 东北师范大学计算机学院， 吉林 长春 1 3002
2、4 ; 3 . 浙江师范大学信息科学与工程学院， 浙江金华 321 004) 摘 要 通过将带有条件效果的动作分解成元件， 然后利用互斤延迟算法进行规划图的扩 张， 得到规划图. 规划图生成后， 从初始条件出 发， 利用一个前向 的 搜索过程进行搜索以求规划 解. 在搜索中 ， 选择的不是单个的动 作， 而 是独立集， 这样可以明 显地减小搜索空间， 而且在搜 索过程中， 还利用了独立集之间的执行次序作为独立集选择的 启发式， 加快搜索过程. 该算法 大大地简化了搜索过程， 提高了 搜索效率. 关键词 规划; 人工智能规划; 条件效果; 扩张时间步; 延续时间步; 相互独立集 【 中图分类号
3、T P18 学科代码 5 2 0 2 0【 文献标识码 A 0 引言 人工智能系 统规划方法是人工智能研究领域中的 重要方法 一1 9 95年美国的A . L ， Bl tnn 和M. L F tirst 提出了一种利用规划图分析( Pl an n i ng G r a p h八 刀 al y si s ) 的快速规划方法图规划( G r a p h - p lan ). . 图 规 划 方 法由 于 其良 好的 性能， 引 起了 人们的 广 泛 关注和 研 究. 图 规 划 之 所以 能 够具 有良 好的 性能， 很大一部分归功于互斥关系的传播. 在图 规划中， 利用互斥关系大大地减少了搜索
4、的空间， 提高了 搜索的 效率. 所以很多研究者们都致力于如何处理互斥关系， 以便更好地提高搜索的效率. 文献 3 给出 一种新的 处理互斥关系的互斥动作延迟算法. 本文对文献【 3的互斥延迟算法进行了扩展， 使它能够处理包含条件效果的动作之间的互斥关系， 但我们的 算法与文献【 3中的算法有很大的 不同， 主要表现在以下几个方面: ( 1)在文献【 3中， 只涉及单个的动作之间的序要求， 而我们不仅涉及了单个元件之间的序要求， 还 涉及了 独立集之间的序要求. 利用元件之间的序要求来判定独立集之间的执行次序， 但并不能根据元件 之间的序要求完全地确定独立集之间的执行次序， 只能确定部分独立集
5、之间的执行次序. ( 2)在搜索中， 我们把同一时间步的 各个独立集之间的执行次序作为独立集选择的启发式， 这样可 以加快搜索的速度. ( 3)在我们的元件互斥延迟算法中， 采用的是状态空间的深度优先搜索， 是一个从初始条件前向的 搜索过程， 而文献【 3中采用的是后向的回溯搜索过程. 1 研究基础 条件效果是动作描述中与上下文相依赖的效果， 一般用一个w h e n 子句来表示条件效果。 C b r i n R. 【 收稿日 期1 墓金项目 作者简介 2 0(拓刀， 一 20 国家自 然科学基金资助项目( 以 ) 4 7 3042， 6057引 拓 7)， 东北师范大学自 然科学青年基金资助
6、项目. 刘日 仙( 1 98砚卜 一 ) ， 女， 硕士， 主要从事智能规划与规划识别研究 能规划与规划识别研究. ; 谷文祥(l947 一) ， 教授， 博士研究生导师， 主要从事智 万方数据 第1 期刘日 仙. 等: 处理条件效果的互斥延迟算法的研究 八 刀 d e 二 ， L 冶 v id E . S m i th和D 田 l iels . w el d 提出了 一种在图规划框架下处理条件效果的方法 要素 扩展法( F a c to 双 妇e x p a n 6 lon) ， 其主要思想是将带有条件效果的动作的所有效果条件化， 然后生成元 件3， 这一 算法确实可以 处理带 条件效果动作
7、的 规划问 题， 但是它的 不足之处是有时 会使搜索过程复 杂化. 在条件效果规划图中同样存在着两种互斥关系: 命题互斥和动作元件互斥. 命题尸和Q在第j 层上互 斥当 且仅当 所有产生命题尸的 方法( 例如第j 一 1 层上的 所有以 命题尸 作为肯定命题出现在其效果中的动作元件) 和所有产生命题 Q的方法相互排斥. 在动作元件的 互斥关系上， 有三种情况， 元件Cn 和C 护n 在第j 层上互斥: ( 1)干扰沪不一致效果: 元件Cn 和 加 之 来自 不同的动作实例， 而且元件 Cn 的效果删除了 元件C 孙 2 的前提或效果. ( 2)竞争需求: 元件Cn 和C m的 前提在第j 一
8、1 层互斥. (3) 引致元件: 以 是元件Cn 的引致元件， 而 嵘 和C ， n互斥， 则 Cn 和O n互斥. 对元件的抵制 ( 图 n f r o n tation) 是指通过否定元件的前提条件来阻止元件的执行. 2 规划图的生成 2 . 1 元件互斥关系的分析 在规划图扩张的过程中， 元件之间可能出现互斥关系， 这说明具有互斥关系的两元件不能在同一时 间步执行， 必须串行执行， 即有一个元件先执行， 另一个元件后执行. 当 元件C l 与元件C Z 互斥时， 有时只是它们不能同时发生， 至于是元件C l 需要延迟执行， 还是元 件C Z 需要延迟执行， 对于最终的规划解不产生影响.
9、在这种情况下， 我们就说互斥元件 C l 和C Z 无序 要求. 在这种情况下， 可以随机指定一个元件到延续时间步去执行. 而有时互斥元件C l 和C Z 哪个作为 延迟元件， 对规划解是会产生很大影响的. 有时只有一个先发生， 另一个才有意义. 有时如果一个元件先 执行了， 另一个元件就不能执行了. 在这种情况下， 我们就说互斥元件C l 和C Z 有序要求. 不难看出， 当 互斥元件C l 和C Z 有序要求时， 如果元件 C l 先执行， 元件 C Z 才有意义， 则应该把元件 C Z 作为延迟 元件. 如元件 C l 先执行， 元件C Z 就不能发生， 则应该把元件 C l 作为延迟元
10、件. 综上所述， 对于同一时 间步上的两个互斥元件， 我们可以通过对它们的互斥关系进行分析， 然后根据它们是否有序要求利用延 续时间步以使它们在不同的时间步执行. 根据互斥关系， 我们可以把某一时间步上的元件划分为多个相 互独立集， 独立集内的元件之间 是不互斥的， 独立集间的元件是互斥的. 如果某一时间步有多个相互独 立集， 则需要多个延续时间步来延续独立集. 2 . 2 规划图扩张 我们生成规划图的主要思想是: 在扩张规划图时， 生成某一时间步的元件列后， 根据互斥关系将没 有互斥关系的元件归人一个集合中( 称这样的一个集合叫相互独立集， 即集合内的每个元件间没有互斥 关系) ， 这样元件
11、列中的所有元件分成了若干个相互独立集. 各种独立集之间互不相交， 即没有相同的元 件， 一元件只能属于其中一个独立集. 独立集内的元件之间不互斥， 独立集之间的元件互斥， 如果某一时 间步的独立集的个数大于1 ， 说明这几个独立集不可能在同一时间步执行， 有的独立集必须进行延迟. 延续时间步的主要作用是延续元件的执行效果( 包括添加效果和删除效果) ， 因为相互独立集间的元件 不能在同一时间步执行， 所以 必须通过延续时间步来使不能在同一时间步执行的独立集串 行化执行. 我 们把非延续时间步称为扩张时间步， 为了区分延续时间步和扩张时间步， 我们可以利用一个动态一维数 组， 对时间步进行标识，
12、 如果是扩张时间步， 则用“ 1 ” 表示， 延续时间步用“ 0 ” 表示. 如果某一时间步有 m 个独立集， 则我们将延迟 m一 1 个时间步， 这 m一 1 个时间步上的元件列相同， 也是原来的这些独立集. 在搜索时， 我们把独立集作为一个单元， 在某一时间步直接选择一个独立集， 这样可以很大程度地减少 搜索的循环. 具体扩张算法如下: ( 1)时间步 1 命题列的生成. 将所有的初始条件作为时间步1 命题列的命题， 一个命题一个结点. 万方数据 东北 师 大 学报 ( 自然科 学版)第40 卷 ( 2)时间步1 元件列的生成. 对元件集合中的每一元件进行考察， 把能够实例化的元件进行实例
13、化 ( 只要元件的前提条件都在时间步1 的命题列中， 该元件就可以实例化) . 每实例化一个元件， 就可以添 加一个元件结点( corn p o n e ntn ede)， 这样便得到时间步1 的元件列. 同时将所有元件与其对应的前提条 件用前提条件边( p r e co n d i t io n d e g e ) 连接起来. ( 3)标识时间步1 元件列中的元件互斥关系， 根据互斥关系找出 各相互独立集， 确定独立集之间的 执行次序. 如果相互独立集的 个数大于1 ， 则接下来便是延续时间步， 反之， 接下来的是扩张时间步. ( 4 ) 如果是延续时间 步， 则保留 上一时间步的 所有非n
14、 o p 元件， 并添加所有的n o p 动作( 命题列中的 每个命题都可以 通过n o p 动作延续到下一时间步) ， 自 然接下来生成的 命题列与上一命题列完全相同. 这便达到了延续作用， 但需注意的是， 这并不属于后面所说的 规划图 稳定状态. ( 5 ) 如果是扩张时间步， 则如果此扩张时间步是紧接在延续时间步之后的， 那么该扩张时间步内则 不考虑上一延续时间步内 所有非n o p 动作， 只 需添加新增加的 元件及n o p 动作. 如果此扩张时间步是接 在扩张时间步之后则按时间步1 元件列的生成方式一样生成元件列. 扩张时间步的命题生成之后， 查看 其间是否包含所有目 标命题且任意
15、两目 标之间不互斥， 若是， 则开始搜索有效规划， 进人搜索阶段; 否 则， 查看该命题列是否与上一命题列相同且是否互斥关系也相同， 若是， 则表示规划图稳定， 目 标命题不 能实现， 规划图扩张结束， 若不是， 则继续进行规划图扩张， 查看相互独立集， 确定下一时间步是延续时 间步还是扩张时间步， 直到目 标实现或规划图稳定. 3 搜索有效规划 规划间题的一个中心任务是找出有效规划 给定一个规划图， 我们通过前向搜索来寻找一个有效规 划. 基本思想是: 先检查目 标是否以非互斥关系出现在规划图的最后一时间步的命题列中， 如果是， 则开 始搜索; 如果没有全部出现则说明还不存在有效规划， 继续
16、扩张规划图. 我们从规划图的 初始条件开始， 选择时间步1 中的一个相互独立集， 然后对初始条件运用独立集， 得到时间步1 的状态， 接着在时间步 2 选择一个相互独立集， 得到时间步2 的状态， 一直如此， 直到在最后一个时间步 n选择一个相互独立 集， 得到时间步n的状态， 如果时间步n的状态中包含目 标集， 则时间步1 的独立集到时间步n的独立 集组成有效规划; 否则， 回溯到前一时间步重新选择一独立集， 如此循环， 直到搜索到有效规划或规划不 存在. 当规划不存在时， 我们将继续扩张规划图， 然后进行搜索， 直到搜索到有效规划或规划图达到稳定 状态. ， 我们的搜索算法主要有以下两个特
17、点: ( 1)将独立集看作一个独立的单元进行搜索; ( 2 ) 搜索算法是一个前向的回 溯搜索过程. 具体的搜索算法如下: 51表示当前第1 时间步的状态: ( 1 ) 5 0 初始条件集合. ( 2 ) 对于时间步 1 : 如果时间步 1 是扩张时间步， 则 A . 根据时间步1 中独立集之间的执行次序， 选择要求先执行的独立集 尸 ; 如果独立集没有执行次 序， 则任选一独立集尸 ; B . 对状态51一 1 运用独立集得到状态51; C . 如果时间步1 中有另一独立集P ， P中的元件C 孙 忍 引致了尸 中的元件Cn ， 则对元件Cn 进行抵 制， 因为独立集 P与尸 之间是互斥的，
18、 而 C n i 的执行将导致元件Cn 的执行， Cn 的执行将阻碍独立集 P的执行， 所以对元件 Cn 进行抵制; D . 如果状态 5包含目 标集， 则时间步 1 到时间步 1 所选的各个独立集组成了有效规划， 退出该循 环; E . 如果1 是规划图的最后一个时间步， 则继续扩张规划图; 万方数据 第 1 期刘日 仙， 等: 处理条件效果的互斥延迟算法的研究 F . 如果1 是规划图达到稳定的时间步， 则退出搜索过程. 如果时间步 1 是延迟时间步， 则 A . 选择一与前面几个延续时间步所选的独立集不相同的独立集; B . 然后对状态5一1 运用独立集得到状态 5; C . 如果时间步
19、1 中有另一独立集尸 ， P中的 元件C 阴引致了尸 中的元件Cn ， 则对元件Cn 进行抵 制， 因为独立集P与尸 之间是互斥的， 而C ， n的执行将导致元件Cn 的执行， Cn 的执行将阻碍独立集 尸的执行， 所以对元件 Cn 进行抵制; D . 如果状态5包含目 标集， 则时间步1 到时间 步1 所选的各个独立集组成了有效规划， 退出 该循 环. ( 3)返回该有效规划. 4 小结 本文的 互斥元件延迟算法通过扩张规划图， 然后从初始条件出发进行一个前向的搜索过程以求规 划解. 在搜索过程中， 把独立集作为搜索选择的单元， 大大地减小了搜索空间， 提高了搜索效率. 独立集 之间的执行次
20、序是搜索时的一个启发式， 如果能够完全地确定独立集之间的执行次序， 则能生成一个无 冲突的规划图， 且可以直接提取规划解， 而无需搜索过程. 所以独立集的串行化是一个关键的问题， 还有 待于进一步研究. 参考文献 1 周治国， 李文印， 邓春燕， 等. 办公自 动化系 统中双层数字签名的研究与实现【 J. 东北师大学报: 自 然科学版， 2 加5 ， 3 7(4): 2 3 - 2 7 . 2 A v R I ML B L 工 刀 以 ， 州 田 R R I CK L F U R S T . E 明 t p 肠 阴 1吧t 卜 皿妙 p lBx 面 昭9 。 甲 h ar 园 师5 J . A
21、 rt i f ic iall n t e ll lg e n e ， 1 9 97， 卯: 281 - 3 0(】 . 3 谷文 祥， 孙铁 利， 吕 英华. 智能 规划中 互斥动 作延迟 算法 研 究 J. 东 北师 大 学报: 自 然 科学版. 2 (X)3 ， 3 5 ( 3): 9 4 一 9 8. 【 4 韩毅， 陈 建， 吕 英华， 等. 自 组 织神经网 络在C R M中的 应用 Jl. 东北师大学报: 自 然科学版， 2 加6 ， 3 8 ( 1 ) : 3 1 一 35. A na l g 0 r i t h mon i n t e r fe r i n g act i o
22、 ns d e fe n rn e n t for h a n d l i n g con d i t i ona l e f fe c t s i nt h e i n t e l l i g e n t P l a n n i n g LI URi 一 xi anl， SU w ei 一 h uaz， G Uw en 一 xi an 扩， Y U A NLi 一 扣 褚 ( 1 . J inhtja伪11 电 e ofp ro f es 曲 川 2 . 伪U 昭e ofQ如p u t e r ， N 6 rt h e ast N o m过U ni v e r s l ty， C hangc
23、 h un 1 3( X) 2 4 ， C 抽 na; ， 3 . 肠U 电e ofl 几 Fo rma t i加 氏i e n c e a l记E 飞in ee 均 唱， Z h ej l 肛 堪N 6 m过U n iv e r s l ty， J 让 由 ua3 2 1 (X)4 ， C 扬 na) Abs t ra c t : T h i s p a pe r i nt rc 沮 u c est h e con c ePtsofo r d e r l y i nt e 川 池 ri ng com pon e n t s and non- or de rl y in t e r f e r
24、i ng 。 卫 n p o n e n tsino r d e r tor 哪1 v e t he p ro b 1 em ofi n t e rf ering a c t ions d e f e rme n t with con d i t iona 1 e f f ec t s . his 祀 理con ve ni ent for t h e a l即r it h mtocrea tea p l an g ra p h . 赶t erthe p l angra p hiscrea 回 ， a fo 州田 月h p rocesscan beg i n 1 rom t h e initi
25、alcon di t 1 o n . 玩t hesear c h p 。， t h e i n d e 钾n d e n c e set i nst 巴 dofai 心e ac- t i o n isc hi 力 se ntosu p portt h e su b g oal. Thiscan si 加fi can d yr e d u c est h e searchsP a c e . A l 阳， t heo r d e r 悦- tween t h e in ds沐 n d encese tsis u 涨 月ash e u ri sticstos 详 ed叩t hesear c h p 找 犯 。 犯 . 肠th e al 即ri t l l mg r e a t lyim- p r o v esthe sear c hP 双 犯 已 治 . K e 卿0 川5 : in t e l l i g e n c e p l anm 眼; p l ang r a p h ; 印n d i t i o n ale l l ec t s ; i nde Pen d e n c e set ( 责任编辑: 陶理) 万方数据