徐本勝　王　潔

(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院　北京 100124)

?

智能空間中的沖突問題研究

徐本勝王潔

(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院北京 100124)

摘要智能空間和回答集程序的整合解決了智能空間中固定優(yōu)先關(guān)系下的資源沖突問題。然而，智能空間處在一個上下文敏感的、動態(tài)的環(huán)境中，信息更新以及環(huán)境變化都會導(dǎo)致資源分配的順序重新發(fā)生變化，從而產(chǎn)生新的沖突問題。針對該問題，基于回答集程序提出一種動態(tài)優(yōu)先的方法。首先，引入缺省規(guī)則并利用缺省決策理論動態(tài)決策智能空間中的優(yōu)先關(guān)系；然后，使用回答集程序表達(dá)空間中的動態(tài)優(yōu)先關(guān)系；最后，求解回答集程序得到?jīng)_突問題的解。實(shí)驗(yàn)結(jié)果表明，該方法可以動態(tài)決策空間中的優(yōu)先關(guān)系，有效解決空間中的沖突問題，對空間中的資源實(shí)現(xiàn)合理分配。

關(guān)鍵詞回答集程序智能空間動態(tài)優(yōu)先缺省規(guī)則

0引言

智能空間是一個嵌入了多模態(tài)傳感器、計(jì)算和信息設(shè)備的工作空間，可使用戶便捷地訪問空間中的信息并獲取計(jì)算機(jī)的服務(wù)，幫助用戶實(shí)現(xiàn)高效工作[1]。為了方便空間中的設(shè)備和服務(wù)之間進(jìn)行信息和資源共享，智能空間最初使用語義網(wǎng)的方法[2]。

語義網(wǎng)采用RDF(資源描述框架)表達(dá)信息并且與網(wǎng)頁的結(jié)構(gòu)息息相關(guān)，然而語義網(wǎng)的推理能力和隱私性都不夠好。因此，相關(guān)研究學(xué)者設(shè)計(jì)開發(fā)了Smart-M3平臺以便更好地實(shí)現(xiàn)智能空間。

Smart-M3是智能空間中的一個的交互操作平臺，空間中的所有信息和服務(wù)都可以在設(shè)備之間進(jìn)行共享和存取。它包含兩個部分，分別是SIB(Semantic Information Broke)和KP(Knowledge Processor)[3]。其中，SIB以RDF三元組的形式對空間中的信息進(jìn)行存儲；知識處理操作則由KP完成，通過刪除、插入、查詢、更新等操作來處理存儲在SIB中的信息[4]。智能空間訪問協(xié)議SSAP(Smart Space Access Protocol)則將SIB和KP進(jìn)行了連接。

2010年Luukkala.V等人在智能空間中引入了回答集程序設(shè)計(jì)ASP[5]，并將ASP求解器Smodels和智能空間中的Smart-M3平臺進(jìn)行了整合[6]并在此基礎(chǔ)上使用固定優(yōu)先權(quán)的方法解決了空間中的資源分配和沖突問題。然而，現(xiàn)實(shí)生活中的優(yōu)先權(quán)并不是完全固定的，它應(yīng)該隨著環(huán)境和信息變化而改變。

因此，建立一種隨環(huán)境和信息更新而能夠動態(tài)改變空間中優(yōu)先關(guān)系的方法是很有必要的。為了解決這個問題，引入缺省規(guī)則[7]的方法并基于缺省決策理論[8]動態(tài)決策空間中的優(yōu)先關(guān)系；然后，使用回答集程序表達(dá)空間中的這種動態(tài)優(yōu)先關(guān)系，最后，求解回答集程序即可得到?jīng)_突問題的解。

1ASP與智能空間的整合

回答集程序設(shè)計(jì)ASP的理論基礎(chǔ)是Gelfond和Lifschitz于1988年提出的一般邏輯程序的穩(wěn)定模型語義。1999年ASP作為一種程序設(shè)計(jì)框架被提出，其語法上類似傳統(tǒng)邏輯編程，語義上是一種非單調(diào)邏輯的描述性語義，具有豐富的知識表達(dá)和推理能力。ASP解決問題的基本思想是：通過一個非單調(diào)邏輯程序描述待求解的問題，根據(jù)描述設(shè)計(jì)一個帶有回答集語義的回答集程序，計(jì)算回答集程序的回答集就是待求解問題的解決方案。

