在动作模型学习的研究中,第一个趋势是状态信息越来越不完备,研究逐渐延伸到部分观测领域.这是因为,很多时候完全观测在现实世界中难以保证.于是与相关领域一样^[19],研究者们越来越多地开始将部分观测环境问题考虑进来.

在最开始的时候,研究人员把精力集中在完全观测领域.在1994年,Sablon和Bruynooghe^[20]学习了事件演算.然后在1995年,Wang提出了一种通过观测和实践来学习操作的算法^[21].5年后,Balac利用回归树来学习动作模型^[22].到此为止,所有的研究都是在完全观测领域中进行的.到21世纪,动作模型学习领域被扩展到了部分观测领域.就在2000年,Schmill使用聚类和决策树推导来学习部分观测环境中的动作模型^[12].4年后,在部分观测马尔可夫过程(POMDP)中学习动作模型的方法被Holmes和Isbell提了出来^[11].直到最近,不完备信息的说法被正式地加以使用.其中在2007年,Yang^[10]提出了在不完备信息条件下从规划例中学习动作模型的方法,主要技术是基于约束的特征选择.随后,Zhou^[13]扩展了Yang的做法,在不完备信息条件下学习包含量词和蕴涵关系的复杂动作模型.另外一个例子是Amir在2008年的工作^[4],他假设所有的特性都能够被观测,但是被观测得到的频率是指定的,然后在这种环境下学习动作模型,具体方法是使用领域动作来演化信念状态以及使用观测动作来过滤信 念状态.不过,上述所有工作都是针对确定性动作模型的.

在动作模型学习的研究中,第二个趋势是越来越多地支持不确定特性.STRIPS有很多不现实的假设,所以很多应用都无法用STRIPS建模.为了移除这些不现实的假设,STRIPS的后继版本逐步增加了很多新特性,其中最重要的就是不确定性.例如,Probabilistic Planning Domain Definition Language(PPDDL)^[23]就支持不确定动作以及带有概率的动作效果.为了跟上PDDL演进的步伐,动作模型学习领域的学者们也逐渐开始支持新的特性,比如Rao^[24]在2010年提出学习PDDL中的派生谓词规则^[3].

不过,在这些新特性中,最早被学习的仍然是不确定性,包括概率特性.在1992年,Chrisman提出了一种抽象得到概率动作模型的方法^[14].4年后,Oates和Cohen学习了带有概率效果的动作模型^[15].而最近几年,对概率动作模型的学习有复兴的趋势.比如2007年,Pasula学习了随机领域中的符号化动作模型^[16].随后,Hajishirzi在假设只有初始状态的分布已知的情况下学习动作模型^[17].再比如,在2010年,Rao学习了网络服务的不确定动作模型^[18].不过,上述这些研究都是基于完全观测的这一假设的.

动作的前提和效果反映的是在相邻状态中变化的命题.因此,对于本文学习问题中的唯一输入——动作-观测序列,我们首先需要重建状态序列.同时,由于初始状态未知,而且命题的真值由于观测的不完备性可能在状态中不可知,所以对于所有的pÎP,我们需要判断它在状态中成立的概率.为了进行这样的判断,我们需要做一些假定,这些假定用于处理观测中的信息,以便状态的重建.

假定1(最少修改假设). 给定一个文字l和一个t步动作-观测序<a_i,o_i>(1≤i≤t),并且假设在动作a_i之前的状态是s_i-1.如果l∈o_i并且对∀j(0<j<i)有l∉o_j成立,则有l∉s_j成立.另外,如果l∉o_i,并且对∀j(i<j≤t)有l∉o_j成立,则有Î∉s_j成立.

做出假设1的原因是动作效果中的文字相对于所有文字的全集来说是非常少的,而且初始状态也没有给定.换言之,一个文字在第1次被观测到之前被改变的概率是非常小的.类似地,一个文字在最后一次被观测到之后被修改的概率也是非常小的.实际上,如果不做出这样的假设,那么相关的信息就会变得非常不可知,我们的问题也就演变成了状态信息不完备的情况.

假定2(均等机会假设). 给定一个文字l和一个t步动作-观测序列<a_i,o_i>(1≤i≤t),并且假设在动作a_i之前的状态是s_i-1.如果对于1≤j<i≤t,有l∈o_i且¬l∉o_k并且对∀k(j<k<i)有l∈o_i且¬l∉o_k,则l∈s_k的概率是

