基于動態(tài)規(guī)劃庫的規(guī)劃識別算法的研究

馮 萍

(長春大學(xué) 計算機科學(xué)技術(shù)學(xué)院,吉林 長春 130022)

基于動態(tài)規(guī)劃庫的規(guī)劃識別算法的研究

馮 萍

(長春大學(xué) 計算機科學(xué)技術(shù)學(xué)院,吉林 長春 130022)

本文在 Kautz規(guī)劃識別方法的基礎(chǔ)上,給組成規(guī)劃的各動作按其對該規(guī)劃出現(xiàn)的影響程度確定一個權(quán)值,并在規(guī)劃庫搜索和匹配機制中應(yīng)用模糊處理,從而建立了基于動態(tài)規(guī)劃庫的模糊規(guī)劃識別模型。

規(guī)劃庫;規(guī)劃識別;加權(quán)模糊

0 引 言

Schmidet[1]在 1978年第一次提出規(guī)劃識別問題。規(guī)劃識別問題屬于心理學(xué)和人工智能交叉領(lǐng)域的問題,主要應(yīng)用在故事理解、自然語言識別、談話分析、心理學(xué)模型和智能計算機接口等領(lǐng)域,隨著規(guī)劃識別的發(fā)展,它的應(yīng)用領(lǐng)域也逐漸地在擴展。規(guī)劃識別[2]是根據(jù)觀察到的片段瑣碎的現(xiàn)象,推出具有合理的因果聯(lián)系的完整而全面的規(guī)劃描述的過程。一個規(guī)劃識別器推出的規(guī)劃既能補充一些我們未觀察到而又實際發(fā)生的現(xiàn)象,同時還可以預(yù)測未來──合理地推出Agent未來可能采取的動作。

Kautz[3]在 1986年第一次基于限定理論和最小化集合的思想提出了規(guī)劃識別的通用框架,在 1987年提出了規(guī)劃識別的形式理論。Kautz方法的不足之處在于識別得到的是所觀察到的動作的最小規(guī)劃集。如果規(guī)劃集里有多個規(guī)劃時,它不能夠確定哪一個規(guī)劃更能解釋觀察到的動作集合;高層規(guī)劃的確定是根據(jù)具體的問題來確定的,沒有明確的標準;不能識別沒有出現(xiàn)在規(guī)劃庫中的新規(guī)劃,即它要求規(guī)劃庫是完備的。為了簡化和實現(xiàn) Kautz提出的識別框架,很多人做了大量努力。姜云飛[4]等人提出利用規(guī)劃知識圖進行計劃識別。Carberry[5]根據(jù)對自然對話的分析以及對人類推理的心理研究提出了一個基于默認推理的計劃識別模型。Charniak等人[6]提出一種基于貝葉斯網(wǎng)絡(luò)的規(guī)劃識別模型。Bauer[7]提出將證據(jù)理論運用到智能幫助系統(tǒng)領(lǐng)域的計劃識別中。Azarewicz[8]等人采用基于模板匹配的方法實現(xiàn)規(guī)劃識別,并基于該方法借助于L ISP語言實現(xiàn)了一個戰(zhàn)術(shù)態(tài)勢估計系統(tǒng),為海軍指揮員提供輔助決策。Villain[9]提出了采用語法分析的方法進行規(guī)劃描述。Hong[10]提出利用目標圖進行計劃識別。Yin[11]在 Hong的目標圖的基礎(chǔ)上提出了利用回歸圖進行計劃識別。

在以上建立的規(guī)劃識別模型中,Kautz規(guī)劃識別表示方法中提出的封閉世界分層模型是它們討論的基礎(chǔ),其核心是規(guī)劃庫的建立。顯然,為了適應(yīng)真實環(huán)境下的規(guī)劃識別求解,必須動態(tài)建立規(guī)劃庫。為此本文提出利用面向?qū)ο蟮姆椒?gòu)造規(guī)劃庫,并利用加權(quán)模糊法描述規(guī)劃,設(shè)計出基于動態(tài)規(guī)劃庫的規(guī)劃識別算法。

