在部分观测环境下的不确定动作模型学习

内容需要下载文档才能查看

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@http://wendang.chazidian.com

Journal of Software,2014,25(1):51?63 [doi: 10.13328/j.cnki.jos.004417] http://wendang.chazidian.com

©中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563

在部分观测环境下的不确定动作模型学习

饶东宁1, 蒋志华2, 姜云飞3

1

2

3? (广东工业大学 计算机学院,广东 广州 510090) (暨南大学 信息科学与技术学院 计算机科学系,广东 广州 510632) (中山大学 信息科学与技术学院 软件研究所,广东 广州 510275)

通讯作者: 蒋志华, E-mail: tjiangzhh@http://wendang.chazidian.com

摘 要: 近年来,动作模型学习引起了研究人员的极大兴趣.可是,尽管不确定规划已经研究了十几年,动作模型学

习的研究仍然集中于经典的确定性动作模型上.提出了在部分观测环境下学习不确定动作模型的算法,该算法可应

用于假定人们对转移系统一无所知的情形下进行,输入只有动作-观测序列.在现实世界中,这样的场景很常见.致力

于动作是由简单逻辑结构组成的、且观测以一定频率出现的一类问题的研究.学习过程分为3个步骤:首先,计算命

题在状态中成立的概率;然后,将命题抽取成效果模式,再抽取前提;最后,对效果模式进行聚类以去除冗余.在基准领

域上进行的实验结果表明,动作模型学习技术可推广到不确定的部分观测环境中.

关键词: 人工智能;自动规划;动作模型学习;不确定动作;部分观测

中图法分类号: TP181 文献标识码: A 中文引用格式: 饶东宁,蒋志华,姜云飞.在部分观测环境下的不确定动作模型学习.软件学报,2014,25(1):51?63. http://www.

http://wendang.chazidian.com/1000-9825/4417.htm

英文引用格式: Rao DN, Jiang ZH, Jiang YF. Learning partially observable non-deterministic action models. Ruan Jian Xue Bao/

Journal of Software, 2014,25(1):51?63 (in Chinese). http://wendang.chazidian.com/1000-9825/4417.htm

Learning Partially Observable Non-Deterministic Action Models

RAO Dong-Ning1, JIANG Zhi-Hua2, JIANG Yun-Fei3

1

2

3(School of Computers, Guangdong University of Technology, Guangzhou 510090, China) (Department of Computer Science, School of Information Science and Technology, Ji’nan University, Guangzhou 510632, China) (Software Research Institute, School of Information Science and Technology, Sun Yat-Sen University, Guangzhou 510275, China)

Corresponding author: JIANG Zhi-Hua, E-mail: tjiangzhh@http://wendang.chazidian.com

Abstract: Recently, interests in learning action models have been increasing. Although non-deterministic planning has been developed

for several decades, most previous studies in the field of action model learning still focus on classical and deterministic action models.

This paper presents an algorithm for identifying non-deterministic actions, including effects and preconditions, in partially observable

domains. It can be applied when people know nothing about a transferring system and only the action-observation sequences are given.

Such scenarios are common in real-world applications. This work focuses on problems in which actions are composed of simple logical

structures and features are observed under some frequency. The learning process is divided into three steps: First, compute the probability

of each proposition which holds in a state. Second, extract effect schema from propositions and then extract preconditions. Third, cluster

effect schema to remove redundancy. Experimental results on benchmark domains show that action model learning is still useful in

non-deterministic and partial observable environments.

Key words: artificial intelligence; automated planning; learning action models; non-deterministic action; partial observability

领域建模是规划研究中的核心问题,而规划领域和规划问题的描述是领域建模中的关键.经过几十年的发

? 基金项目: 国家自然科学基金(61100134, 61003179); 广东省自然科学基金(S2011040001427)

收稿时间: 2012-08-13; 修改时间: 2013-01-25; 定稿时间: 2013-04-09

内容需要下载文档才能查看

52 Journal of Software 软件学报 Vol.25, No.1, January 2014

