基于眾包模式的開(kāi)放式規(guī)劃問(wèn)題研究

高 潔,卓漢逵,劉亞松,李 磊

(1.中山大學(xué)信息科學(xué)與技術(shù)學(xué)院,廣東廣州 510275； 2.吉林大學(xué)珠海學(xué)院,廣東珠海 519041)

?

基于眾包模式的開(kāi)放式規(guī)劃問(wèn)題研究

高 潔1,2,卓漢逵1,劉亞松2,李 磊1

(1.中山大學(xué)信息科學(xué)與技術(shù)學(xué)院,廣東廣州 510275； 2.吉林大學(xué)珠海學(xué)院,廣東珠海 519041)

在開(kāi)放世界中求解智能規(guī)劃問(wèn)題往往是比較困難的,這是由于在開(kāi)放世界中,某些對(duì)象可能是未知的,因而在搜索規(guī)劃解時(shí)需要考慮不同的可能性.一種解決的方法是使用傳感器觀察未知的對(duì)象,而該方法使用的前提是傳感器能夠保證獲取規(guī)劃所需的所有信息.與以往工作不同的是，本文考慮利用外部人士(Crowd)求解規(guī)劃問(wèn)題.假設(shè)存在一些外部人士可以為開(kāi)放世界中某個(gè)規(guī)劃問(wèn)題提供必要的信息，然而在實(shí)際情況下,某些外部人士提供的信息可能是具有欺騙性的,如何使用此類信息求解規(guī)劃問(wèn)題是本文關(guān)注的重點(diǎn).針對(duì)此類問(wèn)題,本文提出了一個(gè)新穎的求解方法,首先獲取一個(gè)求解開(kāi)放世界下的規(guī)劃問(wèn)題所需的帶有變量的命題公式集合,然后根據(jù)外部人士對(duì)命題公式的標(biāo)注估計(jì)出變量所取的值,從而將開(kāi)放世界中的規(guī)劃問(wèn)題轉(zhuǎn)化為一般的規(guī)劃問(wèn)題求解.最后通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的有效性.

智能規(guī)劃;眾包;開(kāi)放世界

電子學(xué)報(bào)URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.036

1 引言

智能規(guī)劃[1,2]是人工智能研究領(lǐng)域近年來(lái)發(fā)展起來(lái)的一個(gè)熱門分支.目前智能規(guī)劃研究主要集中在封閉世界假設(shè)的前提下進(jìn)行,這是由于在開(kāi)放世界中求解規(guī)劃問(wèn)題往往是比較困難的.在開(kāi)放世界中,某些對(duì)象可能是未知的,因而在搜索規(guī)劃解時(shí)需要考慮未知對(duì)象的各種可能信息.一種解決的方法是在規(guī)劃器上安裝傳感器,在搜索規(guī)劃解的過(guò)程中,利用傳感器所獲得的未知對(duì)象的相關(guān)信息再進(jìn)行規(guī)劃[3,4].這種規(guī)劃方法使用的前提是假設(shè)傳感器可以感知規(guī)劃所需的所有信息.然而在開(kāi)放世界中,在規(guī)劃任務(wù)給出之前,很難確定所需傳感器的個(gè)數(shù)與類型,因而也無(wú)法感知規(guī)劃所需的所有信息.

受眾包模式[5](Crowdsource)的啟發(fā),我們嘗試?yán)帽娙说闹腔蹃?lái)解決規(guī)劃問(wèn)題,假設(shè)存在一些外部人士能夠在開(kāi)放世界中為規(guī)劃問(wèn)題提供相應(yīng)的信息.根據(jù)文獻(xiàn)[5]中的定義,眾包描述了一種新的工作模式,即企業(yè)或機(jī)構(gòu)利用一個(gè)較大的人際網(wǎng)絡(luò)通過(guò)公開(kāi)召集方式將某項(xiàng)工作分配出去.該項(xiàng)工作可能是通過(guò)集體完成,也可能是由某個(gè)人單獨(dú)完成.目前已有一些成功的普遍型眾包平臺(tái)問(wèn)世,例如亞馬遜土耳其機(jī)器人*www.mturk.com；也有一些專業(yè)型的眾包平臺(tái),例如呼叫中心*www.liveops.com.眾包模式已應(yīng)用在各種問(wèn)題中,例如口語(yǔ)翻譯[6],書寫辨識(shí)[7],故事生成[8],以及機(jī)器學(xué)習(xí)中訓(xùn)練數(shù)據(jù)標(biāo)示[9]等方面.

