不確定規(guī)劃中可達關系的快速求解算法

龍 鳳,文中華,唐 杰,王進宗

(湘潭大學信息工程學院,湖南湘潭411105)

不確定規(guī)劃中可達關系的快速求解算法

龍 鳳,文中華,唐 杰,王進宗

(湘潭大學信息工程學院,湖南湘潭411105)

在不確定規(guī)劃領域中,通常需要在同一個不確定狀態(tài)轉移系統中解決多個規(guī)劃問題,如果能得到不確定規(guī)劃中狀態(tài)之間的可達關系即可方便求解該規(guī)劃問題,然而現有矩陣乘法求解可達關系時存在算法復雜度高的問題。為此,設計一種快速求解不確定規(guī)劃中狀態(tài)之間可達關系的算法,將確定動作和不確定動作區(qū)分處理,先求解所有確定動作的可達關系,再采用鏈表和隊列求解不確定動作的可達關系。實驗結果表明,與矩陣乘法相比,該算法能得到更全面的可達關系,且求解效率更高。

不確定規(guī)劃;可達關系;智能規(guī)劃;模型檢測;不確定性;不確定狀態(tài)轉移系統

1 概述

在現實世界中,存在許多不確定性問題。相對于確定規(guī)劃而言,不確定規(guī)劃[1-2]能夠更好地解決這些問題。這是近年來智能規(guī)劃的一個熱點研究領域。模型檢測是智能規(guī)劃中處理不確定規(guī)劃問題的一個重要算法。基于模型檢測[3-4]的不確定規(guī)劃也成為研究熱點,并取得了一些重要的成果,如:求解強、弱及強循環(huán)規(guī)劃解[5-6]的提出;對不確定狀態(tài)轉移系統進行分層[7],刪除部分無用狀態(tài)序偶對,減小問題規(guī)模;不確定規(guī)劃中狀態(tài)之間的可達關系研究[8-9];基于模型檢測的不確定規(guī)劃中的狀態(tài)可達性研究[10];循環(huán)或非循環(huán)可達關系[11-12]的求解;正向搜索規(guī)劃解[13];觀察信息約簡[14-15]等。

在一個不確定狀態(tài)轉移系統中,求解規(guī)劃問題時需要反復搜索動作來尋找目標狀態(tài)。由于該搜索過程是沒有方向的,如果能夠得到不確定規(guī)劃中狀態(tài)之間的可達關系,則可以更加快速地求解規(guī)劃問題,減少冗余計算,建立系統引導信息。在文獻[8]中,給出了求解不確定規(guī)劃中的狀態(tài)之間的可達關系的算法,該算法將不確定狀態(tài)轉移系統轉換為鄰接矩陣,通過鄰接矩陣的加和乘運算獲得系統的可達矩陣,利用可達矩陣得到可達關系。但是,該算法在求解過程中具有一定的局限性,不能保證高效地得到可達關系。所以,本文提出一種快速求解不確定規(guī)劃中狀態(tài)間可達關系的算法,該算法對不確定狀態(tài)系統中的一些特殊的不確定動作進行了處理,從而使得該算法可以更加高效、全面地得到不確定狀態(tài)系統的可達關系。

2 相關定義

定義1一個規(guī)劃領域是一個不確定的狀態(tài)轉移系統Σ=(S,A,γ),其中:

(1)S是一個有限狀態(tài)集;

(2)A是一個有限動作集;

