基于众包模式的开放式规划问题研究

高 洁,卓汉逵,刘亚松,李 磊

(1.中山大学信息科学与技术学院,广东广州 510275； 2.吉林大学珠海学院,广东珠海 519041)



基于众包模式的开放式规划问题研究

高 洁1,2,卓汉逵1,刘亚松2,李 磊1

(1.中山大学信息科学与技术学院,广东广州 510275； 2.吉林大学珠海学院,广东珠海 519041)

在开放世界中求解智能规划问题往往是比较困难的,这是由于在开放世界中,某些对象可能是未知的,因而在搜索规划解时需要考虑不同的可能性.一种解决的方法是使用传感器观察未知的对象,而该方法使用的前提是传感器能够保证获取规划所需的所有信息.与以往工作不同的是，本文考虑利用外部人士(Crowd)求解规划问题.假设存在一些外部人士可以为开放世界中某个规划问题提供必要的信息，然而在实际情况下,某些外部人士提供的信息可能是具有欺骗性的,如何使用此类信息求解规划问题是本文关注的重点.针对此类问题,本文提出了一个新颖的求解方法,首先获取一个求解开放世界下的规划问题所需的带有变量的命题公式集合,然后根据外部人士对命题公式的标注估计出变量所取的值,从而将开放世界中的规划问题转化为一般的规划问题求解.最后通过实验验证了该算法的有效性.

智能规划;众包;开放世界

电子学报URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.036

1 引言

智能规划[1,2]是人工智能研究领域近年来发展起来的一个热门分支.目前智能规划研究主要集中在封闭世界假设的前提下进行,这是由于在开放世界中求解规划问题往往是比较困难的.在开放世界中,某些对象可能是未知的,因而在搜索规划解时需要考虑未知对象的各种可能信息.一种解决的方法是在规划器上安装传感器,在搜索规划解的过程中,利用传感器所获得的未知对象的相关信息再进行规划[3,4].这种规划方法使用的前提是假设传感器可以感知规划所需的所有信息.然而在开放世界中,在规划任务给出之前,很难确定所需传感器的个数与类型,因而也无法感知规划所需的所有信息.

受众包模式[5](Crowdsource)的启发,我们尝试利用众人的智慧来解决规划问题,假设存在一些外部人士能够在开放世界中为规划问题提供相应的信息.根据文献[5]中的定义,众包描述了一种新的工作模式,即企业或机构利用一个较大的人际网络通过公开召集方式将某项工作分配出去.该项工作可能是通过集体完成,也可能是由某个人单独完成.目前已有一些成功的普遍型众包平台问世,例如亚马逊土耳其机器人*www.mturk.com；也有一些专业型的众包平台,例如呼叫中心*www.liveops.com.众包模式已应用在各种问题中,例如口语翻译[6],书写辨识[7],故事生成[8],以及机器学习中训练数据标示[9]等方面.

目前在规划问题中使用众包模式还较为少见,但是在规划领域中已产生了一些与众包模式有关的应用,例如众包模式下行程规划问题[10].一个行程由有序的动作序列组成,在整个过程中按照次序依次执行动作.众人利用他们的知识与经验求解行程规划问题.与求解众包模式下的行程规划问题不同的是,我们不要求众人具备求解规划问题的能力,而仅仅要求众人能够提供求解规划问题所需的“资源”,相对而言这是比较容易的任务.在规划过程中,开发一个可以集合众人智慧的规划系统是一件非常有意义的工作,同时也非常具有挑战性,这是由于我们需要考虑到众人意见的无序性与矛盾性.

在本文中,我们提出了COP算法(Crowdsourced Open Planning),即利用众人的知识解决开放世界中的规划问题.具体来说,COP算法分成两个主要步骤,COP算法首先获得一个求解开放世界中的规划问题所需的带变量的命题公式集合,然后由外部人士对命题公式进行标注,再根据标注值估计变量所取的值,从而将开放世界中的规划问题转化为一般的规划问题求解.在假设开放世界中的规划问题可解的前提下,COP算法将重复进行取值步骤,直到求得规划问题的规划解或超过设定的标注公式个数的上限.

2 相关工作

开放世界中的规划问题[11]是指在初始状态，目标状态等信息不完整情况下的规划问题.利用封闭世界中的规划器去求解开放世界中的规划问题是相当困难的事,这是由于假设世界是封闭的,或者假设可以获取所有缺失的信息以将开放世界转变为封闭世界,都是错误的.