展,已有很多种规划领域建模语言被提了出来.比如,Stanford Research Institute Problem Solver(STRIPS)[1], Action Description Language(ADL)[2]以及Planning Domain Definition Language(PDDL)[3].然而,从无至有的撰写领域描述是非常困难和消耗时间的,因此领域模型的获取,特别是自动获取是一个非常值得研究的课题.最近十几年来,利用学习技术来获取领域模型吸引了越来越多人的注意,其中,动作模型学习发展得最快.不过,迄今为止,大多数已有的动作模型学习都是针对经典规划领域,特别是STRIPS领域.

近年来,越来越多的实际应用问题被纳入到规划社区的视野中来.比如说,由于完全可观测对环境的要求过于苛刻,研究人员于是引入了部分可观测领域.这类研究主要针对不能观测到完整系统状态的情况.比如在互联网上,我们一次只能看到一部分网页,而不可能看到整个互联网.当规划目标可能发生变化时,动作模型学习显得尤为重要.比如,如果能够通过行为和反馈学习到自身的动作模型,一个自治智能体就可以自动地对自己的目标做出规划调整.现实世界中,应用问题的另一个特点是动作往往带有不确定性,也就是说,它们的效果可能会有多个.不过,学习不确定动作模型,特别是在部分观测环境中学习不确定动作模型是非常困难的,这主要是基于以下两个原因:首先,困难来自于缺少有用的条件独立的结构[4];其二,动作的不确定性使得学习的效果更加难以保证.

不确定规划一直是自动规划领域的研究热点[5?9],在不确定规划中,动作效果是不确定的,或者初始状态是不确定的.这样的问题比经典规划问题更难[5],因为追踪信念状态比追踪状态更难,并且求解动作策略比求解动作序列更难.这些不确定性往往可以通过对环境的观测来识别.出于节约成本的考虑,环境经常假设为部分可观测的,此时状态信息是不完备的,状态变成了信念状态.在部分观测环境下的不确定规划分为两类:随机规划和POMDP规划.在随机规划[5?7]中,信念状态是状态的集合,求解方法主要是在信念空间进行搜索;而在POMDP规划[8,9]中,信念状态由在状态集合上的概率分布来表示,求解方法主要依赖于MDP方法中的值迭代和策略迭代过程.此外,在不确定规划中,动作模型的自动获取也同样受到广泛的关注.但是,已有的研究成果主要集中在部分观测环境下学习确定性的动作模型[4,10?13],或者是完全观测环境下学习概率动作效果[14?18],而对部分观测环境下学习不确定动作模型的研究几乎没有.如何处理部分观测的信息以及如何处理动作的不确定效果对学习精度的影响,成为解决这一难题的关键.

为了尝试解决这一问题,本文提出一种识别不确定动作模型的算法,该算法在部分观测环境中学习不确定动作的前提和多个效果.它使用一个序列化的观测和动作作为输入,然后输出可能带来这些观测结果的动作模型.学习过程分为3个步骤:首先,根据最小修改假定和均等机会假定来计算命题在状态中成立的概率;然后,将在相邻状态中概率变化明显的命题抽取成效果模式,根据效果模式来抽取前提;最后,对效果模式进行聚类以去除冗余.其中,用于处理观测信息的两个假定和用于对不确定性结果进行去冗的聚类方法是使得在部分观测下学习不确定动作模型可行的关键方法.在基准领域上进行的实验结果说明,动作模型学习技术在部分观测的不确定规划领域仍然有效.这是首个在部分观测环境中进行的不确定动作模型学习的一种尝试.本文所提出的技术对于概率领域也是可行的.

本文第1节给出动作模型学习的文献回顾.在第2节中定义学习问题.然后,具体算法在第3节中给出.第4节的内容是实验部分,包括实验环境、评估方法和实验结果.最后,第5节给出本文的总结和对将来工作的展望. 1 动作模型学习