智能空間中的設(shè)備和服務(wù)信息是以RDF三元組的形式進(jìn)行存儲的，而ASP是一種基于規(guī)則的方法，因此為了整合ASP與智能空間就需要將RDF轉(zhuǎn)化為規(guī)則的形式。轉(zhuǎn)換的過程是將RDF的三元組轉(zhuǎn)化為二元事實(shí)predicate(subject,object)。比如，RDF三元組將會轉(zhuǎn)化為二元事實(shí)(John,wp1:Person)。這樣的形式就可以通過ASP的推理機(jī)Smodels系統(tǒng)的lparse語法檢查并利用smodel進(jìn)行程序的求解。

ASP與智能空間的整合主要是基于以下過程：通過ssls將回答集程序的推理工具Smodels與Smart-M3平臺相連接。其中，ssls是一個能夠訪問Smart-M3操作(刪除、插入、查詢、更新等)的命令行工具并且可以把存儲在SIB中的信息提取出來。利用RDF三元組與二元事實(shí)的轉(zhuǎn)換性可以把存儲在SIB中的每一條信息都轉(zhuǎn)換成相對應(yīng)的一條規(guī)則，從而得到一個回答集程序。利用Smodels求解回答集程序得到的結(jié)果則可以通過KP執(zhí)行插入、更新、刪除等操作，以實(shí)現(xiàn)SIB中信息的更新[10]。

ASP具有很強(qiáng)的知識表達(dá)和推理能力并支持資源分配和沖突消解，當(dāng)有多個可能解的情況下可以利用偏好和最優(yōu)化技術(shù)篩選最合適的解。2010年Luukkala.V等人通過Smart-M3與ASP的整合增強(qiáng)了智能空間中的推理能力，使用固定優(yōu)先權(quán)的方法在一定程度上解決了空間中的資源分配和沖突問題。比如，在汽車這個智能空間中，設(shè)定交通信息的優(yōu)先級高于音樂。當(dāng)交通信息和音樂同時申請使用揚(yáng)聲器時，揚(yáng)聲器在任何環(huán)境下都會接受交通信息的申請，并優(yōu)先分配給交通信息。

但是，智能空間是一個上下文敏感的，動態(tài)的環(huán)境[11,12]，信息更新和環(huán)境變化都會導(dǎo)致資源分配的順序重新發(fā)生改變，引起新的沖突問題。比如，汽車中有一個正處于睡眠狀態(tài)的嬰兒，當(dāng)收到一條最新的路況交通信息時，為了不打擾嬰兒的睡眠，我們期望揚(yáng)聲器能夠播放緩慢柔和的音樂而不是路況交通信息。采用Luukkala.V等人提出的固定優(yōu)先級的方法無法解決這種問題。因此，我們提出另一種解決方法，即動態(tài)優(yōu)先的方法。

2基于ASP解決智能空間中的沖突問題

由于ASP具有豐富的知識表達(dá)和推理能力，ASP與智能空間的整合促進(jìn)了智能空間的相關(guān)研究工作。2010年張璟璟等人基于Jini技術(shù)并以智能空間中的漫游打印為應(yīng)用背景，設(shè)計(jì)了一種有效的智能空間的資源管理解決方案。2012年Janhunen.T等人基于元程序的方法，允許智能空間中的設(shè)備發(fā)布它的行為規(guī)則，并利用元程序的具體化表達(dá)將規(guī)則信息存儲到SIB中，從而實(shí)現(xiàn)了對規(guī)則信息的共享和存儲，增強(qiáng)了智能空間中設(shè)備之間的交互能力。2012年趙麗麗等人基于加權(quán)邏輯程序來表達(dá)智能空間中確定性的信息以增強(qiáng)確定性信息的表達(dá)和推理，但是該方法不支持對空間中不確定信息的表達(dá)和推理。2014年劉志勇等人通過對智能空間中資源管理的研究構(gòu)建了一個智能空間資源管理系統(tǒng)并對空間中的資源調(diào)度算法進(jìn)行了研究。

本文為了處理智能空間中信息更新和環(huán)境變化后的資源沖突問題，基于ASP提出一種動態(tài)優(yōu)先的方法，首先引入缺省規(guī)則并根據(jù)環(huán)境和信息變化動態(tài)決策優(yōu)先關(guān)系，并用ASP表達(dá)這種動態(tài)優(yōu)先關(guān)系，最后求解該回答集程序即得到?jīng)_突問題的解。

2.1智能空間中的動態(tài)優(yōu)先關(guān)系表達(dá)

