一种快速求强规划解的算法

劳佳琪,文中华,2,伍小辉,唐 杰

(1.湘潭大学信息工程学院,湖南湘潭411105;2.湖南工程学院计算机与通信学院,湖南湘潭411104)

一种快速求强规划解的算法

劳佳琪1,文中华1,2,伍小辉1,唐 杰1

(1.湘潭大学信息工程学院,湖南湘潭411105;2.湖南工程学院计算机与通信学院,湖南湘潭411104)

为提高求解效率,设计一种求强规划解的简化分层算法。以传统分层算法为基础,引入贪心选择策略,对每个非目标状态的动作进行筛选,去除对求解强规划解无益的动作,加快状态向下搜索的速度,并在改进分层的基础上,优化求强规划解策略,由于在求解过程中会存在大量重复搜索,因此建立一个集合保存已访问状态的信息,避免对状态的重复搜索。分析结果表明,在初始状态到达目标状态路径都不重合的情况下,改进算法的时间复杂度为O(nm)(n为初始状态个数,m为层数),在都重合情况下为O(m),优于普通正向搜索算法与反向搜索算法。

不确定规划;强规划解;分层状态;贪心策略;模型检测;智能规划

1 概述

智能规划是人工智能领域的一个重要领域,不确定规划［1］是其中的一个重要分支。在不确定规划中,由于动作效果是不确定的,一个规划的执行可能对应许多个序列状态,因此找出一个序列使所有可能的执行都到达目标状态(即强规划解)是很有意义的。

模型检测［2-3］是求解不确定规划问题的一个重要方法,目前有很多关于基于模型检测求解强规划解［4］的研究,并且取得了许多重要成果。如文献［5-6］提出运用反向搜索法求解强规划解,由于缺少引导信息,需要重复搜索大量无用动作,因此文献［7-9］提出运用分层法求解强规划解,与反向搜索法相比,该方法去除了大量无用的动作,避免了许多无用搜索,加快了求解强规划解的速度,但该方法仍

存在不足,即对于每个非目标状态可能存在较多向下层转移的动作,并且当问题规模较大时,会存在大量重复搜索,降低求解效率。

本文参考文献［9-11］算法,提出一种快速求强规划解的算法。改进分层策略,使每个非目标状态仅保留一个向下转移的动作,并尽可能使处于同一层的非目标状态可以到达共同目的状态,完善求解强规划解的策略［12］,避免重复搜索。

2 相关定义

在不确定规划领域中,存在某些动作的执行效果是不确定的,那么一个规划的执行就会到达不同的状态。但有时需要这样一个规划,一旦执行它就一定会到达满足某些条件的状态,因此,文献［5］提出强规划解的概念。主要定义如下:

定义1(不确定规划领域) 一个规划领域是一个不确定的状态转移系统Σ=(S,A,γ),其中,S是有限状态集;A是有限动作集;γ:S×A→2S是状态转移函数［5］。

γ用来刻画不确定性:在状态s下执行动作a所得到的状态集合就是γ(s,a)。若γ(s,a)非空,则称动作a在状态s下是可执行的。在状态s下可执行动作的集合记为A(s)={a:∃s∈γ(s,a)},并称(s,a)为状态动作序偶。

定义2(规划问题) 规划领域Σ下的规划问题P是一个三元组(Σ,S0,Sg),其中,S0⊆S是初始状态集合;Sg⊆S是目标状态集合［6］。

定义3(不确定规划的执行结构) 设π是规划领域Σ=(S,A,γ)中的一个状态动作序偶表,P= (Σ,S0,Sg)是Σ上的一个规划问题,从初始状态集S0所导出的π的执行结构为K=＜Q,T＞,其中,Q⊆S和T⊆S×S是满足以下条件的最小集合［13］:

(1)若s∈S0,则s∈Q。

(2)若s∈Q且∃(s,a)∈π,s′∈γ(s,a),则s′∈Q且(s,s′)∈T。