动作模型学习技术已经发展了20多年,其中有两大趋势:学习被逐步扩展到部分观测领域;学习的领域越来越具有不确定属性.

1.1 在部分观测环境中学习动作模型

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

在最开始的时候,研究人员把精力集中在完全观测领域.在1994年,Sablon和Bruynooghe[20]学习了事件演

内容需要下载文档才能查看

饶东宁 等:在部分观测环境下的不确定动作模型学习 53

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

1.2 支持不确定特性

在动作模型学习的研究中,第二个趋势是越来越多地支持不确定特性.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].不过,上述这些研究都是基于完全观测的这一假设的.

2 问题陈述

本文的目标问题是跟踪一个动态系统,然后通过所得到的时间步和部分观测序列来学习不确定动作模型.同时,像一些已有研究一样[4],初始状态是未知的.对这个问题的解,应该是一个动作模型的组合,规划器使用这个动作模型的组合能够给出期望的观测序列.当然,对这个解的计算和验证可以通过递归地在时间步t进行演算,然后得到时间步t+1的信念状态来进行.这涉及到确定一组可能的动作模型以及这些动作模型可能改变系统状态的方式.这种改变的方式就是转移模型,它决定了系统可能处在哪些状态中.也就是说,任意一个转移模型决定了一系列可能的状态,一个目标问题的解就是一个转移模型及其所关联的可能状态.在本节,我们将形式化地定义本文的目标问题.

定义1. 一个转移系统是一个四元组?P,S,A,R?,其中,

? P是一个有限命题集合;

? S?2P是一个状态集合;

? A是一个有限动作集合,A={a|a=?pre(a),add(a),del(a)?}.其中,pre(a),add(a),del(a)?2P,分别表示动作a的

前提集合、增加效果集合和删除效果集合;

? R?S×A×S是一个转换关系,序对?s,a,s′?表示状态s经过应用动作a可转换到s′,即

s′=(s?del(a))∪add(a).

在上述定义中,对于给定的s和a,如果s′是唯一的,则称该转移系统是确定的;反之,如果s′不唯一,则称该转移系统是不确定的.上述形式化的转移系统最终需要通过规划定义语言来描述,才能使用规划系统进行求解.下面我们通过一个例子来说明一个具体的转移系统是怎样用规划语言来描述的.例1给出了概率规划大赛中一个基准领域的描述.国际规划大赛(Int’l Planning Competition,简称IPC)是智能规划主要的交流平台,自从2004年起,规划大赛分设了专门进行概率规划领域的比赛,即国际概率规划大赛(Int’l Probabilistic Planning Competition,简称IPPC).考虑到本文系统的通用性以及测试领域的代表性,我们采用国际概率规划大赛的基准

内容需要下载文档才能查看

54

领域进行介绍和测试. Journal of Software 软件学报 Vol.25, No.1, January 2014

例1:在国际概率规划大赛2008(IPPC 2008)的基准领域中,有一个Blocksworld领域(如图1所示),它是使用PPDDL定义的概率规划领域.其中,为了定义概率的和决策论的规划领域和问题,PPDDL增加了对概率效果的 支持.PPDDL中对概率效果的语法为(probabilistic p1 e1 ... pk ek),意思是效果ei会以概率pi发生,并且∑pi=1.

i=1k

例如,动作pick-up是不确定动作,它有两组效果,第1组效果发生的概率是3/4,第2组效果发生的概率为

1/4.

Fig.1 Blocksworld domain in the IPPC 2008

图1 IPPC 2008 Blocksworld领域