目前在規(guī)劃問(wèn)題中使用眾包模式還較為少見(jiàn),但是在規(guī)劃領(lǐng)域中已產(chǎn)生了一些與眾包模式有關(guān)的應(yīng)用,例如眾包模式下行程規(guī)劃問(wèn)題[10].一個(gè)行程由有序的動(dòng)作序列組成,在整個(gè)過(guò)程中按照次序依次執(zhí)行動(dòng)作.眾人利用他們的知識(shí)與經(jīng)驗(yàn)求解行程規(guī)劃問(wèn)題.與求解眾包模式下的行程規(guī)劃問(wèn)題不同的是,我們不要求眾人具備求解規(guī)劃問(wèn)題的能力,而僅僅要求眾人能夠提供求解規(guī)劃問(wèn)題所需的“資源”,相對(duì)而言這是比較容易的任務(wù).在規(guī)劃過(guò)程中,開(kāi)發(fā)一個(gè)可以集合眾人智慧的規(guī)劃系統(tǒng)是一件非常有意義的工作,同時(shí)也非常具有挑戰(zhàn)性,這是由于我們需要考慮到眾人意見(jiàn)的無(wú)序性與矛盾性.

在本文中,我們提出了COP算法(Crowdsourced Open Planning),即利用眾人的知識(shí)解決開(kāi)放世界中的規(guī)劃問(wèn)題.具體來(lái)說(shuō),COP算法分成兩個(gè)主要步驟,COP算法首先獲得一個(gè)求解開(kāi)放世界中的規(guī)劃問(wèn)題所需的帶變量的命題公式集合,然后由外部人士對(duì)命題公式進(jìn)行標(biāo)注,再根據(jù)標(biāo)注值估計(jì)變量所取的值,從而將開(kāi)放世界中的規(guī)劃問(wèn)題轉(zhuǎn)化為一般的規(guī)劃問(wèn)題求解.在假設(shè)開(kāi)放世界中的規(guī)劃問(wèn)題可解的前提下,COP算法將重復(fù)進(jìn)行取值步驟,直到求得規(guī)劃問(wèn)題的規(guī)劃解或超過(guò)設(shè)定的標(biāo)注公式個(gè)數(shù)的上限.

2 相關(guān)工作

開(kāi)放世界中的規(guī)劃問(wèn)題[11]是指在初始狀態(tài)，目標(biāo)狀態(tài)等信息不完整情況下的規(guī)劃問(wèn)題.利用封閉世界中的規(guī)劃器去求解開(kāi)放世界中的規(guī)劃問(wèn)題是相當(dāng)困難的事,這是由于假設(shè)世界是封閉的,或者假設(shè)可以獲取所有缺失的信息以將開(kāi)放世界轉(zhuǎn)變?yōu)榉忾]世界,都是錯(cuò)誤的.

Babaian等人[12]提出了PSIPLAN知識(shí)表示體系,可以用于有效地在開(kāi)放世界中表示規(guī)劃域.已有的規(guī)劃系統(tǒng)[3,13]通過(guò)檢測(cè)動(dòng)作執(zhí)行狀態(tài)并利用傳感器的感知能力找到不一致的執(zhí)行狀態(tài),再進(jìn)行規(guī)劃修改或再規(guī)劃來(lái)解決開(kāi)放世界中的規(guī)劃問(wèn)題.Nareyek等人[14]使用結(jié)構(gòu)性的限制可滿足條件來(lái)構(gòu)造規(guī)劃結(jié)構(gòu)以處理開(kāi)放式規(guī)劃問(wèn)題.Talamadupula[15]等人表明了團(tuán)隊(duì)問(wèn)題中處理開(kāi)放世界問(wèn)題的必要性,并給出了條件目標(biāo)的定義.這些系統(tǒng)都依賴于傳感器的感知能力,與其不同之處在于,我們旨在利用眾人的知識(shí)來(lái)確定初始狀態(tài)或目標(biāo)狀態(tài)中的不確定信息.

