基于动态规划库的规划识别算法的研究

冯 萍

(长春大学 计算机科学技术学院,吉林 长春 130022)

基于动态规划库的规划识别算法的研究

冯 萍

(长春大学 计算机科学技术学院,吉林 长春 130022)

本文在 Kautz规划识别方法的基础上,给组成规划的各动作按其对该规划出现的影响程度确定一个权值,并在规划库搜索和匹配机制中应用模糊处理,从而建立了基于动态规划库的模糊规划识别模型。

规划库;规划识别;加权模糊

0 引 言

Schmidet[1]在 1978年第一次提出规划识别问题。规划识别问题属于心理学和人工智能交叉领域的问题,主要应用在故事理解、自然语言识别、谈话分析、心理学模型和智能计算机接口等领域,随着规划识别的发展,它的应用领域也逐渐地在扩展。规划识别[2]是根据观察到的片段琐碎的现象,推出具有合理的因果联系的完整而全面的规划描述的过程。一个规划识别器推出的规划既能补充一些我们未观察到而又实际发生的现象,同时还可以预测未来──合理地推出Agent未来可能采取的动作。

Kautz[3]在 1986年第一次基于限定理论和最小化集合的思想提出了规划识别的通用框架,在 1987年提出了规划识别的形式理论。Kautz方法的不足之处在于识别得到的是所观察到的动作的最小规划集。如果规划集里有多个规划时,它不能够确定哪一个规划更能解释观察到的动作集合;高层规划的确定是根据具体的问题来确定的,没有明确的标准;不能识别没有出现在规划库中的新规划,即它要求规划库是完备的。为了简化和实现 Kautz提出的识别框架,很多人做了大量努力。姜云飞[4]等人提出利用规划知识图进行计划识别。Carberry[5]根据对自然对话的分析以及对人类推理的心理研究提出了一个基于默认推理的计划识别模型。Charniak等人[6]提出一种基于贝叶斯网络的规划识别模型。Bauer[7]提出将证据理论运用到智能帮助系统领域的计划识别中。Azarewicz[8]等人采用基于模板匹配的方法实现规划识别,并基于该方法借助于L ISP语言实现了一个战术态势估计系统,为海军指挥员提供辅助决策。Villain[9]提出了采用语法分析的方法进行规划描述。Hong[10]提出利用目标图进行计划识别。Yin[11]在 Hong的目标图的基础上提出了利用回归图进行计划识别。

在以上建立的规划识别模型中,Kautz规划识别表示方法中提出的封闭世界分层模型是它们讨论的基础,其核心是规划库的建立。显然,为了适应真实环境下的规划识别求解,必须动态建立规划库。为此本文提出利用面向对象的方法构造规划库,并利用加权模糊法描述规划,设计出基于动态规划库的规划识别算法。

1 算法设计前提

为了保证算法的完备性,本算法基于以下两个封闭世界假设：

(1)已知的执行一个动作的方法就是执行该动作的所有方法;(即系统的设计者具有完备的知识。)(2)所有动作都是有目的的,必须知道执行一个动作的所有可能的理由。

这些假设用来评价从一个观察到的动作集合得到的结论是否合理,可以通过McCarthy的限定理论体现。

2 规划的加权模糊描述方法

在传统的规划描述中,规划的各子前提事件之间往往是“平等”的,没有侧重之分,在合取式 A1∧A2∧…∧AN中,其真值为各子式真值的最小值。因而只要一子式 A,(1≤i≤n)为假,整个式子即为假。n为假,整个式子即为假。同样在析取式A1∨A2∨…∨AN中只要有一式 Ai.(i≤n)为真,全式即为真,这尽管也反映了一部分客观联系,但仍与许多情形不符。因此不应该对组成规划的各事件“一视同仁”[7、8],也就是说各事件在决定该规划是否发生时占的权重不应一样。

同时,根据观察到的事件,可能会找到多个满足条件的规划集,但它们在现实世界中出现的可能性是不一样的。这主要是由于观察到的事件在满足条件的规划内的重要程度不同所致。由于重要程度不同,所以观察到的事件对规划出现可能性的支持程度也不同。因此根据各事件在不同规划中所占的不同权值来估算各个规划出现的可能性就可以找到最可能出现的规划──最优解。

在本算法中也考虑到具体应用中对观察到事件的描述和规划库中事件描述未必完全一致,也许会是一些模糊概念,我们也会对特殊事件作模糊匹配。因而,本文中我们采用加权模糊法[7、8]来描述规划,并用一阶谓词逻辑来表示规划,以便于我们推导规划可信度。

3 规划可信度的设定

设 x1,x2,…x为 n个 (n≥2)加权前提事件,P(xi)为由 xi组成的规划。它们的真度分别为 T(x1),T(x2),…,T(xn),实数 w1,w2,…,wn为满足 的权系数,则

P(x)是个加权前提事件集也是个加权与事件集,我们称其为“P的加权合取式”,其真度为:

即合取式的真度为各子式真度的加权和。

设τi为某一规划 Pi的确认阈值[9]。当 Pi≥τi时,该条规划即被确认。并称规划为已识别规划。即我们有理由确信该规划为识别器的解。

此时如果该规划M不是独立规划,则将其目标事件在作为前提事件在规划库中继续查找上层规划N。那么目标事件真度为其上层规划N的前提事件,其事件真度我们设置为规划M的可信度,即 TN(x)=PM(x)。