执行结构K就是一个有向图,其结点集Q是系统(以S0为初始状态集)执行规划解时所可能到达的所有状态的集合。T表示了所有可能的状态转移,K的终止状态集合记为Sterminal(K),状态s∈Q是K的终止状态当且仅当不存在s′∈Q使得(s,s′)∈T。

定义5(可达状态数) 设Σ=(S,A,γ)是一个规划领域,若有n个状态可以确定到达状态sx,则称sx的确定可达状态数为n。若有m个状态可以不确定到达状态sx,则称sx的不确定可达状态数为m/2。sx的可达状态数为确定可达状态数与不确定可达状态数之和,记为sxnum。

定义6(最大可达状态数) 设Σ=(S,A,γ)是一个规划领域,对于∀s∈S,∃a∈A,都有γ(s,a)= {si,si+1,…,si+n}(n≥0),若该集合中可达状态数最大的状态为sm(i≤m≤i+n),其可达状态数记为max［γ(s,a)］。

3 状态分层及强规划求解算法

文献［7］提出在求解强规划解之前,首先对不确定系统中的状态进行分层,将大量对求解强规划解无用的状态动作序偶去除,并且运用正向搜索技术求解强规划解,即从初始状态开始向下搜索(假设目标状态位于最底层)。但当初始状态集S0较大时,则需要对该集合中的每个状态都进行搜索,例如对于状态s1∈S0,γ(s1,a1)=s2,s2∉Sg,γ(s2,a2)=s3,s3∈Sg,则对于状态s1的搜索完成。若此时有状态s11∈S0并且γ(s11,a11)=s2,按照原有算法需要继续对s2进行搜索,那么就会产生重复搜索的情况,尤其当不确定系统规模较大,初始状态较多时,会产生大量冗余搜索。因此,本文在文献［7］的基础之上,提出一种简化的分层方法,对于每个非目标状态及其可执行动作集合,只保留一个向下转移的动作,并且该动作保证所到达目标状态的可达状态数为最大值,这样可以保证不同的状态在执行向下转移动作时,有很大的可能性转移到同一个状态。

基于该分层方法,改进求强规划解策略,建立一个集合,记录已被访问节点的信息,当某一个初始状态搜索到已被标记的状态时,就停止向下搜索,这样可以避免大量的重复搜索。

3.1 分层方法

设P=(Σ,S0,Sg)是一个不确定的状态转移系统Σ=(S,A,γ)上的一个规划问题,初始状态集合为S0,目标状态集合为Sg。贪心选择策略(该过程类似于投票策略):假设不确定系统第n层状态为:sj,sj+1,…,sj+x(x≥0),第n+1层状态为:si,si+1,…,si+y(y≥0),则对于第n+1层中的状态可能存在不止一个动作到达第n层,则对动作进行筛选,筛选步骤如下:

(1)遍历第n+1层中的所有状态的动作,只保留执行后可到达第n层的动作。

(2)找出第n层中可达状态数最大且未被选中的状态sj+m(m≤x)。

(3)对于第n+1层中的状态,只保留可到达sj+m的动作。

(4)返回步骤(2),直到第n+1层中的所有状态的动作都被筛选。

分层方法具体过程如下:

(1)第1层为目标状态集合Sg(即最底层),S1=Sg。

(2)S2={s:s∉S1,∃A1,∀a∈A1,γ(s,a)⊆S1}若S2≠∅,则对所有属于该层的状态的动作进行筛选,即(s,ai)={s:s∈S2,a:∃i,∀j,j≠i,{ai,aj}⊆A1,max［γ(s,ai)］≥max［γ(s,aj)］}再进行第3层分层。

(3)S2={s:s∉(S1∪S2),∃A2,∀a∈A2,γ(s,a)⊆(S1∪S2)},若S3≠∅,则对所有属于该层的状态的动作进行筛选,即(s,ai)={s:s∈S3,a:∃i,∀j,j≠i,{ai,aj}⊆A2,max［γ(s,ai)］≥max［γ(s,aj)］},再进行第4层分层,否则结束分层。