Babaian等人[12]提出了PSIPLAN知识表示体系,可以用于有效地在开放世界中表示规划域.已有的规划系统[3,13]通过检测动作执行状态并利用传感器的感知能力找到不一致的执行状态,再进行规划修改或再规划来解决开放世界中的规划问题.Nareyek等人[14]使用结构性的限制可满足条件来构造规划结构以处理开放式规划问题.Talamadupula[15]等人表明了团队问题中处理开放世界问题的必要性,并给出了条件目标的定义.这些系统都依赖于传感器的感知能力,与其不同之处在于,我们旨在利用众人的知识来确定初始状态或目标状态中的不确定信息.

为了获得规划所需的条件,我们采用众包模式求解开放世界中的规划问题.众包模式首先被用于在数据挖掘时提高训练数据标签的正确性[16].Raykar[17]等人提出了一种模型,其中反映工人准确性的参数依赖于正确答案.虽然众包模式已被大量应用于不同领域,但是在规划领域中的应用还是非常少见的.作为第一个探索众包模式在智能规划领域中应用的工作,Talamadupula等人[18]提出了一种通用框架,奠定了众包模式规划问题的基础.Manikonda[19]等人开发了一套旅行规划生成系统AI-MIX，其思想是使用自动检测的方法提高众包模式所生成的行程规划解的质量.卓汉逵等人[20]给出了一种称为CAMA的动作模型学习算法，用于利用众包模式获取动作模型的前提条件与动作效果.本文提出了在开放世界中,当初始状态与目标状态中包含未知信息时,一种基于众包模式的规划问题求解方法.

3 开放式规划问题

一般的规划问题定义为一个三元组(s0,g,U),这里s0表示初始状态,g表示目标状态,都由一个命题公式集合组成.U表示一个STRIPS动作模型集,每个动作模型由一个四元组(a,PRE,ADD,DEL)构成,这里a表示一个动作模式,包括动作名称及参数信息(零个或者多个).PRE是动作a的前提条件列表,指明了实施动作a之前应满足的条件.ADD表示增加效果列表,指明了实施动作a以后增加的新效果.DEL表示删除效果列表,指明了实施动作a以后删除的效果.这里所涉及的动作模型为STRIPS模型.规划问题的规划解即为从初始状态到目标状态所需执行的动作序列.

表1 一个开放式规划问题的例子

4 COP算法步骤

我们在算法1中给出了COP算法的整体框架,下面的小节中我们将详细阐述COP算法的每个步骤.

4.1 构建带变量的命题公式组

on(?x,A),clear(?x),ontable(A)

4.2 根据Ti,构建待标注公式集合Yi

在COP算法的第二步,我们需获取一个待标注的命题公式集合.在第i步所获得的带变量的命题公式集合Ti中,将命题公式中的变量带入O中可以取到的值,从而获得完全例化的命题公式以供外部人士标注.当两个命题公式包含相同变量时,为达到标注公式个数极小的目的，我们随机选择其中的一个命题公式进行例化.最后将获得的所有完全例化的命题公式集合记为Yi，并由外部人士进行标注.下面,我们用一个例子从直观上解释一下该步骤的主要思想.依然用表1中的例子来解释.应用以上步骤以后,我们获得了一个可以与初始状态相匹配的中间状态,由命题公式

ontable(Y),ontable(A),clear(Y),

on(C,A),clear(C),handempty

组成,选取其中带有变量的命题公式ontable(?y)与clear(?y).由于这两个公式具有相同的变量,为达到标注公式个数极小化的目的,我们随机选择其中一个公式ontable(?y)作为待标注公式.假设包含所有可能物体的集合O={A,B,C,D},除去已在中间状态中出现的物体A,C后,变量?y可以取值B或D.因而得到待标注公式ontable(B)与ontable(D).

4.3 由外部人士标注公式集合Yi,并获取真值表Ki

我们将需要标注的命题公式映射为一个调查表，并用相同的调查表模板来表示每一个谓词.例如,我们将命题公式“ontable(B)”映射为

“Is the blockBon the table?”.

一个标注者只可以选择“Yes”或“No”其中之一作为回复.我们付给标注者10分钱作为对每个命题的报酬.每个标注者只能标注每个命题公式一次.每个调查表由二十个标注者分别给出标注.冗余度用于降低标注者给予错误或恶意回复的可能性.另外,我们也可以利用命题之间的互斥约束减少调查表的数量,例如clear(A)和on(B,A)是彼此互斥的,我们只需取其中的一个调查表用于标注.最后获得一个待标注公式的真值表,记为Ki.

4.4 计算Yi中各个公式的值

另一方面,若为假,则对于第j个标注者的正确负比率(True negative rate)TNj定义为标注者标注该公式为0的概率,即

利用线性辨别函数,正例的概率可以用一个logistic函数来表示,即

p(y=1|x,ω)=σ(ωTx),

这里需估计参数ω以及正确正比率P=〈TP1,…,TPR〉和正确负比率N=〈TN1,…,TNR〉.设θ={ω,P,N},训练数据集D的概率可以定义为

这里