做出假设2的原因是:在建立状态序列的时候,动作的效果是未知的,因此无法判定具体是在哪一步产生相应的变化.那么,我们只能假定每个动作都有相同的机会去改变一个文字.如假定2所述,当j<i且l∈o_i和¬l∉o_j时,a_j+1,…,a_i均有的概率使得l为真,那么l∈sk (j<k<i)的概率为

下面的算法1给出了建立状态序列的过程.在这个算法中,prob是二维数组,每个元素prob[i][j]表示命题集P中第j个流文字p_j在s_i中成立的概率,其中,1≤j≤n,n=|P|,1≤i≤t.

算法1. 状态建立算法.

输入:t步动作-观测序列<a_i,o_i>(1≤i≤t);

输出:命题集合P,状态序列S=ás₀,…,s_tñ,动作集合A和概率数组prob[1...t][1...n].

关于算法1的解释如下:在算法1中,第1行~第5行重建了P,S,A,其中,P的元素来自于观测中出现的命题,由于观测的不完备性,S是信念状态集合,A由动作-观测序列中的动作构成.第6行~第31行用来计算各命题在状态中出现的概率,其中,第15行、第16行、第18 行、第19行、第25行、第26行、第30行和第31行的依据是假设1,而第13行、第14行、第23行和第24行的依据是假设2.对于每个在观测中出现的文字,分为正文字和负文字两种情况来讨论:如果是正文字(第8行),并且在之前的观测中出现其负文字(第12行),则依据假设2,这两个观测之间的动作有均等机会使得该文字对应的命题为真(即动作的增加效果),因而计算其在两个观测之间的状态中出现的概率(第13行、第14行);负文字的情况与正文字的情况类似,区别只是在于如果在之前的观测中出现其正文字(第22行),那么这两个观测之间的动作有均等机会使得该文字对应的命题为假(即动作的删除效果),因此,该命题在状态中成立的概率为1减去其不成立的概率(第24行).

算法1的时间复杂性是O(nxt³),其中,n=|P|,P是命题集合,t是动作-观测序列的步数.分析如下:在算法1中,第1行~第5行的时间复杂性是O(nxt).第6行循环的次数是O(t) ,而第7行循环的次数是O(n).接着,算法的第8行~第19行处理观测中的正文字.当观测中出现正文字时,即第8行的条件成立,第14行和第16行的计算在最坏情况下均执行O(t²)次.而第18行的循环在最坏情况下执行O(t)次,第18行与第9行是顺序进行的.因此算法的第8行~第19行的时间复杂性是O(nxt³).不难看到,算法的第8行~第19行和第20行~第31行是两个对称结构,分别处理观测中的正文字和负文字,因而这两部分的时间复杂性是相同的.于是,整个算法的时间复杂性是O(nxt³).实际上,在大多数情况下,算法1执行得很快,因为在一般情况下,我们有n>>t.

根据动作模型的定义,前提是在状态中应用动作的充要条件,即动作在状态中可应用,当且仅当该动作的前提在状态中是成立的.因此,从概率统计的观点来看,如果文字l是动作前提的一部分,那么在动作执行前的所有状态中该文字成立的概率要么是1,要么接近1.此外,由于PDDL语言所描述的动作模型是基于一阶谓词逻辑的,因此我们需要在抽取动作前提之前将状态之间的变化进行模式化.算法2实现了上述思想.

关于算法2的解释如下:首先,在算法2的第4行是对动作名进行比较,而不是对整个动作实例进行比较.这是因为动作模型是基于一阶逻辑的,因此只要动作实例的名字相同,就都属于同一动作模型,就可以用来提取前提和效果;其次,在算法2中,probDiff是矢量,表示在动作执行前后的两个状态中所有命题的概率差.在第9行中,当命题在前后两个状态中成立的概率差超过给定的阈值时,就认为该命题被动作改变,成为动作的效果.接着, effSch 表示模式化的效果,precSch表示模式化的前提,而模式化指的是将对象常量转化为参数变量.例如,将命题on(A,B)模式化的结果为on(x,y).在第14行中,根据模式化的效果来模式化前提,可以减少无关对象的干扰而方便模式的匹配,也为后面提取效果做好准备.所涉及到的步骤包括:1) 先求出s_i-1和s_j-1中相同的且出现概率为1的文字,作为动作a_i的初始前提集合iniPrec(第5行);2) 根据变量关联来筛选iniPrec中的前提,即与效果effSch有变量关联的前提留下,没有变量关联的前提被丢弃(第13行);3) 根据模式化的效果来模式化前提,即在效果中已有的变量绑定在前提中延续,而在效果中未出现但在前提中出现的新对象被绑定新变量(第14行);最后,在第16行中,prec是模式化的前提集合,其元素的交集为动作a_i的前提precondition_i,而求元素的交集实质上是进行模式匹配的过程. 算法2除输出动作前提外,还输出包含冗余的效果集合,为下一步提取动作效果做好准备.

