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

徐本勝　王　潔

(北京工業大學計算機學院　北京 100124)

?

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

徐本勝王潔

(北京工業大學計算機學院北京 100124)

摘要智能空間和回答集程序的整合解決了智能空間中固定優先關系下的資源沖突問題。然而，智能空間處在一個上下文敏感的、動態的環境中，信息更新以及環境變化都會導致資源分配的順序重新發生變化，從而產生新的沖突問題。針對該問題，基于回答集程序提出一種動態優先的方法。首先，引入缺省規則并利用缺省決策理論動態決策智能空間中的優先關系；然后，使用回答集程序表達空間中的動態優先關系；最后，求解回答集程序得到沖突問題的解。實驗結果表明，該方法可以動態決策空間中的優先關系，有效解決空間中的沖突問題，對空間中的資源實現合理分配。

關鍵詞回答集程序智能空間動態優先缺省規則

0引言

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

語義網采用RDF(資源描述框架)表達信息并且與網頁的結構息息相關，然而語義網的推理能力和隱私性都不夠好。因此，相關研究學者設計開發了Smart-M3平臺以便更好地實現智能空間。

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

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

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

1ASP與智能空間的整合

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

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

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

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

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

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

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

本文為了處理智能空間中信息更新和環境變化后的資源沖突問題，基于ASP提出一種動態優先的方法，首先引入缺省規則并根據環境和信息變化動態決策優先關系，并用ASP表達這種動態優先關系，最后求解該回答集程序即得到沖突問題的解。

2.1智能空間中的動態優先關系表達

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

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

(2) 當多個activity實例申請使用同一個capability實例時具有更高優先權的activity實例應該給予優先分配。

(3) 如果沒有更高優先權的activity實例申請使用設備，那么已分配的activity實例應保持對此設備的使用關系。

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

←{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)

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

e→Aa

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

date(today)∧weather(rain)→Acarry_umbrella

其中A={carry_umbrella,carry_nothing}。

為了對當前環境和信息下的不同activity實例之間的優先關系進行動態決策，引入了缺省決策理論。具體表示如下:

其中：

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

根據上述的缺省決策理論有如下原則：對于申請使用同一個設備的多個activity，在當前環境和信息下具有更大期望效用的activity應該被賦予更大的優先級。基于缺省規則可以進行如下表示：

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，因此，可以把上面的缺省規則改寫為回答集程序的形式，記為規則(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)

利用規則(4)，我們就可以根據智能空間中的信息和環境的變化，依據缺省決策理論，通過計算當前環境下的activity實例的期望效用值來動態決策activity實例間的優先關系。

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

2.2實例

例2：在汽車這個智能空間中存在鍵盤、揚聲器等設備。揚聲器可以用來播放路況交通信息和音樂。現在，汽車中有一個處于清醒狀態的嬰兒，揚聲器正在播放一些緩慢柔和的音樂，當收到一條最新的路況交通信息時，用戶希望能接收該條信息，因此期望揚聲器能優先播放路況交通信息。一段時間后，嬰兒慢慢進入睡眠狀態，當又收到一條最新的路況交通信息時，為了不打擾到嬰兒的睡眠，用戶期望揚聲器能夠繼續播放緩慢柔和的音樂而不是路況信息。在此種場景下，需要動態決策Message和Music的優先關系。因此，我們采用2.1節中的方法來解決上述問題。

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

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

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

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

″wp1:used″(Loudspeaker,Message),

″wp1:used″(Loudspeaker,Music)

當嬰兒處于清醒狀態時，由當前環境下的效用和概率信息可以得到Message的期望效用大于Music的期望效用。因此由2.1節中的規則(4)可以推理得到priority(Message,Musuc)即Message的優先級高于Music。將SIB中的RDF三元組信息轉化成規則的形式如下：

(5) activity(Music)←

(6) activity(Message)←

(7) capability(Loudspeaker)←

(8) used(Loudspeaker,Music)←

(9) used(Loudspeaker,Message)←

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

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

由上可以看出，通過2.1節中的方法可以根據環境和信息的變化動態決策空間中存在的activity實例間的優先關系，當嬰兒清醒時Message的優先權高于Music，當嬰兒熟睡時，Music的優先權高于Message。而Luukkala.V等人提出的固定優先方法是固定activity實例間的優先關系，比如固定Message的優先權始終高于Music，那么無論信息和環境發生任何更新和變化，揚聲器都會優先播放路況交通信息Message。

固定優先方法只能處理固定優先關系下的資源沖突問題，并且資源一旦分配就不會改變。但是智能空間是一個動態的、上下文敏感的環境，空間中的優先關系和資源分配順序不可能是固定不變的。當智能空間中的信息和環境發生變化時，固定優先方法已不能適應空間的動態變化。與之相比，我們提出的動態優先方法可以根據信息和環境變化動態決策空間中的優先關系，改變空間中的資源分配順序，適應智能空間的動態變化，解決信息更新后的資源沖突問題，從而實現對資源的合理分配。

3結語

智能空間中的資源設備眾多，固定空間中的優先關系可以在一定程度上解決資源分配時的沖突問題。但是，這無法解決因信息更新和環境變化而產生的沖突問題。本文基于缺省規則和缺省決策理論，提出了一種動態優先的方法，根據智能空間中信息和環境的變化動態決策空間中的優先關系，解決了空間中的這種沖突問題，實現了資源的合理分配。

參考文獻

[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。徐本勝，碩士生，主研領域：回答集程序設計，不確定推理。王潔，副教授。

中圖分類號TP301

文獻標識碼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