在上述推理过程中,当某一子前提真度未知时,可将其设为 0,即假设为假,此时,只要根据其各已知前提事件的真度和权值计算出的规划可信度 P大于或等于规则的使用阈值τ时,该规划仍可被确认,这就为不完全信息的处理提供了可能,也使得我们的规划识别器可以预测未来将要发生的事件序列。

4 基于动态规划库的规划识别模型

面向对象的程序设计技术(称O-O技术)作为一种新的程序设计技术已得到广泛的重视。“类”和“对象”是面向对象方法的精华。本文中我们基于面向对象的程序设计思想把知识规则的结构和模糊推理方法定义成规则类,把具体的规则定义成规则类的实体 (即对象),用这些规则实体构建动态链表从而组成动态规划库,推理的过程由规划库中各规则实体提供的方法完成。

根据上述思想建立的模型如图 1所示。

图 1 基于动态规划库的规划识别模型

5 加权模糊规划识别算法

每次识别过程中规划器都依次调用规划链中每个规划对象的识别函数,直至识别结束,输出结论。

在识别算法包括以下步骤：

(1)规划器首先读入已知事件,到基本事件库中进行模糊匹配,调用相应隶属度函数求其事件真度,即在基本事件链中找相似事件。若求得的事件真度为 0,意味着没有相似事件,则将这一前提事件由ADD函数将其追加到基本事件库。否则提取其在基本事件库中的事件号和事件真度生成基本事件链。

(2)在基本事件链中读取一个基本事件,从规划库中找到包含这一基本事件的所有规划,此时基本事件就是这些规划的前提事件,提取该前提事件在这些规划中的权值和对应的规划号,动态规划库里。

(3)处理下一前提事件,重复步骤 1、2直到所有前提事件处理完毕。比较这些前提事件对象,将规划号相同的前提事件组成新的链表。

(4)调用求规划可信度函数,根据各前提事件的事件真度和权值计算出该规划的可信度,如大于等于事先给定的阈值,则确认该规划,否则换一下条规划重新进行判断。(实验初期我们把阈值暂时定位 0.35)

(5)在每一条规划被确认后,输出该规划(为规划库中的完整规划,即包含尚未出现的事件)。并将已输出的前提事件对象从前提事件链中删除。同时,要从规划库中提取该规划目标事件的独立标记,如为 Y,则结束识别。如为N,则要将该目标作为前提事件再次进行识别,即把目标事件连接到已处理完的前提事件后面返回步骤 1,此时将该规划的可信度作为目标事件在上层规划中前提事件的事件真度。

6 结 语

传统的规划识别的方法是根据观察动作建立规划库,根据一定的搜索和匹配机制来获取规划解。本文采用给组成规划的各动作按其对该规划出现的影响程度确定一个权值,使规划识别器能够快速准确地识别出规划。在规划库搜索和匹配机制中应用模糊处理,使得模糊理论在规划识别中得以运用,所以得到的结果更加符合客观事实。

[1] Henry,A.,Kautz,A.For mal theory of plan recognition[Ph.D.Thesis].Rochester：University of Rochester,1987.

[2] Blum,A.L and Furst,M.L.,Fast Planning Through Planning GraphAnalysis.In Proceedingof the InternationalJointConference onArtificial Intelligence,1995,1636-1642.

[3] KAUTZHA.A FormalTheory of PlanRecognition[D].PhD thesis,USA：University of Rochester,1987.

[4] 姜云飞,马宁.一种基于规划知识图的规划识别算法[J].软件学报,2002,13(4)：686-692.

[5] CARBERRY S.IncorporatingDefault Inferences intoPlan Recognition[C]//Proc.the 8thNationalConference on Artificial Intelligence.Boston, USA：[s.n.],1990：471-478.

[6] CHARN IAK E,GOLDMAN R P.A BayesianModel of Plan Recognition[J].Artificial Intelligence,1993,64(1)：53-79.

[7] BAUER M.A Dempster-shaferApproach toModeling A gentPreferences forPlan Recognition[J].User Modeling andUser-Adapted Interaction, 1995,5(3-4)：317-348.

[8] AZAREW ICZ J,FALA G.Template-basedMulti-agent Plan Recognition for Tactical Situation Assess ment[C]//Proc.5th conference on Artificial Intelligence Application.Miam,i FL,USA：[s.n.],1989：247-254.

[9] V ILA IN M.Getting Serious about Parsing Plans：A GrammaticalAnalysisofPlan Recognition[C]//Proc.8thNationalConference onArtificial Intelligence,Boston,USA：[s.n.],1990：190-197.

[10] HONG J.PlanRecognition through Goal Graph Analysis[J].Journal ofArtificial Intelligence Research,2001,15(1)：1-30.

[11] Y INM,GU W,L IU R.Using Regressive Graph as a Novel Paradigm in Plan Recognition[C]//Proc.International Conference on Machine Learning and Cybernetics,Xi an,China：[s.n.],2003,3：1636-1641.

责任编辑：吴旭云

A research of plan recogn ition algorithm based on dynam ic plan library

FENG Ping
(College of Computer Science and Technology,Changchun University,Changchun 130022,China)

According to Kautz plan recognition algorithm,we give every action of the plan a right value on the basis of their influence degrees and use fuzzy processing in searching and matchingmechanis m so as to establish a fuzzy plan recognition model based on dynamic plan library.

plan library;plan recognition;weighted fuzzy

TP301

A

1009-3907(2010)06-0070-03

2010-04-22

冯萍(1977-),女,吉林通化人,讲师,主要从事智能规划与规划识别方面研究。