(3)γ:S(A→2S是狀態(tài)轉移函數。

其中,利用γ刻畫不確定性:在s下執(zhí)行動作a可能得到的結果狀態(tài)集合就是γ(s,a)。若γ(s,a)非空,則稱動作a在狀態(tài)s下是可執(zhí)行的。在狀態(tài)s下可執(zhí)行動作的集合記為A(s)={a:?s∈γ(s,a)},并稱(s,a)為狀態(tài)動作序偶。

定義2一個規(guī)劃問題是由3個變量組成的三元組P=(Σ,I,G),其中:

(1)Σ=(S,A,γ)是不確定狀態(tài)轉移系統;

(2)I?S是初始狀態(tài)集合;

(3)G?S是目標狀態(tài)集合。

定義3在一個不確定狀態(tài)轉移系統中,從狀態(tài)si開始,執(zhí)行 γ(si+1,ai+1),γ(si+2,ai+2),…,γ(sn,an)后,可能存在一條路徑到達狀態(tài)sx,那么,稱si到sx為不確定可達。對于任意sx都必有sx∈γ(sj,aj) (1＜x＜n,0＜j＜i)。

定義4在一個不確定狀態(tài)轉移系統中,從狀態(tài)si開始,執(zhí)行 γ(si+1,ai+1),γ(si+2,ai+2),…,γ(sn,an)后,不存在任何路徑能夠到達狀態(tài)sx,那么,稱si到sx為確定不可達。其中,對于任意sx都有sx∈γ(sj,aj)(1＜x＜n,0＜j＜i)。

定義5在一個不確定狀態(tài)轉移系統中,從狀態(tài)si開始,執(zhí)行 γ(si+1,ai+1),γ(si+2,ai+2),…,γ(sn,an)后,任意一條路徑都能到達狀態(tài)sx,那么,稱si到sx為確定可達。其中,對于任意sx都有sx∈γ(sj,aj)(1＜x＜n,0＜j＜i)。

定義6在不確定狀態(tài)轉移系統中,2個狀態(tài)之間的可達關系用函數G(si,sj)來表示,函數G(si,sj)定義如下:

(1)G(si,sj)=0:si到sj為確定不可達;

(2)G(si,sj)=1:si到sj為確定可達;

(3)G(si,sj)=2:si到sj為不確定可達。

3 可達關系的求解算法

3.1 算法原理

文獻[8]利用矩陣乘的算法來求解可達關系。該算法先將不確定狀態(tài)轉移系統轉換為鄰接矩陣,然后通過鄰接矩陣的加和乘運算獲得可達矩陣,時間復雜度比較高。

本文提出的可達關系求解算法是將不確定狀態(tài)轉移系統中確定動作和不確定動作進行區(qū)別處理。這樣可以避免一些重復計算,從而提高求解效率。算法主要分為兩部分:(1)處理確定動作,確定動作的起始狀態(tài)到終止狀態(tài)是確定可達的,只需進行簡單處理。(2)處理不確定動作,首先處理確定可達的情況,若狀態(tài)s是不確定動作a的起始狀態(tài),且不確定動作a的所有終止狀態(tài)都能確定可達狀態(tài)s′,則狀態(tài)s是確定可達狀態(tài)s′,然后處理不確定到達的情況,顯然,去除某些不確定動作的起始狀態(tài)到部分終止狀態(tài)確定可達以外,余下的不確定動作的起始狀態(tài)到終止狀態(tài)集都是不確定可達。同時,算法保證了確定可達具有傳遞性,即狀態(tài)a確定到達狀態(tài)b,b確定可達狀態(tài)c,那么狀態(tài)a必定確定可達狀態(tài)c。

3.2 算法分析

本文算法主要分為兩部分:(1)處理確定動作,求解確定動作的可達關系;(2)處理不確定動作,采用鏈表和隊列求解不確定動作的可達關系。設Σ=(S,A,γ)是一個不確定的狀態(tài)轉移系統,其中有n個狀態(tài)。

處理確定動作的算法中動作起始狀態(tài)為u,終止狀態(tài)個數為num,終止狀態(tài)為v。數組graph[i][j]表示狀態(tài)i和狀態(tài)j的可達關系,即graph[i][j]為0代表不可達,graph[i][j]為1代表確定可達,graph[i][j]為2代表不確定可達。

處理確定動作的算法具體如下:

狀態(tài)到狀態(tài)本身是確定可達的,所以,第2行、第3行表示狀態(tài)到自己本身是確定可達的;第5行～第7行表示確定動作的起始狀態(tài)到終止狀態(tài)是確定可達;第8行中mulm代表第幾個不確定動作,即不確定動作的ID號;第 10行的函數solveReach求任意2個點是否確定可達,即執(zhí)行這個函數后,可以保證graph具有傳遞性。

函數solveReach處理的具體流程如下:

函數solveReach的代碼中數組graph[i][j]表示狀態(tài)i和狀態(tài)j的可達關系,即graph[i][j]為0代表不可達,graph[i][j]為1代表確定可達,graph[i][j]為2代表不確定可達。第4行～第8行是確保確定可達具有傳遞性,即graph[i][k]= =1且graph[k][j]==1,那么就有graph[i][j]==1。

處理不確定動作時,分為確定可達和不確定可達兩部分進行處理。其中,mulAcation[i][0]代表第i個不確定動作的初始狀態(tài)數目(為1)和終止狀態(tài)數目之和,這里假設為num+1,mulAcation[i][1]代表第i個不確定動作的初始狀態(tài)的編號,mulAcation[i][2,3,…,num+1]代表第i個不確定動作的所有終止狀態(tài)的編號。隊列actionQue用來保存所有不確定動作的ID號。

處理不確定動作中確定可達的算法具體如下:

在處理確定可達的算法時,為了保證處理時可以進行逆向查找,將不確定動作的ID號mulm保存在saHead[v]鏈表中,這樣可以通過這個鏈表找到mulm。第2行～第10行是求狀態(tài)u是否能夠確定到達狀態(tài)i,判斷算法如下:由于狀態(tài)u是不確定動作act的起始狀態(tài),因此如果這個不確定動作act的所有終止狀態(tài)都確定可達狀態(tài)i,那說明狀態(tài)u也是確定可達狀態(tài)i;第12行的for循環(huán)更新每一個狀態(tài);第19行的for循環(huán)是處理的一種不確定動作嵌套的特殊情況,即不確定動作act的所有終止狀態(tài)中的任意一個狀態(tài)是另外一個不確定動作的起始狀態(tài),如果這個不確定動作的ID號ra還沒有加入隊列,則將它加入到隊列中。至此,處理確定可達部分的算法結束。

處理不確定動作中不確定可達的算法具體如下:

在處理不確定可達的算法中,第2行的for循環(huán)是將所有保存在mulAction中的可達關系全部放入graph數組中,如果graph[u][v]已經為1,則不需要更新,否則將graph[u][v]置為2。至此處理不確定動作的過程結束。

在執(zhí)行完處理確定動作和不確定動作的算法后,再執(zhí)行一遍solveReach函數,就可以得到所有狀態(tài)對之間的可達關系。

對算法時間復雜度進行分析,設規(guī)劃領域中有n個狀態(tài),該算法的時間主要用于2個部分,即處理確定動作的算法和處理不確定動作的算法。這兩部分中都用到了solveReach函數,對solveReach函數的時間復雜度進行分析:這部分算法的時間主要用于3個循環(huán),而且這3個循環(huán)都要遍歷規(guī)劃領域中的所有狀態(tài),時間復雜度為O(n3)。對于處理確定動作的算法進行分析可知,這部分算法需要遍歷規(guī)劃領域的所有狀態(tài),最后需執(zhí)行solveReach函數來確保確定可達的傳遞性,時間復雜度為O(n+n3);在處理不確定動作的算法中,假設進入隊列的次數為q,且需要遍歷規(guī)劃領域中所有的狀態(tài),最后還需執(zhí)行一遍solveReach函數,時間復雜度為O(qn+n3)。根據對這兩部分算法的時間復雜度分析可知,快速求解可達關系的算法時間復雜度為O(qn+n3)。

4 算法實例分析

設Σ=(S,A,γ)是一個不確定狀態(tài)轉移系統,如圖1所示。

圖1 不確定狀態(tài)轉移系統

根據本文算法可知,狀態(tài)到狀態(tài)本身是確定可達的,即graph[i][i]=1。算法分兩部分求可達關系:(1)處理確定動作,根據算法中對確定動作的處理可得graph[s1][s2]=1,即狀態(tài)s1確定可達狀態(tài)s2。同理,graph[s4][s7]=1,graph[s5][s7]=1,graph[s6][s7]=1,graph[s3][s6]=1,graph[s3][s1]=1。由于算法保證確定可達具有傳遞性,且有graph[s6][s7]=1,graph[s3][s6]=1,因此有graph[s3][s7]=1。(2)處理不確定動作,如圖 1所示,該不確定狀態(tài)轉移系統有 3個不確定動作T1,T2,T3。對于T1有graph[s4][s7]=1,graph[s5][s7]=1,即不確定動作T1的終止狀態(tài)集確定可達狀態(tài)s7。所以根據算法可得,該不確定動作的起始狀態(tài)s2也確定可達狀態(tài)s7,即graph[s2][s7]=1,因此更新狀態(tài)s2和狀態(tài)s7之間的可達關系。同時,由于graph[s1][s2]=1,根據傳遞性有graph[s1][s7]=1,因此更新狀態(tài)s1和狀態(tài)s7之間的可達關系。同理,對于T2,T3可以得到graph[s3][s7]=1,更新這個可達關系。

至此已完成確定可達情況的處理,接下來處理不確定可達的情況。根據處理不確定動作的算法可知,對于T2有graph[s3][s1]=2,由于上文已得到狀態(tài)s3和狀態(tài)s1之間為確定可達,因此不需要更新這個可達關系,仍為graph[s3][s1]=1;graph[s3][s5]=2,更新這個可達關系。同理,對于T1,T3可以得到graph[s2][s4]=2,graph[s2][s5]=2,graph[s3][s5]=2,更新這些可達關系。

在執(zhí)行solveReach函數后得到graph[s1][s4]=2,graph[s1][s5]=2,graph[s3][s4]=2。

所以,該不確定狀態(tài)轉移系統的確定可達關系和不確定可達關系如下:

5 實驗結果及分析

實驗環(huán)境均為Windows7+Core(TM)i3-3220

3.3 GHz+4.0 GB內存 +VC6。實驗數據隨機生成。

表1為文獻[8]中求狀態(tài)可達關系的算法與本文提出快速求解狀態(tài)可達關系算法的實驗結果比較。

表1 執(zhí)行時間對比 s

由表1可知,當不確定狀態(tài)轉移系統中的狀態(tài)數目較少時,文獻[8]中的矩陣乘算法和本文算法的運行時間都很短,此時本文算法的優(yōu)勢不明顯。當不確定狀態(tài)系統中的狀態(tài)數目較多時,本文算法的優(yōu)勢便突顯出來,證明它在求解可達關系時具有更高的效率。隨著狀態(tài)數的增長,由于時間復雜度不同,矩陣乘的運行時間增長速度較快,而本文算法的運行時間則增長平緩。

從實驗結果及分析可以看出,采用本文算法可以更加快速地得到不確定系統狀態(tài)之間的可達關系。

6 結束語

本文提出一種快速求解狀態(tài)可達關系的算法。通過實例說明,本文算法可以更加高效、全面地得到不確定狀態(tài)系統的可達關系。在求解狀態(tài)可達關系的基礎上,下一步將對以下工作進行研究:(1)基于可達關系求多Agent規(guī)劃解;(2)對狀態(tài)轉移系統中的動作增加權值,求確定可達的狀態(tài)最短路徑。

[1] Huang Wei,Wen Zhonghua,Jiang Yunfei,etal. Comparison Between Two Languages Used to Express Planning Goals:CTL and EAGLE[C]//Proceedings of PRICAI’06.[S.l.]:Springer-Verlag,2006:180-189.

[2] Roveri C M.Conformant Planning via Model Checking and Heuristic Search[J].Artificial Intelligence,2004, 159(1/2):127-206.

[3] Bertoli P,Cimatti A,Roveri M,et al.Strong Planning Under Partial Observability[J].Artificial Intelligence, 2006,170(1):337-384.

[4] Roveri C M,Traverso P.Automatic OBDD-based Generation ofUniversalPlansin Non-deterministic Domains[C]//Proceedings of AAAI’98.Madison, USA:AAAI Press,1998:26-30.

[5] Cimatti A,Pistore M,Rovveri M,et al.Weak,Strong,and Strong Cyclic Planning via Symbolic Model Checking[J]. Artificial Intelligence,2003,147(1/2):35-64.

[6] 陳建林.強規(guī)劃解、弱規(guī)劃解的研究[D].湘潭:湘潭大學,2011.

[7] 文中華,黃 巍,劉任任,等.模型檢測規(guī)劃中的狀態(tài)分層算法[J].軟件學報,2009,20(4):858-869.

[8] 文中華,黃 巍,劉任任,等.模型檢測規(guī)劃中的狀態(tài)之間的可達關系研究[J].計算機學報,2012,35(8): 1634-1643.

[9] 黃麗芳.基于不確定系統的狀態(tài)可達關系求規(guī)劃解的算法研究[D].湘潭:湘潭大學,2013.

[10] 胡雨隆.基于模型檢測的不確定規(guī)劃中的狀態(tài)可達性研究[D].湘潭:湘潭大學,2012.

[11] 黃麗芳,文中華,胡雨隆,等.不確定規(guī)劃中狀態(tài)循環(huán)可達關系的求解算法[J].計算機應用研究,2013, 30(9):2689-2693.

[12] 胡雨隆,文中華,常 青,等.不確定規(guī)劃中狀態(tài)非循環(huán)可達關系的求解算法[J].計算機仿真,2012, 29(5):114-117.

[13] 陳建林,文中華,朱 江,等.正向搜索算法求強規(guī)劃解[J].計算機工程與應用,2011,47(6):52-54.

[14] Huang Wei,Wen Zhonghua,Jiang Yunfei,etal. Structured Plans and Observation Reduction for Plans with Contexts[C]//Proceedings of IJCAI’09. Pasadena,USA:AAAI Press,2009:1721-1728.

[15] Huang Wei,Wen Zhonghua,Jiang Yunfei,et al.Observation Reduction for Strong Plans[C]//Proceedings of IJCAI’07.Hyderabad,India:AAAI Press,2007:1930-1935.

編輯 陸燕菲

Fast Solving Algorithm of Reachability Relation in Uncertain Planning

LONG Feng,WEN Zhonghua,TANG Jie,WANG Jinzong
(College of Information Engineering,Xiangtan University,Xiangtan 411105,China)

In uncertain planning field,it is frequent to solve many planning problems over a nondeterministic statetransition system in uncertain planning.So getting the state reachability for the nondeterministic state-transition system can make solving planning problems easier.However,the existing solution matrix multiplication of relations exist the problem of high algorithm complexity.Therefore,this paper presents a fast solving algorithm of reachability relation between the states in uncertain planning.The algorithm determines the certainly action and uncertainty actions separately.It determines the relationships between the certainty action,then solves relations between uncertain actions with lists and queues. Experimental result shows that the algorithm not only can get a more comprehensive relationship,but also has higher efficiency than the matrix multiplication algorithm.

uncertain planning;reachability relation;intelligent planning;model checking;uncertainty;uncertain statetransition system

1000-3428(2015)01-0196-04

A

TP18

10.3969/j.issn.1000-3428.2015.01.036

國家自然科學基金資助項目(61070232,61272295)。

龍 鳳(1989-),女,碩士研究生,主研方向:智能規(guī)劃;文中華,教授、博士生導師;唐 杰、王進宗,碩士研究生。

2013-12-30

2014-03-26 E-mail:416807936@qq.com

中文引用格式:龍 鳳,文中華,唐 杰,等.不確定規(guī)劃中可達關系的快速求解算法[J].計算機工程,2015,41(1): 196-199.

英文引用格式:Long Feng,Wen Zhonghua,Tang Jie,et al.Fast Solving Algorithm of Reachability Relation in Uncertain Planning[J].Computer Engineering,2015,41(1):196-199.