智能空間中存在很多的設(shè)備服務(wù)信息，每個設(shè)備實(shí)例稱為一個capability，每個服務(wù)實(shí)例稱為一個activity。在activity實(shí)例和capability實(shí)例之間有一個used關(guān)系，表示activity申請使用這個capability實(shí)例。當(dāng)capability實(shí)例接受該請求，就會在兩個實(shí)例之間建立一個committed的關(guān)系。此外，兩個activity實(shí)例之間還有一個優(yōu)先關(guān)系priority，比如priority(ActGood,ActBad)表示ActGood和ActBad之間的優(yōu)先關(guān)系并且ActGood的優(yōu)先級大于ActBad的優(yōu)先級。對于to_commit來說，就是要選擇一個capability-activity對集，并且滿足以下三條原則。

(1) 空間中的所有資源在尚未達(dá)到它的最大使用量之前都可以被一個新的activity實(shí)例申請使用。

(2) 當(dāng)多個activity實(shí)例申請使用同一個capability實(shí)例時具有更高優(yōu)先權(quán)的activity實(shí)例應(yīng)該給予優(yōu)先分配。

(3) 如果沒有更高優(yōu)先權(quán)的activity實(shí)例申請使用設(shè)備，那么已分配的activity實(shí)例應(yīng)保持對此設(shè)備的使用關(guān)系。

基于以上三條原則可以使用ASP的方法解決固定優(yōu)先關(guān)系下的資源沖突問題，因此需要用規(guī)則的形式對以上三個原則進(jìn)行描述。下面的三條約束規(guī)則(1)、(2)、(3)分別對應(yīng)上面的三條原則。

←{to_commit(Cap,Act):used(Cap,Act)}M-1,

used(Cap,Act1),

not to_commit(Cap,Act1),

max_users(Cap,M)

(1)

←to_commit(Cap,ActBad),

used(Cap,ActBad),

not to_commit(Cap,ActGood),

used(Cap,ActGood),

priority(ActGood,ActBad)

(2)

←to_commit(Cap,ActBad),

not committed(Cap,ActBad),

used(Cap,ActBad),

committed(Cap,ActGood),

not to_commit(Cap,ActGood)

used(Cap,ActGood),

priority(ActGood,ActBad)

(3)

但是，智能空間是一個動態(tài)的上下文敏感的環(huán)境，空間中的優(yōu)先關(guān)系不可能是完全固定的，當(dāng)信息發(fā)生更新后，使用固定的優(yōu)先方法會引起新的沖突問題，因此必須動態(tài)表示空間中的優(yōu)先關(guān)系。為了表達(dá)空間中的動態(tài)優(yōu)先關(guān)系引入缺省規(guī)則。缺省規(guī)則的一般形式為:

e→Aa

其中，e是一階公式集合，表示已知的信息或知識，A是原子集合，表示所有可選擇的決策行為，a是原子，并且a∈A。缺省規(guī)則e→Aa的直觀含義是：在已知信息e的基礎(chǔ)上，對于A中的所有決策，a是最優(yōu)的決策結(jié)果。例如，對于缺省規(guī)則：“如果天氣預(yù)報今天會下雨，那么今天出門要帶傘”，可以如下表示：

date(today)∧weather(rain)→Acarry_umbrella

其中A={carry_umbrella,carry_nothing}。

為了對當(dāng)前環(huán)境和信息下的不同activity實(shí)例之間的優(yōu)先關(guān)系進(jìn)行動態(tài)決策，引入了缺省決策理論。具體表示如下:

其中：

其中，ε(a,e)是a在已知信息e下的期望效用，w是選定的封閉世界，μ(a,w)表示行為a在w下的效用，P(w|e)是在已知信息e下w成立的條件概率。缺省決策理論的直觀含義是，在已知信息e的基礎(chǔ)上，A中期望效用最大的行為是最優(yōu)的決策結(jié)果。

根據(jù)上述的缺省決策理論有如下原則：對于申請使用同一個設(shè)備的多個activity，在當(dāng)前環(huán)境和信息下具有更大期望效用的activity應(yīng)該被賦予更大的優(yōu)先級。基于缺省規(guī)則可以進(jìn)行如下表示：

activity(ActGood)∧activity(ActBad)∧

used(ActBad,Cap)∧used(ActBad,Cap)∧

capability(Cap)→Apriority(ActGood,ActBad)

其中：

A={priority(ActGood,ActBad),

priority(ActBad,ActGood)}

此外，我們定義謂詞expect_utility(Act,X)表示Act的期望效用為X，因此，可以把上面的缺省規(guī)則改寫為回答集程序的形式，記為規(guī)則(4)。