(4)Sx={s:s∉(S1∪S2∪…∪Sx-1),∃Ax-1,∀a∈Ax-1,γ(s,a)⊆(S1∪S2∪…∪Sx-1)},若Sx≠∅,则对所有属于该层的状态的动作进行筛选,即(s,ai)={s:s∈Sx,a:∃i,∀j,j≠i,{ai,aj}⊆Ax-1, max［γ(s,ai)］≥max［γ(s,aj)］}为第x层(x≥2),否则结束分层。

通过上述步骤,则分层完毕。

3.2 求强规划解的方法

若S0⊄S1∪S2∪…∪Sfloor,则强规划解不存在。反之,开始求解强规划解:由于经过上述方法分层,在不确定系统中,每个状态只保留一个向下层状态转移的动作,并且该动作保证所到达的状态的可达状态数最大,则不同的初始状态在向下搜索的时候有很大的几率会到达同一目标状态。

假设集合Solved保存了已经遍历过的状态,集合Answer保存已遍历过的状态动作序偶。

首先从S0中选取任意选取一个状态si,假设该状态在第n层,则往下搜索,必然存在一条唯一路径L1到达目标状态集合,并将S1-L加入到集合Solved。再从S0中选取一个状态sj,则可能出现2种情况:

(1)sj∈Solved:若该状态属于Solved,则表明sj已被遍历过,则必然存在一条路径可以到达目标状态,否则sj不可能属于Solved集合。

(2)sj∉Solved:若不属于Solved,则进行向下搜索,并把sj加入到集合Solved中。假设状态sj下一次到达的状态集合为Snext,则有以下3种情况:

1)Snext⊆Solved:停止向下搜索。

2)Snext∩Solved=∅:将Snext集合加入到Solved集合中,即Solved=Solved∪Snext,再依次对Snext集合中的状态进行搜索,直到到达的状态都属于Solved集合或者Sg集合。

3)Snext∩Solved≠∅且Snext⊄Solved:将Snext集合加入到Solved集合中,即Solved=Solved∪Snext,再依次对Snext中不属于Solved的状态进行搜索,直到到达的状态都属于Solved集合或者Sg集合。

然后再从S0中选取一个状态,重复这一过程,直到S0为空集,返回强规划解。

4 算法实现及分析

4.1 算法实现

设Σ=(S,A,γ)是一个不确定状态转移系统;S0为初始状态集合;Sg为目标状态集合;Solved为已访问状态的集合;Unsolved为未访问状态的集合;Answer保存已遍历过的状态动作序偶。算法如下:

其中,STRONGNEW(S1,S2,…,Sfloor-1)={s:s∉S1∪S2∪…∪Sfloor-1,γ(s,a)⊆S1∪S2∪…∪Sfloor-1,γ(s,a)≠∅}SIMPLIFY(Sfloor)={(s,ai):s∈Sfloor,∃i,∀j,i≠j,max［γ(s,ai)］＞max［γ(s,aj)］}。

第4行～第7行为对不确定系统进行分层,其中,第5行为构建新的分层;第6行为对新构建的分层中的状态进行动作筛选。第8行～第12行进行初始化并开始求解强规划解。

SOLUTION函数的具体过程如下:

第2行～第6行,若状态si属于Solved集合,则不需要继续向下搜索,否则将该状态加入Solved集合中。第7行～第9行,若γ(si,a)⊆Solved,则将动作序偶(si,a)加入Answer解集。第10行～第14行,状态si执行不确定动作a之后,所到达状态集合为si→a。若该集合与Solved集合存在交集,则接下去只需要搜索未被Solved集合包含的状态。第15行～第19行,状态si执行不确定动作a之后到达的状态集合与Solved集合不存在交集,则再递归调用SOLUTION函数,继续向下搜索。