接下来,我们定义观测.一个状态s?S是P的一个子集,它包括了那些在该状态中为真的命题.一个文字是一个命题p∈P或者它的否定¬p.如果一个文字的真值随着状态的变化而变化,我们称其为流文字(fluent literals),反之,称为非流文字(non-fluent literals).例如,在Blocksworld领域中,on(A,B)在当前状态下为真,在应用了动作pickup(A,B)之后,在下一个状态下为假,因此,on(A,B)是流文字.而block(A)在任何状态下都为真,因此它不是流文字.而我们需要观测的显然是流文字,在这里,一个观测变量就是一个流文字.在已有的研究中,一个观测可以定义成动作[4],也可以定义成一个观测变量构成的逻辑公式[5].当定义成动作时,观测o是一个序对?pre(o),obs(o)?,其中,pre(o)和obs(o)都是命题集合,该定义表明:当pre(o)?s成立时,可以观测到obs(o)中命题的真值.这样定义的好处是把观测动作当成领域动作一样来处理.而当定义成逻辑公式时,观测o是观测变量集合L的一个合取范式(conjunctive normal form,简称CNF),它表明:每个合取项在当前状态s下的真值为真,其中,合取项是由观测变量组成的逻辑公式.这样定义的好处是便于向状态中添加经过观测而确立的命题.本文采用观测的第2种定义,并且为了简化处理,限定每个合取项至多由一个观测变量组成.

定义2. 给定状态s,一个观测o是在观测变量集合L(即流文字集合)上受限的合取范式,即o=l1∧l1∧…∧lk,其中,li∈L,1≤i≤k.观测o表明,li(1≤i≤k)在s中的真值为真.

最后,我们定义本文的学习问题.在现实世界的某些应用中,一个agent有可能对周围的环境是一无所知的,只能通过与环境交互来获取环境的信息.因此,在本文的学习问题中,转移系统的各组成部分可能是完全不知道的,学习目标是通过给定的动作-观测系列来获取转移系统的核心部分——转换关系.此外,若无特别说明,本文中所有的观测都假设为准确的.

定义3. 一个在部分观测领域学习不确定动作模型的问题是,从一个t步动作-观测序列?ai,oi?(1≤i≤t)中学习转移系统中转换关系R的子集.

内容需要下载文档才能查看

饶东宁 等:在部分观测环境下的不确定动作模型学习

55

为了更好地描述上述学习问题的输入,例2给出了IPPC 2008 Blocksworld领域的一个实例(instance)产生的?动作,观测?序列片段.

例2:求解例1中问题的?动作,观测?序列的片段如图2所示.其中,第1行表示动作pick-up(b4,b1),第2行~第11行表示执行完该动作所做的观测,该观测表明哪些文字在应用动作pick-up(b4,b1)之后的状态里为真,例如on-table(b1),clear(b1),holding(b4)的真值为真等等

.

Fig.2 A series of actions and observations for Example 1

图2 例1中问题产生的?动作,观测?序列

3 学习不确定动作模型

为了解决本文的学习问题,我们首先要从动作-观测序列中建立状态序列,并且计算每个命题在其中成立的概率;然后,我们会先学习每个动作的前提,再学习每个动作的多个效果.得到的状态序列以及学习到的动作即可构成转换关系中的序对?s,a,s′?.

3.1 建立状态序列

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

假定1(最少修改假设). 给定一个文字l和一个t步动作-观测序列?ai,oi?(1≤i≤t),并且假设在动作ai之前的状态是si?1.如果l∈oi并且对?j(0<j<i)有l?oj成立,则有l?sj成立.另外,如果l∈oi,并且对?j(i<j≤t)有l?oj成立,则有l∈sj成立.

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

假定2(均等机会假设). 给定一个文字l和一个t步动作-观测序列?ai,oi?(1≤i≤t),并且假设在动作ai之前的状态是si?1.如果对于1≤j<i≤t,有l∈oi且¬l∈oj,并且对?k(j<k<i)有l?ok且¬l?ok,则l∈sk的概率是

?1?1∑?1?i?j?i?j.

m=0??

做出假设2的原因是:在建立状态序列的时候,动作的效果是未知的,因此无法判定具体是在哪一步产生相应的变化.那么,我们只能假定每个动作都有相同的机会去改变一个文字.如假定2所述,当j<i且l∈oi和¬l∈oj

1时,aj+1,…,ai均有的概率使得l为真,那么l∈sk(j<k<i)的概率为 i?jk?j?1m