priority(ActGood,ActBad)←capability(Cap),

used(ActGood,Cap),used(ActBad,Cap),

activity(ActGood),activity(ActBad),

expect_utility(ActGood,X),

expect_utility(ActBad,Y),X>Y

(4)

利用規(guī)則(4)，我們就可以根據(jù)智能空間中的信息和環(huán)境的變化，依據(jù)缺省決策理論，通過計(jì)算當(dāng)前環(huán)境下的activity實(shí)例的期望效用值來動態(tài)決策activity實(shí)例間的優(yōu)先關(guān)系。

因此，基于(1)、(2)、(3)、(4)四條規(guī)則就可以動態(tài)決策空間中的優(yōu)先關(guān)系以解決智能空間中的資源沖突問題。

2.2實(shí)例

例2：在汽車這個智能空間中存在鍵盤、揚(yáng)聲器等設(shè)備。揚(yáng)聲器可以用來播放路況交通信息和音樂?，F(xiàn)在，汽車中有一個處于清醒狀態(tài)的嬰兒，揚(yáng)聲器正在播放一些緩慢柔和的音樂，當(dāng)收到一條最新的路況交通信息時，用戶希望能接收該條信息，因此期望揚(yáng)聲器能優(yōu)先播放路況交通信息。一段時間后，嬰兒慢慢進(jìn)入睡眠狀態(tài)，當(dāng)又收到一條最新的路況交通信息時，為了不打擾到嬰兒的睡眠，用戶期望揚(yáng)聲器能夠繼續(xù)播放緩慢柔和的音樂而不是路況信息。在此種場景下，需要動態(tài)決策M(jìn)essage和Music的優(yōu)先關(guān)系。因此，我們采用2.1節(jié)中的方法來解決上述問題。

首先對于該實(shí)例，智能空間中存儲于SIB中的信息如下：

″rdf:type″(Loudspeaker,″dcs:capability″),

″rdf:type″(Message,″wp1:activity″),

″rdf:type″(Music,″wp1:activity″),

″wp1:used″(Loudspeaker,Message),

″wp1:used″(Loudspeaker,Music)

當(dāng)嬰兒處于清醒狀態(tài)時，由當(dāng)前環(huán)境下的效用和概率信息可以得到Message的期望效用大于Music的期望效用。因此由2.1節(jié)中的規(guī)則(4)可以推理得到priority(Message,Musuc)即Message的優(yōu)先級高于Music。將SIB中的RDF三元組信息轉(zhuǎn)化成規(guī)則的形式如下：

(5) activity(Music)←

(6) activity(Message)←

(7) capability(Loudspeaker)←

(8) used(Loudspeaker,Music)←

(9) used(Loudspeaker,Message)←

結(jié)合2.1節(jié)中的規(guī)則(1)-規(guī)則(3)可以得到一個回答集程序P，通過回答集推理機(jī)Smodels求解程序P，得到回答集A并且to_commit(Loudspeaker,Message)∈A即根據(jù)當(dāng)前的信息和智能空間所處的環(huán)境得到的結(jié)果是將揚(yáng)聲器分配給Message。

一段時間后，嬰兒慢慢進(jìn)入睡眠狀態(tài)。根據(jù)此時環(huán)境下的效用和概率信息可以得到Music期望效用大于Message的期望效用。由2.1節(jié)中的規(guī)則(4)可以推理得到priority(Music,Message)即當(dāng)前環(huán)境下Music的優(yōu)先級高于Message。更新程序P，求解P得到新的回答集B并且to_commit(Loudspeaker,Music)∈B即根據(jù)當(dāng)前的信息和智能空間所處的環(huán)境得到的結(jié)果是揚(yáng)聲器分配給Music。

由上可以看出，通過2.1節(jié)中的方法可以根據(jù)環(huán)境和信息的變化動態(tài)決策空間中存在的activity實(shí)例間的優(yōu)先關(guān)系，當(dāng)嬰兒清醒時Message的優(yōu)先權(quán)高于Music，當(dāng)嬰兒熟睡時，Music的優(yōu)先權(quán)高于Message。而Luukkala.V等人提出的固定優(yōu)先方法是固定activity實(shí)例間的優(yōu)先關(guān)系，比如固定Message的優(yōu)先權(quán)始終高于Music，那么無論信息和環(huán)境發(fā)生任何更新和變化，揚(yáng)聲器都會優(yōu)先播放路況交通信息Message。