算法2的时间复杂性为O(mxtxn²),其中,m=|A|,n=|P|,A是动作集合,P是命题集合,t为动作-观测序列步长.分析如下:算法2的主体由3重循环组成:第1重循环是在第1行,共循环O(m)次;第2重循环是在第3行,其循环次数为O(t);而第3重循环是在第7行,其循环次数为O(n).在第2重循环内部:第5行求两个状态的交集,时间复杂性为O(n);第6行求矢量差,时间复杂性也为O(n).在第3重循环内部:第10行将单个命题模式化成谓词可以看成是在常数时间内完成,这是因为一般 情况下谓词的参数个数都是个位数;第13行过滤前提,由于iniEffect和iniPrec的大小均不超过O(n),因此时间复杂性为O(n²).同理,第14行模式化前提的时间复杂性为O(n²);最后,第16行中求子集族中元素的交集,时间复杂性为O(n²).所以,整个算法2的时间复杂性为O(mxtxn²).此外,A中的动作均来自于动作-观测序列,因此我们有m≤t,算法2的时间复杂性也简略地表示为O(t²xn²).

不过,在算法2中,阈值的选择需要一个标准.在本文中,我们采用一种拟合实验数据的方式.具体地说,我们希望学习所得的前提中文字的数目与原有标准领域定义的动作前提中文字数目基本吻合.为此,我们列举领域中动作的前提数,然后用它的平均值作为该领域期望的动作模型前提文字数.实际上,对于所有的IPPC 2008领域我们都进行了统计.作为例子,表 1展示了Blocksworld领域的情况,其前提中文字个数的平均数为3.在实验中,我们会调整阈值,使得输出的动作前提的文字个数与这个期望值相近.

表 1(Table 1)

Table 1 Number of literals in preconditions (IPPC 2008 Blocksworld domain) 表 1 动作前提中的文字个数(IPPC 2008 Blocksworld领域) Domain name Action name Number of literals in precondition Blocks-Domain pick-up 3 pick-up-from-table 3 put-on-block 4 put-down 2 pick-tower 4 put-tower-on-block 4 put-tower-down 2

Table 1 Number of literals in preconditions (IPPC 2008 Blocksworld domain) 表 1 动作前提中的文字个数(IPPC 2008 Blocksworld领域)

在算法2中,在模式化前提之前我们实际上已经得到了所有效果的模式.不过,这些模式有很多是相同的.进一步地,由于部分观测的环境,很多形式上差别不大的模式实际上来自于相同的动作效果.例如,两组效果模式{clear(x),holding(y),not on(y,x)}和{clear(y),holding(x),not on(x,y)}实际上表示相同的含义.因此,从算法2中得到的同一动作的效果模式的数量会远远大于所需要的动作效果个数.这个事实要求我们对相同或者相似的效果进行合并.这个问题实际上是相关研究中实体相似度判断的问题^[25].因此,我们借用相似度判断的方式来对算法2中得到的效果进行聚类.其中的关键在于如何判断两个效果模式的相似程度,我们采用已有定义^[25]来判断.

定义4(实体相似度). 如果两个实体A和B都是谓词集合,并且这两个集合的秩分别为|A|和|B|,那么这两个 实体的相似度为

如果两个实体A和B的相似度足够大,那么它们就可以被视为是同一个实体.当然,在进行比较时会进行一些简单的变量替换的过程,可能会因此带来误差.整个算法见算法3.

关于算法3的解释如下:算法3对每个动作的效果集合进行聚类.这些效果来自于动作-观测序列中被动作明显改变的命题.只要与给定的动作名相同,每个动作实例就产生一组效果.这些效果可能包含冗余,因此需要进行聚类.第4行计算效果模式的相似度,达到一定的阈值就认为它们是一样的.第6行记录一类效果模式的样例数,以便观察冗余程度.然而在具体的实现过程中,为了保证效果模式的有效性,我们在开始算法3之前还有一个效果模式的筛选过程,即一个效果模式必须覆盖一定数量的样例之后才被保留,这样保留下来的效果模式才比较有代表性.我们称这个样例的数量为最小覆盖样例数.