1 算法設(shè)計前提

為了保證算法的完備性,本算法基于以下兩個封閉世界假設(shè)：

(1)已知的執(zhí)行一個動作的方法就是執(zhí)行該動作的所有方法;(即系統(tǒng)的設(shè)計者具有完備的知識。)(2)所有動作都是有目的的,必須知道執(zhí)行一個動作的所有可能的理由。

這些假設(shè)用來評價從一個觀察到的動作集合得到的結(jié)論是否合理,可以通過McCarthy的限定理論體現(xiàn)。

2 規(guī)劃的加權(quán)模糊描述方法

在傳統(tǒng)的規(guī)劃描述中,規(guī)劃的各子前提事件之間往往是“平等”的,沒有側(cè)重之分,在合取式 A1∧A2∧…∧AN中,其真值為各子式真值的最小值。因而只要一子式 A,(1≤i≤n)為假,整個式子即為假。n為假,整個式子即為假。同樣在析取式A1∨A2∨…∨AN中只要有一式 Ai.(i≤n)為真,全式即為真,這盡管也反映了一部分客觀聯(lián)系,但仍與許多情形不符。因此不應(yīng)該對組成規(guī)劃的各事件“一視同仁”[7、8],也就是說各事件在決定該規(guī)劃是否發(fā)生時占的權(quán)重不應(yīng)一樣。

同時,根據(jù)觀察到的事件,可能會找到多個滿足條件的規(guī)劃集,但它們在現(xiàn)實世界中出現(xiàn)的可能性是不一樣的。這主要是由于觀察到的事件在滿足條件的規(guī)劃內(nèi)的重要程度不同所致。由于重要程度不同,所以觀察到的事件對規(guī)劃出現(xiàn)可能性的支持程度也不同。因此根據(jù)各事件在不同規(guī)劃中所占的不同權(quán)值來估算各個規(guī)劃出現(xiàn)的可能性就可以找到最可能出現(xiàn)的規(guī)劃──最優(yōu)解。

在本算法中也考慮到具體應(yīng)用中對觀察到事件的描述和規(guī)劃庫中事件描述未必完全一致,也許會是一些模糊概念,我們也會對特殊事件作模糊匹配。因而,本文中我們采用加權(quán)模糊法[7、8]來描述規(guī)劃,并用一階謂詞邏輯來表示規(guī)劃,以便于我們推導(dǎo)規(guī)劃可信度。

3 規(guī)劃可信度的設(shè)定

設(shè) x1,x2,…x為 n個 (n≥2)加權(quán)前提事件,P(xi)為由 xi組成的規(guī)劃。它們的真度分別為 T(x1),T(x2),…,T(xn),實數(shù) w1,w2,…,wn為滿足 的權(quán)系數(shù),則

P(x)是個加權(quán)前提事件集也是個加權(quán)與事件集,我們稱其為“P的加權(quán)合取式”,其真度為:

即合取式的真度為各子式真度的加權(quán)和。

設(shè)τi為某一規(guī)劃 Pi的確認閾值[9]。當 Pi≥τi時,該條規(guī)劃即被確認。并稱規(guī)劃為已識別規(guī)劃。即我們有理由確信該規(guī)劃為識別器的解。

此時如果該規(guī)劃M不是獨立規(guī)劃,則將其目標事件在作為前提事件在規(guī)劃庫中繼續(xù)查找上層規(guī)劃N。那么目標事件真度為其上層規(guī)劃N的前提事件,其事件真度我們設(shè)置為規(guī)劃M的可信度,即 TN(x)=PM(x)。

在上述推理過程中,當某一子前提真度未知時,可將其設(shè)為 0,即假設(shè)為假,此時,只要根據(jù)其各已知前提事件的真度和權(quán)值計算出的規(guī)劃可信度 P大于或等于規(guī)則的使用閾值τ時,該規(guī)劃仍可被確認,這就為不完全信息的處理提供了可能,也使得我們的規(guī)劃識別器可以預(yù)測未來將要發(fā)生的事件序列。