固定優(yōu)先方法只能處理固定優(yōu)先關(guān)系下的資源沖突問題，并且資源一旦分配就不會改變。但是智能空間是一個動態(tài)的、上下文敏感的環(huán)境，空間中的優(yōu)先關(guān)系和資源分配順序不可能是固定不變的。當(dāng)智能空間中的信息和環(huán)境發(fā)生變化時，固定優(yōu)先方法已不能適應(yīng)空間的動態(tài)變化。與之相比，我們提出的動態(tài)優(yōu)先方法可以根據(jù)信息和環(huán)境變化動態(tài)決策空間中的優(yōu)先關(guān)系，改變空間中的資源分配順序，適應(yīng)智能空間的動態(tài)變化，解決信息更新后的資源沖突問題，從而實(shí)現(xiàn)對資源的合理分配。

3結(jié)語

智能空間中的資源設(shè)備眾多，固定空間中的優(yōu)先關(guān)系可以在一定程度上解決資源分配時的沖突問題。但是，這無法解決因信息更新和環(huán)境變化而產(chǎn)生的沖突問題。本文基于缺省規(guī)則和缺省決策理論，提出了一種動態(tài)優(yōu)先的方法，根據(jù)智能空間中信息和環(huán)境的變化動態(tài)決策空間中的優(yōu)先關(guān)系，解決了空間中的這種沖突問題，實(shí)現(xiàn)了資源的合理分配。

參考文獻(xiàn)

[1] Borkar S.Technology challenges and opportunities for ubiquitous computing[C].Solid State Circuits Conference,IEEE,2012:125-128.

[2] Selvarajah K,Zhao R,Speirs N.Building smart space applications with pervasive computing in embedded systems[J].Journal on Computing,2014,1(4):22-24.

[3] Honkola J,Laine H,Brown R.Smart-M3 information sharing platform[C].ISCC,2010:1041-1046.

[4] Kaustell A,Saleemi M,Rosqvist T,et al.Framework for smart space application development[C]//Proceedings of the International Workshop on Semantic Interoperability,2011.

[5] Luukkala V,Honkola J.Integration of an answer set engine to smart-m3[M].Smart Spaces and Next Generation Wired/Wireless Networking.Springer Berlin Heidelberg,2010:92-101.

[7] Wang J,Ju S E,Liu C N.Agent-oriented probabilistic logic programming[J].Journal of Computer Science and Technology,2006,21(3):412-417.

[8] Horvitz E J.Reasoning about beliefs and actions under computational resource constraints[J].arXiv preprint arXiv,2013,1(3):1304-1325.

[9] Schaub T.Answer set programming[C]//Proceedings of the 12thConference on Formal Methods in Computer-Aided Design.,2012:2-5.

[10] Janhunen T,Luukkala V.Meta programming with answer sets for smart spaces[M].Springer Berlin Heidelberg,2012.

[11] Honkola J,Laine H,Brown R,et al.Cross-domain interoperability:A case study[M].Smart spaces and next generation Wired/Wireless networking.Springer Berlin Heidelberg,2009:22-31.

[12] Aziz R A,Janhunen T,Luukkala V.Distributed deadlock handling for resource allocation in smart spaces[M].Smart Spaces and Next Generation Wired/Wireless Networking.Springer Berlin Heidelberg,2011:87-98.

收稿日期：2015-02-11。徐本勝，碩士生，主研領(lǐng)域：回答集程序設(shè)計(jì)，不確定推理。王潔，副教授。

中圖分類號TP301

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.007

STUDY ON CONFLICT PROBLEM IN SMART SPACE

Xu BenshengWang Jie

(CollegeofComputerScience,BeijingUniversityofTechnology,Beijing100124,China)

AbstractThe integration of answer set programming (ASP) and smart space can solve resource conflict problems in smart space on the condition of fixed priority relation.However,smart space is in a context sensitive and dynamic environment,the updating of information and changing of environment would all cause the alternation in order of resource allocation,and further lead to new resource conflicts.To solve this problem,in this paper we put forward a dynamic priority method based on answer set programming.First,we introduce default rule and use default decision making theory to dynamically decide the priority relation in smart space.Secondly,we employ answer set programming to represent the dynamic priority relations in the space.Finally,we calculate the answer set programming to get the solution of conflict problem.Experimental result shows that this method is able to dynamically decide the priority relation in the space and effectively overcomes the conflict problems in space,and achieves reasonable allocation of resources in the space as well.

KeywordsASPSmart spaceDynamic priorityDefault rule