算法3的时间复杂性为O(t²xn²xm),其中,m=|A|,n=|P|,A是动作集合,P是命题集合,t为动作-观测序列步长.分析如下:从算法2可知,每个动作最多有t个效果模式,即|effect_j|≤t,这是因为在算法2的第3行的循环中每次最多产生一个效果模式.在算法3中,第1行~第3行构成一个3重循环:第1重循环共循环m次,第2重和第3重循环均循环t次.在第3重循环内部,第4行计算实体相似度所花费的时间为O(n²),因为每个效果模式的大小不超过O(n).因此, 算法3的时间复杂性为O(t²xn²xm).同上,A中的动作均来自于动作-观测序列,因此有m≤t,算法3的时间复杂性也简略地表示为O(t³xn²).

像第3.2节对前提的提取一样,阈值的选择在算法3中依旧需要一个准则.本文中,我们继续采用数据拟合的方式,即要求学习到的动作效果个数与原有领域描述中动作的效果个数基本一致.为此,我们统计了每个领域的动作效果数.表 2中就以IPPC 2008的Blocksworld领域为例展示了动作效果的数目,其平均值为2.我们在实验中就以这个平均值为目标调校阈值.

表 2(Table 2)

Table 2 Number of effects for actions (IPPC 2008 Blocksworld domains) 表 2 动作效果的个数(IPPC 2008 Blocksworld领域) Domain name Action name Number of literals in precondition Blocksworld pick-up 2 pick-up-from-table 2 put-on-block 2 put-down 1 pick-tower 2 put-tower-on-block 2 put-tower-down 1

Table 2 Number of effects for actions (IPPC 2008 Blocksworld domains) 表 2 动作效果的个数(IPPC 2008 Blocksworld领域)

IPPC 2008共设有Fully Observable Probabilistic(FOP),Non Observable Non-Deterministic(NOND)和Fully Observable Non-Deterministic(FOND)等几个部分.它们都采用了评估服务器-规划器客户机的模式.测试中的每一轮分4步,循环进行:第1步是服务器产生初始状态并发给规划器,第2步是规划器在线产生规划并返回一个动作,第3步是服务器执行动作并评估效果,最后一步是服务器后发送新的状态给规划器.

