[發明專利]一種基于POMDP模型的眾包平臺任務分配方法

有效

• 申請號: 201811254337.X
• 申請日: 2018-10-19
• 公開（公告）號: CN109409739B
• 公開（公告）日: 2021-10-26
• 發明（設計）人: 劉峰;夏志偉;張弛;曾虎雙
• 申請（專利權）人: 南京大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于POMDP模型的眾包平臺任務分配方法，該方法包括如下步驟：

1)準備階段

a)準備日常的數據，即歷史任務信息；

b)確定常數參數，包括工人等級數、任務種類數；

c)對歷史數據進行格式轉換，按照特定的數據格式，對數據進行預處理；

2)建模階段

a)根據應用的數據，確定POMDP模型中的簡單元素，包括狀態、動作、觀察、折扣因子；

b)根據數據集進行函數學習，完成POMDP模型中的復雜元素，包括收益函數、狀態轉移函數、觀察函數；

c)根據需要提供決策支持的任務種類，確定初始信念狀態；

d)將2-a)中的初步模型與2-b)中得到的函數以及2-c)中的初始信念狀態結合，得到最終的POMDP平臺模型；

e)根據標準POMDP模型文件的格式將POMDP平臺模型轉化為POMDP文件；

3)決策階段

a)使用POMDP求解程序求解2-e)中得到的POMDP文件，求解得到從信念狀態到動作映射的策略；

b)使用得到的決策，根據當前信念狀態得到最優動作；

c)執行最優動作，更新信念狀態信息，重復執行b)直至終止；

其中步驟1-c)所述的數據格式說明：

1)數據格式需要滿足特定的數據結構，首先定義的是一些集合；

任務種類集合T，工人等級集合L，任務完成質量集合Q＝{A，B，C，D}，評估結果集合B＝{true，false}；

2)以下是歷史信息的結構：

任務記錄集合M＝{m₁，m₂，...，m_k}中的每個元素包含了一次任務的全部信息，每條任務記錄mi＝{P，t，r}有其對應任務執行過程集合P＝{p₁，p₂，...，p_n}、任務種類t∈T以及任務請求方支付的酬勞對于每次任務執行過程p_i＝(t_i，l_i，c_i，b_i)，有對應的種類t_i，工人等級l_i，支付的酬勞c_i，評估結果b_i；其中種類t_i∈T，工人等級l_i∈L，支付酬勞關于評估結果b_i，當i＜n時，b_i＝false，當i＝n時，b_i＝true；

其中步驟2-a)所述的模型說明：

1)狀態，其集合以下表示為S：

一共有兩種類型的狀態，一種是正在執行中的狀態(q，t)，另一種是終止狀態，正在執行的狀態有兩個元素，完成質量q和任務種類t，因此正在執行中的狀態是種類和完成質量的笛卡爾積，數量是種類數乘以完成質量數，終止狀態表示任務被提交，已經返回給需求方；

2)動作，其集合以下表示為A：

一共有兩種類型的動作：分配和完成；

完成動作表示系統將任務終止，并返回給需求方；分配動作表示將任務分配給某一特定的工人群體，工人群體有兩個元素，種類t和等級l，因此分配動作的數量為種類數乘以等級數，這里工人的種類與任務種類相同；

3)觀察，其集合以下表示為Z：

一共有兩種觀察：true和false；

每次進行動作之后，眾包平臺都會對任務進行質量評估，評估通過則設觀察值為true，否則為false；其中2-b)的收益函數學習過程說明：

1)收益函數的格式為R：設轉移前狀態為s，動作為a，轉移后狀態為s’，關于動作a分情況討論；

2)如果動作a是分配動作，搜索動作a所對應的任務種類的所有任務執行記錄組成的集合M_a＝{m|m∈M，m的種類與a的種類相同}，在集合M_a的任務執行過程中獲取與動作a對應工人等級相同的任務執行過程組成的集合P_a＝{p|p∈m.P，m∈M’，p的工人等級與a的工人等級相同}，計算P_a平均支付酬勞，取負后為收益，如果P_a是空集，則設R為負無窮，即：

3)如果動作a是結束動作，如果狀態s為終止狀態，則R＝0，否則有狀態s＝(q，t)檢索狀態s所對應的任務種類中所有任務執行記錄組成的集合M_s＝{m|m∈M，m的種類與s的種類相同}，計算其平均酬勞，如果M_s是空集，則報錯，發生數據缺失，即：

其中2-b)的狀態轉移函數學習過程說明：

τ：設轉移前狀態為s，動作為a，轉移后狀態為s’，概率分情況討論：

1)首先關于動作a分類討論，如果動作a為完成動作，那么任務必定進入終止狀態，即對s’＝e，轉移概率τ＝1，對s’≠e時，概率τ＝0；

2)對于a是分配動作，關于轉移前狀態s分類討論，如果轉移前狀態s為終止狀態，那么類似情況1)，轉移后狀態s’也一定是終止狀態；如果轉移前狀態s不是終止狀態，此時動作a是分配動作，那么轉移后狀態一定不是終止狀態，即對轉移后狀態為終止狀態，轉移概率τ＝0；

3)最后一種情況是轉移前后狀態s和s’都不是終止狀態，動作a是分配動作；如果轉移前后狀態s和s’的任務種類不同，概率τ＝0；對于轉移前后狀態s和s’狀態任務種類相同，這里使用歷史數據進行學習，學習過程如下：

4)對于任意的任務種類X，從M中取出所有任務種類為X的任務記錄的集合M_X＝{m|m∈M，m的任務種類為X}，關于所有m∈M_X，考察執行序列P＝{p₁，p₂，...，p_n}，新設一個對應的躍遷集合U＝{u₁，u₂，...，u_n}，其中u_i表示p_i發生了質量躍遷的概率，即質量發生了提高的概率；初始質量為D，最終質量為A，發生了3次躍遷；故有在執行了p_n之后，必然發生了質量由B到A的躍遷，可以得到公式1，u_n＝1，以及公式2，u_i的值與p_i對應的工人等級l_i相關，不同工人等級對應的u_i與工人的平均酬勞線性相關，即可得公式3，u_H∶u_M∶u_L＝R_H∶R_M∶R_L，其中R_H，R_M，R_L的計算方法為收益函數中分配動作的計算方法，聯立公式1、公式2和公式3可解得所有u_i，然后對于所有的m∈M_X中對應u_H，u_M，u_L求均值，得到最終的U_H，U_M，U_L，在狀態轉移函數中，由動作a對應的工人等級l，得到其對應的質量躍遷概率u_l，則對于轉移前狀態s，如果s的任務質量為A，則轉移后狀態質量為A的概率為1，其它狀態的概率為0，如果任務質量不為A，則狀態發生躍遷的概率為u_l，保持原狀態的概率為1-u_l，其它狀態的概率為0，即：

其中2-b)的觀察函數學習過程說明：

O：記動作為a，轉移后狀態為s，獲得的觀察為z；如果動作a是終止動作或狀態s是結束狀態，則觀察值為true的概率為1，為false的概率為0，如果動作a是分配動作，則狀態s是執行中狀態，此時觀察函數取決于狀態的完成質量q，關于q分情況討論：

當q∈{C，D}時，觀察值為true的概率為0，為false的概率是1；當q＝B時，觀察值為true的概率為0.2，為false的概率是0.8，當q＝A時，觀察值為true的概率為0.8，為false的概率是0.2；

其中2-c)的信念狀態說明：

1)信念狀態是信念空間上的一個概率分布，表示系統對當前狀態的判斷，用來作為決策的依據。