為了獲得規(guī)劃所需的條件,我們采用眾包模式求解開(kāi)放世界中的規(guī)劃問(wèn)題.眾包模式首先被用于在數(shù)據(jù)挖掘時(shí)提高訓(xùn)練數(shù)據(jù)標(biāo)簽的正確性[16].Raykar[17]等人提出了一種模型,其中反映工人準(zhǔn)確性的參數(shù)依賴于正確答案.雖然眾包模式已被大量應(yīng)用于不同領(lǐng)域,但是在規(guī)劃領(lǐng)域中的應(yīng)用還是非常少見(jiàn)的.作為第一個(gè)探索眾包模式在智能規(guī)劃領(lǐng)域中應(yīng)用的工作,Talamadupula等人[18]提出了一種通用框架,奠定了眾包模式規(guī)劃問(wèn)題的基礎(chǔ).Manikonda[19]等人開(kāi)發(fā)了一套旅行規(guī)劃生成系統(tǒng)AI-MIX，其思想是使用自動(dòng)檢測(cè)的方法提高眾包模式所生成的行程規(guī)劃解的質(zhì)量.卓漢逵等人[20]給出了一種稱為CAMA的動(dòng)作模型學(xué)習(xí)算法，用于利用眾包模式獲取動(dòng)作模型的前提條件與動(dòng)作效果.本文提出了在開(kāi)放世界中,當(dāng)初始狀態(tài)與目標(biāo)狀態(tài)中包含未知信息時(shí),一種基于眾包模式的規(guī)劃問(wèn)題求解方法.

3 開(kāi)放式規(guī)劃問(wèn)題

一般的規(guī)劃問(wèn)題定義為一個(gè)三元組(s0,g,U),這里s0表示初始狀態(tài),g表示目標(biāo)狀態(tài),都由一個(gè)命題公式集合組成.U表示一個(gè)STRIPS動(dòng)作模型集,每個(gè)動(dòng)作模型由一個(gè)四元組(a,PRE,ADD,DEL)構(gòu)成,這里a表示一個(gè)動(dòng)作模式,包括動(dòng)作名稱及參數(shù)信息(零個(gè)或者多個(gè)).PRE是動(dòng)作a的前提條件列表,指明了實(shí)施動(dòng)作a之前應(yīng)滿足的條件.ADD表示增加效果列表,指明了實(shí)施動(dòng)作a以后增加的新效果.DEL表示刪除效果列表,指明了實(shí)施動(dòng)作a以后刪除的效果.這里所涉及的動(dòng)作模型為STRIPS模型.規(guī)劃問(wèn)題的規(guī)劃解即為從初始狀態(tài)到目標(biāo)狀態(tài)所需執(zhí)行的動(dòng)作序列.

表1 一個(gè)開(kāi)放式規(guī)劃問(wèn)題的例子

4 COP算法步驟

我們?cè)谒惴?中給出了COP算法的整體框架,下面的小節(jié)中我們將詳細(xì)闡述COP算法的每個(gè)步驟.

4.1 構(gòu)建帶變量的命題公式組

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

4.2 根據(jù)Ti,構(gòu)建待標(biāo)注公式集合Yi

在COP算法的第二步,我們需獲取一個(gè)待標(biāo)注的命題公式集合.在第i步所獲得的帶變量的命題公式集合Ti中,將命題公式中的變量帶入O中可以取到的值,從而獲得完全例化的命題公式以供外部人士標(biāo)注.當(dāng)兩個(gè)命題公式包含相同變量時(shí),為達(dá)到標(biāo)注公式個(gè)數(shù)極小的目的，我們隨機(jī)選擇其中的一個(gè)命題公式進(jìn)行例化.最后將獲得的所有完全例化的命題公式集合記為Yi，并由外部人士進(jìn)行標(biāo)注.下面,我們用一個(gè)例子從直觀上解釋一下該步驟的主要思想.依然用表1中的例子來(lái)解釋.應(yīng)用以上步驟以后,我們獲得了一個(gè)可以與初始狀態(tài)相匹配的中間狀態(tài),由命題公式

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

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

組成,選取其中帶有變量的命題公式ontable(?y)與clear(?y).由于這兩個(gè)公式具有相同的變量,為達(dá)到標(biāo)注公式個(gè)數(shù)極小化的目的,我們隨機(jī)選擇其中一個(gè)公式ontable(?y)作為待標(biāo)注公式.假設(shè)包含所有可能物體的集合O={A,B,C,D},除去已在中間狀態(tài)中出現(xiàn)的物體A,C后,變量?y可以取值B或D.因而得到待標(biāo)注公式ontable(B)與ontable(D).

4.3 由外部人士標(biāo)注公式集合Yi,并獲取真值表Ki