pi=σ(ωTxi),

通过最大化对数似然函数,应用EM算法[25]估计参数θ,即

可以得到期望值如下：

进而可得

且

类似地,可得b1与b2的表达式.

在本文中,每个实例实际上是一个公式,并不存在属性向量xi,我们希望由多个注释者提供的标注获取公式真实值的一个估计值.因此我们用p=prob[z=1]来估计正类的普遍性,并假设普遍性的β先验概率为β(p|a1,a2).EM算法可以简化为以下步骤：

(2)给定μi,正确正比率与正确负比率可以估计为：

4.5 更新并求解规划问题

5 实验验证

5.1 实验数据与评价标准

这里#IdenticalSolution(SOL,SOL′)表示将SOL与SOL′相比较,其中相同解的个数.

5.2 实验结果及分析

我们首先估计COP算法的准确率.我们设定物体个数为10个,并使得变量个数的比率α从0.1变化到0.5,我们运行COP算法以测试问题的准确性.从图2中曲线可知,随着变量个数比率α的增加,三个测试领域中的求解准确率基本上呈逐渐降低的趋势,这与我们的直觉是一致的.这是由于变量个数比率α越大,开放式规划问题中所含有的不确定信息越多.另外如图1所示,当变量比率低于0.3时,求解准确率不低于70%.另外,我们希望获取随着物体个数的变化,COP算法准确率的变化趋势.设物体个数从4个变化到13个,随着变量个数比率α的变化,计算COP算法准确率的平均值,其结果如表2～表4所示.Mobj表示物体的个数.这里Mobj∈[4,7]所对应的列表示当物体个数从4个变化到7个时,对应变量个数比率α,所求得的准确率的平均值,同理对于Mobj∈[8,10]与Mobj∈[11,13]所对应的列也表示相同的意思.从以上表格中可知,在每个规划域中,随着未知变量比率的提高(从0.1提高到0.5),COP算法的精确率相应地减少.这是因为未知变量数量的增加,使得带有未知变量的命题公式数量增加,这将导致未知信息量增加,从而使得算法COP的精确率降低.这里我们设定外部标注公式总次数最大阈值N=100.

表2 在Blocks World域中COP算法精确率平均值

表3 在Depots域中COP算法精确率的平均值

表4 在Driverlog域中COP算法精确率的平均值

我们也测试了所需支付注释者劳务费的情况.假设注释者劳务费仅仅取决于由COP算法所产生的待标注命题公式的数量,而不考虑标注不同类型的待标注命题公式的难度.待标注命题公式的数量取决于物体个数与变量个数比率两个因素.我们通过改变物体个数,并设定变量个数比率以计算所需标注命题公式的个数,结果如图2～图4所示.由图2～图4中的图像可知,随着物体个数增多,无论变量个数比率如何,一般来说待标注命题公式的个数也逐渐增多.这是因为物体个数越多,变量赋值方式越多,从而导致需标注命题个数越多.同样地,变量个数比率越大,所有可能的变量组合方式也越多,也导致需标注命题个数越多.

6 结论

目前智能规划研究主要集中在封闭世界假设的前提下,对于开放世界中的规划问题鲜有研究.目前开放世界中的规划问题一般采用了传感器获取未知信息或者在给定预先假设的前提下进行求解.在实际问题中,开放世界中的规划问题更加具有一般性,仍然是当前规划研究的难点.本文关注于采用众包模式解决开放世界中的规划问题.我们提出了基于众包模式的开放式规划算法COP,有效地解决了初始状态与目标状态中带有变量的开放式规划问题,并利用三个改造后的规划域验证了算法的有效性.今后,我们将研究如何改善COP算法的性能,以期提高COP算法有效比例.

[1]胡亮,解男男,等.基于智能规划的多步攻击场景识别算法[J].电子学报,2013,41(9):1753-1759.

Hu Liang,Xie Nan-nan,et al.A multi-stage attack scenario recognition algorithm based on intelligent planning[J].Acta Electronica Sinica,2013,41(9):1753-1759.(in Chinese)

[2]王桢珍,武小悦,刘忠.一种基于智能规划的信息安全风险过程建模方法[J].电子学报,2008,36(S1):76-80,70.

Wang Zhen-zhen,Wu Xiao-yue,Liu Zhong.Aplanning-based method of risk process modeling for information security[J].Acta Electronica Sinica,2008,36(S1):76-80,70.(in Chinese)

[3]Knight R,Rabideau G,et al.Casper:Space exploration through continuous planning[J].Intelligent Systems,2001,16(5):70-75.

[4]Talamadupula K,Benton J,et al.Planning for human-robot teaming in open worlds[J].ACM Transactions on Intelligent Systems and Technology,2010,1(2):14-22.