我们采用FOP领域作为基准测试领域,这主要是为了证明我们的方法可以扩展到概率环境.在上述第3步中产生的内容将作为动作序列.为了模拟部分观测环境,我们随机地选择一定比例的流文字标记为已知,作为观测的结果,即设置一个观测率l.这些观测加入到规划解中,构成动作-观测序列.然后,采用5-交叉验证的测试方法来学习动作模型,即4/5的训练例用来学习动作模型,而剩下的1/5用来进行评估.具体地说,我们采用MDPSim (http://code.google.com/p/mdpsim/),IPPC 2008的官方软件来产生训练例.所有的实验都是在PC工作站上进行的,其中,CPU是2.4 GHZ Celeron,内存为2 GB.MDPSim软件是C编写的,我们在Ubuntu Server 10.04.3 LTS上运行它.我们的系统是采用Java来编写的,在Windows 2008 Server上加以运行.对于IPPC 2008 FOP的所有领域,我们采用10个问题,每个问题10次测试,每次测试取100步的方法.即总共产生10 000个训练例,其中,8 000个用于训练,2 000个用于评估.在实际开发过程中,出于编码上的方便,我们将算法2和算法3加以混编.具体地,我们会首先学习邻接状态间的变化,然后在聚类效果的同时建立动作的模式,而前提的抽取被放在最后.

此外,这里补充关于训练例数量的说明.在部分观测环境下的实验需要体现统计特性,因此往往需要比较大量的数据来说明问题.在前人的一些工作中,例如Yang等人^[10]的工作,采用100~200个规划解作为训练数据集,但是每个规划解并不限制规划步骤的长度.只是对于规划比赛中的基准问题,规划解长度一般小于100,因此按照规划步来计算训练例总数在10 000左右.而在另一些前人的工作中,例如Amir等人^[4]的工作,则是直接以规划步来作为训练例,数目在5 000个左右.因此,本文采用10 000个规划步作为训练例集合,是参考了同类相关工作的执行标准.

参考已有的研究^[19],我们说一个动作的前提不能被动作的前驱状态满足时就产生了一个错误,这时,学习到的动作前提没有对训练例进行正确的解释.同样地,如果一个动作的效果在其后继状态中不能被满足,也称出现了一个错误.但是对于概率效果而言,更重要的是用概率分布的差异来表示错误率.

定义5. 前提错误率error_pre为m/n,其中,m是错误解释的训练例的数量,而n是总的训练例的数量.

定义6. 概率效果错误率error_effs为概率分布的距离.如果原有动作描述中的分布是P(x),而学习得到的分布为Q(x),那么其距离为

不过,考虑到IPPC 2008中仅采用了Bernoulli分布,我们在测试中用Bernoulli分布的参数的差作为效果错误率的简单估计.

定义7. 动作模型错误率:

类似地,本文中领域错误率定义为其所包含的动作模型的错误率的平均值.

由于没有其他的研究工作进行部分观测环境下的不确定动作模型的学习,因此本文的实验结果展示的是本系统在不同规划基准领域中学习错误率的比较.相对于其他相关方法,本文方法的先进性仅在理论上作初步的讨论.与以往工作不同,本文是在部分观测环境下学习不确定动作模型,其中,用于处理观测信息的两个假定和用于对不确定性结果进行去冗的聚类方法成为使这一目标可行的关键方法.以往工作,或者在部分观测环境下学习确定性的动作模型,或者在完全观测环境下学习概率动作效果,在部分观测下学习确定性动作模型的典型方法有CBFS(constraints-based formulas selecting)^[10]和SLAF(simultaneous learning and filtering)^[4].这两种方法都难以用于我们的学习目标.具体原因在于动作的不确定性使得CBSF中的约束具有柔性,因此难以直接使用.而SLAF尽管声称可扩展到不确定领域,但其在不确定环境中的推理非常复杂.另一方面,以往不确定动作模型的学习或者是有监督的^[26],或者假设环境是完全可观测的^[16].这些对于我们的学习目标都不现实.正如前面一节所讨论的学习样例的数量,我们需要大量的数据来进行学习,如果要求有监督,那么工作量就太大了.同样,完全可观测环境也大量增加了实际成本开销.更进一步地,在动作模型的描述语言方面,本文方法也具有优越性.以往工作要么基于STRIPS,要么基于各自的描述形式,而本文方法是基于在概率规划比赛中使用的标准描述语言PPDDL.

图 3给出了在观测率l=0.9时本文系统在IPPC 2008(FOP)领域的学习错误率.其中,效果最好的来自于Blocksworld领域,其错误率大概为0.231.初步的分析是,不同领域的学习错误率之间的差异主要来自于动作模型本身复杂性的影响.至于更深层的原因需要更进一步的领域分析.由于学习到的动作模型具有不确定性,因此学习的错误率要比类似情况下的确定性动作模型学习^[4]的错误率高一些.图 4给出了对应的学习时间.

图 3

Fig. 3

Fig. 3 Error rate of IPPC 2008 (FOP) domains图 3 IPPC 2008 (FOP)领域的学习错误率

图 4

Fig. 4

Fig. 4 CPU time for IPPC 2008 (FOP) domains 图 4 IPPC 2008 (FOP)领域的学习时间

由于篇幅所限,本文不一一列举出所有的学习结果,仅用一个例子来加以说明.

例3:当观测率为0.95时,本文系统在Blocksworld领域学习到的动作pick-up的模型如下:

与例1所示的标准模型对比可以看到,动作的前提都学到了,动作的效果也学到了两组,不过,其中有文字丢失.在第1组效果中没有学习到文字(holding ?x).此外,经过统计得到的效果概率分布也与标准模型有稍微差别.尽管这一学习结果与标准模型不完全相同,但是可以看到,它们的相似度是比较高的,效果的组数和大部分的文字是完全相同的.

此外,观测率和最小覆盖样例数的设置对学习结果也有影响.在实验中可以发现,当观测率<0.8时,学习效果普遍很差,大多数领域动作模型的错误率非常高;而当观测率>0.95时,大多数领域能够学习到基本正确的动作模型.我们认为,这些范围的观测率反映的是比较极端的情况,即不可观测和完全可观测两种情形.而当观测率约为0.9时,不同领域的错误率反映的是正常的领域差异(如图 3所示),即由领域本身的复杂性所主导的.另一方面,最小覆盖样例数用来筛选初步得到的动作效果模式,在实验中可以发现:当最小覆盖样例数<4时,筛选之后仍然得到大量效果;而当逐步提高最小覆盖样例数时,筛选结果会有所改善.但是最小覆盖样例数也不能太大,因为太多的效果模式被筛除会导致最后的动作效果很少,从而导致很高的错误率.在本文的实验中我们发现,最小覆盖样例数选择在8左右是比较适宜的.