我們將需要標(biāo)注的命題公式映射為一個(gè)調(diào)查表，并用相同的調(diào)查表模板來(lái)表示每一個(gè)謂詞.例如,我們將命題公式“ontable(B)”映射為

“Is the blockBon the table?”.

一個(gè)標(biāo)注者只可以選擇“Yes”或“No”其中之一作為回復(fù).我們付給標(biāo)注者10分錢作為對(duì)每個(gè)命題的報(bào)酬.每個(gè)標(biāo)注者只能標(biāo)注每個(gè)命題公式一次.每個(gè)調(diào)查表由二十個(gè)標(biāo)注者分別給出標(biāo)注.冗余度用于降低標(biāo)注者給予錯(cuò)誤或惡意回復(fù)的可能性.另外,我們也可以利用命題之間的互斥約束減少調(diào)查表的數(shù)量,例如clear(A)和on(B,A)是彼此互斥的,我們只需取其中的一個(gè)調(diào)查表用于標(biāo)注.最后獲得一個(gè)待標(biāo)注公式的真值表,記為Ki.

4.4 計(jì)算Yi中各個(gè)公式的值

另一方面,若為假,則對(duì)于第j個(gè)標(biāo)注者的正確負(fù)比率(True negative rate)TNj定義為標(biāo)注者標(biāo)注該公式為0的概率,即

利用線性辨別函數(shù),正例的概率可以用一個(gè)logistic函數(shù)來(lái)表示,即

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

這里需估計(jì)參數(shù)ω以及正確正比率P=〈TP1,…,TPR〉和正確負(fù)比率N=〈TN1,…,TNR〉.設(shè)θ={ω,P,N},訓(xùn)練數(shù)據(jù)集D的概率可以定義為

這里

pi=σ(ωTxi),

通過(guò)最大化對(duì)數(shù)似然函數(shù),應(yīng)用EM算法[25]估計(jì)參數(shù)θ,即

可以得到期望值如下：

進(jìn)而可得

且

類似地,可得b1與b2的表達(dá)式.

在本文中,每個(gè)實(shí)例實(shí)際上是一個(gè)公式,并不存在屬性向量xi,我們希望由多個(gè)注釋者提供的標(biāo)注獲取公式真實(shí)值的一個(gè)估計(jì)值.因此我們用p=prob[z=1]來(lái)估計(jì)正類的普遍性,并假設(shè)普遍性的β先驗(yàn)概率為β(p|a1,a2).EM算法可以簡(jiǎn)化為以下步驟：

(2)給定μi,正確正比率與正確負(fù)比率可以估計(jì)為：

4.5 更新并求解規(guī)劃問(wèn)題

5 實(shí)驗(yàn)驗(yàn)證

5.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)標(biāo)準(zhǔn)

這里#IdenticalSolution(SOL,SOL′)表示將SOL與SOL′相比較,其中相同解的個(gè)數(shù).

5.2 實(shí)驗(yàn)結(jié)果及分析

我們首先估計(jì)COP算法的準(zhǔn)確率.我們?cè)O(shè)定物體個(gè)數(shù)為10個(gè),并使得變量個(gè)數(shù)的比率α從0.1變化到0.5,我們運(yùn)行COP算法以測(cè)試問(wèn)題的準(zhǔn)確性.從圖2中曲線可知,隨著變量個(gè)數(shù)比率α的增加,三個(gè)測(cè)試領(lǐng)域中的求解準(zhǔn)確率基本上呈逐漸降低的趨勢(shì),這與我們的直覺(jué)是一致的.這是由于變量個(gè)數(shù)比率α越大,開(kāi)放式規(guī)劃問(wèn)題中所含有的不確定信息越多.另外如圖1所示,當(dāng)變量比率低于0.3時(shí),求解準(zhǔn)確率不低于70%.另外,我們希望獲取隨著物體個(gè)數(shù)的變化,COP算法準(zhǔn)確率的變化趨勢(shì).設(shè)物體個(gè)數(shù)從4個(gè)變化到13個(gè),隨著變量個(gè)數(shù)比率α的變化,計(jì)算COP算法準(zhǔn)確率的平均值,其結(jié)果如表2～表4所示.Mobj表示物體的個(gè)數(shù).這里Mobj∈[4,7]所對(duì)應(yīng)的列表示當(dāng)物體個(gè)數(shù)從4個(gè)變化到7個(gè)時(shí),對(duì)應(yīng)變量個(gè)數(shù)比率α,所求得的準(zhǔn)確率的平均值,同理對(duì)于Mobj∈[8,10]與Mobj∈[11,13]所對(duì)應(yīng)的列也表示相同的意思.從以上表格中可知,在每個(gè)規(guī)劃域中,隨著未知變量比率的提高(從0.1提高到0.5),COP算法的精確率相應(yīng)地減少.這是因?yàn)槲粗兞繑?shù)量的增加,使得帶有未知變量的命題公式數(shù)量增加,這將導(dǎo)致未知信息量增加,從而使得算法COP的精確率降低.這里我們?cè)O(shè)定外部標(biāo)注公式總次數(shù)最大閾值N=100.

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

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

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