4 基于動態(tài)規(guī)劃庫的規(guī)劃識別模型

面向?qū)ο蟮某绦蛟O(shè)計技術(shù)(稱O-O技術(shù))作為一種新的程序設(shè)計技術(shù)已得到廣泛的重視?！邦悺焙汀皩ο蟆笔敲嫦?qū)ο蠓椒ǖ木A。本文中我們基于面向?qū)ο蟮某绦蛟O(shè)計思想把知識規(guī)則的結(jié)構(gòu)和模糊推理方法定義成規(guī)則類,把具體的規(guī)則定義成規(guī)則類的實體 (即對象),用這些規(guī)則實體構(gòu)建動態(tài)鏈表從而組成動態(tài)規(guī)劃庫,推理的過程由規(guī)劃庫中各規(guī)則實體提供的方法完成。

根據(jù)上述思想建立的模型如圖 1所示。

圖 1 基于動態(tài)規(guī)劃庫的規(guī)劃識別模型

5 加權(quán)模糊規(guī)劃識別算法

每次識別過程中規(guī)劃器都依次調(diào)用規(guī)劃鏈中每個規(guī)劃對象的識別函數(shù),直至識別結(jié)束,輸出結(jié)論。

在識別算法包括以下步驟：

(1)規(guī)劃器首先讀入已知事件,到基本事件庫中進行模糊匹配,調(diào)用相應(yīng)隸屬度函數(shù)求其事件真度,即在基本事件鏈中找相似事件。若求得的事件真度為 0,意味著沒有相似事件,則將這一前提事件由ADD函數(shù)將其追加到基本事件庫。否則提取其在基本事件庫中的事件號和事件真度生成基本事件鏈。

(2)在基本事件鏈中讀取一個基本事件,從規(guī)劃庫中找到包含這一基本事件的所有規(guī)劃,此時基本事件就是這些規(guī)劃的前提事件,提取該前提事件在這些規(guī)劃中的權(quán)值和對應(yīng)的規(guī)劃號,動態(tài)規(guī)劃庫里。

(3)處理下一前提事件,重復(fù)步驟 1、2直到所有前提事件處理完畢。比較這些前提事件對象,將規(guī)劃號相同的前提事件組成新的鏈表。

(4)調(diào)用求規(guī)劃可信度函數(shù),根據(jù)各前提事件的事件真度和權(quán)值計算出該規(guī)劃的可信度,如大于等于事先給定的閾值,則確認該規(guī)劃,否則換一下條規(guī)劃重新進行判斷。(實驗初期我們把閾值暫時定位 0.35)

(5)在每一條規(guī)劃被確認后,輸出該規(guī)劃(為規(guī)劃庫中的完整規(guī)劃,即包含尚未出現(xiàn)的事件)。并將已輸出的前提事件對象從前提事件鏈中刪除。同時,要從規(guī)劃庫中提取該規(guī)劃目標事件的獨立標記,如為 Y,則結(jié)束識別。如為N,則要將該目標作為前提事件再次進行識別,即把目標事件連接到已處理完的前提事件后面返回步驟 1,此時將該規(guī)劃的可信度作為目標事件在上層規(guī)劃中前提事件的事件真度。

6 結(jié) 語

傳統(tǒng)的規(guī)劃識別的方法是根據(jù)觀察動作建立規(guī)劃庫,根據(jù)一定的搜索和匹配機制來獲取規(guī)劃解。本文采用給組成規(guī)劃的各動作按其對該規(guī)劃出現(xiàn)的影響程度確定一個權(quán)值,使規(guī)劃識別器能夠快速準確地識別出規(guī)劃。在規(guī)劃庫搜索和匹配機制中應(yīng)用模糊處理,使得模糊理論在規(guī)劃識別中得以運用,所以得到的結(jié)果更加符合客觀事實。

[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] 姜云飛,馬寧.一種基于規(guī)劃知識圖的規(guī)劃識別算法[J].軟件學(xué)報,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-),女,吉林通化人,講師,主要從事智能規(guī)劃與規(guī)劃識別方面研究。