4.2 算法分析

由于分层消耗的时间与普通正向搜索算法分层所花费的时间差别不大,因此主要分析求强规划解时间。假设算法运行时间为T(n,m),其中,n为初始状态个数;m为不确定系统分层后的层数。根据强规划解的求解策略,考虑2种极端情况:(1)当第一个状态si∈S0搜索完毕后,其他所有状态都属于S1-L集合,那么T(n,m)=T(1,m),则时间复杂度为O(m);(2)对于∀i,si∈S0(0≤i≤n),且S1-L∩S2-L∩…∩Sn-L=∅,那么:

其中,C1,C2为常数;则时间复杂度为O(nm)。

5 算法示例及实验对比

5.1 算法示例

设Σ=(S,A,γ)是一个确定状态转移系统,不确定状态转移图如图1所示。已知S0={s1,s2},Sg= {s6,s7,s8},运用本文算法求解该不确定系统的强规划解。

图1 不确定状态转移图

首先进行分层:S1={s6,s7,s8},接下去构建第2层,由图1可知S2={s3,s4,s5},需要对动作进行筛选,因为状态s6的可达状态数为1,s7的可达状态数为2.5,s8的可达状态数为1.5,则s3,s4,s5只保留到达s7的动作。同理,构建第3层,S3= {s1,s2},再进行动作筛选,则s1,s2只保留到达s4的动作。筛选动作后的不确定状态转移图如图2所示。

图2 筛选动作后的不确定状态转移图

分层完毕后,开始进行强规划的求解。首先从状态s1开始进行搜索,直到到达目标状态。则Solved={s4,s7,s8},Answer={(s1,a2),(s4,a4)}再从状态s2开始进行搜索,由图2可知,γ(s2,a)={s3,s4},因为s4∈Sovled,则接下去只需要对s3进行搜索,由于s7∈Solved,则只需把动作序偶(s3,a3)加入Answer集合。最终得到的强规划解为Answer={(s1,a2),(s4,a4),(s2,a1), (s3,a3)}。

5.2 实验对比

以下为普通正向搜索算法,改进后正向搜索算法(本文算法)以及反向搜索算法的实验结果比较。实验环境均为Windows7+Core(TM)i3-3220 3.3 GHz+4.0 GB内存+VC6。3种算法使用的数据输入输出过程相同,故其运行时间没有包括在内。运行时间比较如表1所示。根据表1可知,改进后正向搜索算法与普通正向搜索算法相比,在求解速度有一定的提高。但从最后2组数据中得出,普通算法与改进后算法时间是处于一个数量级的,这是由于在初始状态搜索的路径中几乎不存在重合的状态(即算法分析中的第2种情况),导致搜索时间增加。但这2种算法比反向搜索算法求解效率都要高。

表1 运行时间比较s

6 结束语

本文设计一种快速求解强规划解的算法。该算法主要从两方面进行优化:(1)在原有分层基础上,对非目标状态的动作进行筛选,加快搜索速度; (2)改进求强规划解的策略,避免对状态的重复搜索。从理论上分析了改进后算法时间复杂度的范围。实验结果证明了其有效性。今后将从以下方面进行研究:(1)改进对非目标状态筛选的策略,加快搜索速度;(2)运用本文算法求解不确定规划中的强循环规划解。

［1]Weld D S.Recent Advances in AI Planning［J］.AI Magazine,1999,20(2):93-123.

［2]Cimatti A,Roveri M.Conformant Planning via Symbolic Model Checking［J］.Journal of Artificial Intelligence Research,2000,13(3):305-338.

［3]Huang Wei,WenZhonghua,JiangYunfei,etal.Observation Reduction for Strong Plans［C］//Proceedings of the 20th International Joint Conference on Artificial Intelligence.Hyderabad,India:［s.n.］,2007:1930-1935.