我們也測(cè)試了所需支付注釋者勞務(wù)費(fèi)的情況.假設(shè)注釋者勞務(wù)費(fèi)僅僅取決于由COP算法所產(chǎn)生的待標(biāo)注命題公式的數(shù)量,而不考慮標(biāo)注不同類型的待標(biāo)注命題公式的難度.待標(biāo)注命題公式的數(shù)量取決于物體個(gè)數(shù)與變量個(gè)數(shù)比率兩個(gè)因素.我們通過(guò)改變物體個(gè)數(shù),并設(shè)定變量個(gè)數(shù)比率以計(jì)算所需標(biāo)注命題公式的個(gè)數(shù),結(jié)果如圖2～圖4所示.由圖2～圖4中的圖像可知,隨著物體個(gè)數(shù)增多,無(wú)論變量個(gè)數(shù)比率如何,一般來(lái)說(shuō)待標(biāo)注命題公式的個(gè)數(shù)也逐漸增多.這是因?yàn)槲矬w個(gè)數(shù)越多,變量賦值方式越多,從而導(dǎo)致需標(biāo)注命題個(gè)數(shù)越多.同樣地,變量個(gè)數(shù)比率越大,所有可能的變量組合方式也越多,也導(dǎo)致需標(biāo)注命題個(gè)數(shù)越多.

6 結(jié)論

目前智能規(guī)劃研究主要集中在封閉世界假設(shè)的前提下,對(duì)于開(kāi)放世界中的規(guī)劃問(wèn)題鮮有研究.目前開(kāi)放世界中的規(guī)劃問(wèn)題一般采用了傳感器獲取未知信息或者在給定預(yù)先假設(shè)的前提下進(jìn)行求解.在實(shí)際問(wèn)題中,開(kāi)放世界中的規(guī)劃問(wèn)題更加具有一般性,仍然是當(dāng)前規(guī)劃研究的難點(diǎn).本文關(guān)注于采用眾包模式解決開(kāi)放世界中的規(guī)劃問(wèn)題.我們提出了基于眾包模式的開(kāi)放式規(guī)劃算法COP,有效地解決了初始狀態(tài)與目標(biāo)狀態(tài)中帶有變量的開(kāi)放式規(guī)劃問(wèn)題,并利用三個(gè)改造后的規(guī)劃域驗(yàn)證了算法的有效性.今后,我們將研究如何改善COP算法的性能,以期提高COP算法有效比例.

[1]胡亮,解男男,等.基于智能規(guī)劃的多步攻擊場(chǎng)景識(shí)別算法[J].電子學(xué)報(bào),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]王楨珍,武小悅,劉忠.一種基于智能規(guī)劃的信息安全風(fēng)險(xiǎn)過(guò)程建模方法[J].電子學(xué)報(bào),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年畢業(yè)于加拿大滑鐵盧大學(xué)數(shù)學(xué)學(xué)院，其后在吉林大學(xué)珠海學(xué)院工作，2008年到中山大學(xué)信息科學(xué)與技術(shù)學(xué)院學(xué)習(xí)，獲工學(xué)博士學(xué)位，目前從事人工智能方面的有關(guān)研究.

E-mail:jiegao26@163.com

卓漢逵 男,1982年生于廣東陸豐.中山大學(xué)超級(jí)計(jì)算學(xué)院副教授，博士.研究方向?yàn)橹悄芤?guī)劃、數(shù)據(jù)挖掘.

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；責(zé)任編輯：藍(lán)紅杰

國(guó)家自然科學(xué)基金(No.61309011);高?；究蒲袠I(yè)務(wù)費(fèi)(No.14lgzd06)

TP301

A

0372-2112 (2016)08-2025-08