[5]Howe J.The rise of crowdsourcing[J].Wired Magazine,2006,14(6):1-4.

[6]Liem B.An Iterative dual pathway structure for speech-to-text transcription[A].Hartman B, Proceedings of the 3rd Workshop on Human Computation[C].USA:AAAI,2011.1123-1131.

[7]Ouyang T.Bootstrapping personal gesture shortcuts with the wisdom of the crowd and handwriting recognition[A].Rosemary W,Proceedings of the 2012 ACM annual conference on Human Factors in Computing Systems[C].USA:ACM,2012.2895-2904.

[8]Li B.Story generation with crowdsourced plot graphs[A].Ferguson G,Proceedings of the 27th AAAI Conference on Artificial Intelligence[C].USA:AAAI,2013.598-604.

[9]Raykar V C.Ranking annotators for crowdsourced labeling tasks[A].Taylor J,Neural Information Processing Systems[C].USA:MIT,2011.1809-1817.

[10]Zhang,Haoqi.Human computation tasks with global constraints[A].Joseph A.Konstan,Proceedings of the SIGCHI Conference on Human Factors in Computing Systems[C].USA:ACM,2012.217-226.

[11]Kambhampati S.Model-lite Planning for the Web Age Masses:The challenges of planning with incomplete and evolving domain models[A].Ferguson G,Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence[C].USA:AAAI,2007.1112-1119.

[12]Babarian T,Schmolze G.Efficient Open World Reasoning for Planning[J].Logical Methods in Computer Science,2006,2:1-39.

[13]Lemai S,Ingrand F.Interleaving temporal planning and execution in robotics domains[A].Ferguson G,Proceedings of the Nineteenth AAAI Conference on Artificial Intelligence[C].USA:AAAI,2004.617-622.

[14]Nareyek A.Open World Planning as SCSP[M].USA:AAAI Press,2000.35-46.

[15]Talamadupula K,Kambhampati S,Schermerhorn P,Scheutz M.Planning for human-robot teaming in open worlds[J].ACM Transactions on Intelligent Systems and Technology,2010,1(2),14:1-24.

[16]Dawid A P,Skene A M.Maximum likelihood estimation of observer error-rates using the EM algorithm[J].Applied statistics,1979:20-28.

[17]Raykar V C,Yu S,Zhao L H,et al.Learning from crowds[J].The Journal of Machine Learning Research,2010,11:1297-1322.

[18]Talamadupula K.Herding the crowd:Automated planning for crowdsourced planning[A].Kristen Grauman,The First AAAI Conference on Human Computation and Crowdsourcing[C].USA:AAAI,2013.1121-1132.

[19]Manikonda L.AI-MIX:using automated planning to steer human workers towards better crowdsourced plans[A].Ferguson G,Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence[C].USA:AAAI,2014.3004-3009.

[20]Hankz Hankui Zhuo.Crowdsourced action model acquisition for planning[A].Ferguson G,Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence[C].USA:AAAI.2015.

高 洁 女,1978年9月出生，湖南新化人.2004年毕业于加拿大滑铁卢大学数学学院，其后在吉林大学珠海学院工作，2008年到中山大学信息科学与技术学院学习，获工学博士学位，目前从事人工智能方面的有关研究.

E-mail:jiegao26@163.com

卓汉逵 男,1982年生于广东陆丰.中山大学超级计算学院副教授，博士.研究方向为智能规划、数据挖掘.

E-mail:zhuohank@mail.sysu.edu.cn

Research on Crowdsourced Open Planning

GAO Jie1,2,,ZHUO Han-kui1,LIU Ya-song2,LI Lei1

(1.SchoolofInformationScienceandTechnology,SunYat-SenUniversity,Guangzhou,Guangdong510275,China；2.ZhuhaiCollege,JilinUniversity,Zhuhai,Guangdong519041,China)

Plan synthesis in an open world is challenging,since some objects in an open world might be unknown,then we need to consider various scenarios before planning.One way to solve this problem is to employ sensors to observe unknown objects,assuming the sensors are capable of correctly capturing all information needed for planning.Different with previous work,we turn to the crowd for help before doing planning.We assume there are abundant annotators available to provide information needed before planning,however there is possibly a substantial amount of discrepancy from the crowd in practice.It is thus challenging to solve the planning problem with possibly noisy information provided by the crowd.We propose a novel approach with two phases.We first build a set of propositions with variables,and collect values from crowd for those propositions.We then estimate the actual values of variables and transform the problem in an open world into a normal planning problem and solve it.Finally,we empirically exhibit the effectiveness of our approach.

automated planning;crowdsource;open world

2015-01-28;

2015-04-09；责任编辑：蓝红杰

国家自然科学基金(No.61309011);高校基本科研业务费(No.14lgzd06)

TP301

A

0372-2112 (2016)08-2025-08