［4]Marco P,Traverso P.Planning as Model Checking for Extended Goals in Nondeterministic Domains［C］// Proceedings of the 17th International Joint Conference on Artificial Intelligence.San Francisco,USA:［s.n.］, 2001:479-484.

［5]Cimatti A,Pistore M,Roveri M,et al.Weak,Strong,and Strong Cyclic Planning via Symbolic Model Checking［J］.Artificial Intelligence,2003,47(1):35-84.

［6]Cimatti A,Roved M,Traverso P.Strong Planning in Nondeterministic Domains via Model Checking［C］// Proceedings of the 4th International Conference on AI Planning Systems.Edinburgh,UK:［s.n.］,1998:36-43.

［7]文中华,黄 巍,刘任任,等.模型检测规划中的状态分层方法［J］.软件学报,2009,20(4):858-869.

［8]Fu Jicheng,Vincent N,Farokh B,et al.Simple and Fast Strong Planning For Fully-observable Nondeterministic Planning Problems［C］//Proceedings of IJCAI’11.Barcelona,Spain:［s.n.］,2011:473-478.

［9]陈建林.强规划解、弱规划解的研究［D］.湘潭:湘潭大学,2011.

［10]胡雨隆.基于模型检测的不确定规划中的状态可达性研究［D］.湘潭:湘潭大学,2012.

［11]陈建林,文中华,朱 江,等.正向搜索方法求强规划解［J］.计算机工程与应用,2011,47(6):52-54.

［12]胡雨隆,文中华,常 青,等.确定树求强规划解［J］.计算机工程与应用,2012,48(4):40-42.

［13]Ghallab M,Nau D,Traverso P.Automated Planning Theory and Practice［M］.［S.l.］:Morgan Kaufmann Publishers,2004.

［14]胡雨隆,文中华,常 青,等.不确定规划中非循环可达关系的求解方法［J］.计算机仿真,2012,29(4): 114-117.

编辑 刘 冰

A Fast Algorithm for Solving Strong Planning Solution

LAO Jiaqi1,WEN Zhonghua1,2,WU Xiaohui1,TANG Jie1
(1.College of Information Engineering,Xiangtan University,Xiangtan 411105,China;
2.College of Computer and Communication,Hunan Institute of Engineering,Xiangtan 411104,China)

This paper designs a quick solution to solve the simplified layered strong planning algorithm to increase the settlement efficiency.It is based on the introduction of greedy strategy,screening for non-target state for each action.This algorithm removes useless action plan for solving the strong solution to accelerate the state down search speed.On the basis of improved stratification,optimization and strong strategic planning solution,because the solution process is repeated,there are a lot of searching,and therefore the algorithm creates a collection to save the state having access to information,to avoid duplication of state search.After analysis,in the condition that the paths which are the intial state to goal state are overlapping,and the time complexity of this algorithm isO(nm),(nis the number of the initial state,mis the number of layers).The time complexity isO(m)in the condition that all the initial states to the target states are coincident.And the results are better than the ordinary forward search algorithm and reverse search algorithm.

nondeterministic planning;strong planning solution;hierarchical state;greedy strategy;model checking; intelligent planning

劳佳琪,文中华,伍小辉,等.一种快速求强规划解的算法［J］.计算机工程,2015,41(3):162-166.

英文引用格式:Lao Jiaqi,Wen Zhonghua,Wu Xiaohui,et al.A Fast Algorithm for Solving Strong Planning Solution［J］.Computer Engineering,2015,41(3):162-166.

1000-3428(2015)03-0162-05

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.031

国家自然科学基金资助项目(61070232,61272295,61105039,61202398);湖南省重点学科建设基金资助项目(0812);湖南省教育厅科学研究基金资助一般项目(12C0399)。

劳佳琪(1990-),男,硕士研究生,主研方向:智能规划;文中华,教授、博士生导师;伍小辉、唐 杰,硕士研究生。

2014-03-07

:2014-05-22E-mail:lywhlao@qq.com