[發明專利]一種基于空間眾包社交影響偏好的組任務分配方法

有效

• 申請號: 202010170604.6
• 申請日: 2020-03-12
• 公開（公告）號: CN111311115B
• 公開（公告）日: 2021-04-23
• 發明（設計）人: 鄭凱;趙艷;李響
• 申請（專利權）人: 電子科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 成都眾恒智合專利代理事務所(普通合伙) 51239
• 代理人: 劉華平

1.一種基于空間眾包社交影響偏好的組任務分配方法，其特征在于，包括工人組的基于社交影響的偏好模型SIPM和基于工人組偏好值的基于偏好的組任務分配PGTA；所述SIPM部分中，同時使用工人-任務交互數據和工人組-任務交互數據，采用二分圖嵌入模型BGEM和注意力機制獲得每個工人組對不同任務種類的偏好值；采用BGEM對工人-任務交互數據和工人組-任務交互數據進行建模，從而分別學習低維空間中工人和任務種類的向量表示；引入工人的社交影響力，所述社交影響力表示在作出任務選擇決策時團隊中工人的權重，具體為：將工人-任務交互數據和工人組-任務交互數據融合以構建一個社交網絡，基于該社交網絡提取社交網絡信息；將工人組-任務交互數據和工人-任務交互數據相結合，獲得工人和任務種類的表示向量以及工人的權重，即工人社交影響；同時，使用注意力機制計算工人組向量，該注意力機制為不同的工人分配不同的權重，最終，將工人組的表示向量和任務種類向量做點積，以獲得工人組對任務種類的偏好值；

所述PGTA中，給定要分配的工人和任務，首先通過考慮行程限制以獲得可用工人集合，然后使用基于樹分解的最優任務分配算法將任務分配給合適的工人組以最大化總任務分配，并且給對任務有著更高偏好值的工人組更高的優先級；

個人交互模型：

給定工人和任務之間的交互，即工人-任務交互數據，首先構建一個二分圖，其中，表示工人集合，表示任務種類，表示中的節點集合，表示工人和任務種類間的邊集合；當工人執行過種類為的任務時，則兩者之間存在一條邊邊的權值設為其中，表示工人執行過的種類為的任務數量，表示工人執行過的任務總數；

使用BGEM建模個人工人-任務交互，對于給定的工人和種類為的任務進行交互的概率可以計算如式(1)所示：

其中，表示工人的表示向量，這代表該工人的偏好，表示任務種類的表示向量；

定義BGEM的目標函數，BGEM的目標旨在對于每個工人最小化經驗分布和估計的鄰居概率分布之間的KL散度；使用表示工人節點的出度，該出度使用計算得出，其中，表示邊的權值；將經驗分布定義為因此，目標函數可定義為式(2)：

工人組交互模型：

構建一個二分圖表示工人組和任務種類之間的交互，該二分圖用表示，其中，表示工人組集合，表示和的節點集合，表示工人組和任務種類間的邊集合；當工人組執行過種類為的任務時，則兩者之間存在一條邊同時，邊的權值可簡單設為其中，表示工人組執行過的種類為的任務數量，表示工人組執行過的任務總數；使用表示工人組的表示向量，表示任務種類的表示向量；目標是為每個工人組獲取表示向量以估計對所有任務種類的偏好值；

工人組-任務交互數據的目標函數可以通過式(3)計算：

引入一個系數表示工人組中工人的權重，該權重表示組在選擇任務時工人的組意識的個人社交影響力；具體為：給定工人組如式(4)定義工人組的表示向量

為每個工人引入一個額外的正值該值表示不依賴于任何特定組的全局個人社交影響力；使用表示一個工人對組內選擇任務的相對影響力；因此，按照注意力機制，該系數可由如式(5)計算：

根據社交網絡結構信息計算每個工人的社交網絡特征向量使用特征選擇向量為不同的結構特征分配不同的權重；將所有的特征值歸一化為[0，1]范圍內；接下來，將社交網絡特征向量和特征選擇向量做點積，作為工人的全局個人社交影響的高斯先驗，即其中是一個偏差項；由于全局個人社交影響可能會受到其他未知因素的影響，為了學習更加健壯的全局個人社交影響力，設服從正態分布，均值為

在目標函數方面，由于為個人社交影響參數引入了高斯先驗，因此在目標函數中添加相應的正則化項即其中超參數可以控制正則項的權重；因此，新的目標函數如式(6)所示：

將和相結合形成聯合目標函數，定義如式(7)所示：

采用標準的隨機梯度下降策略最小化式(7)中的目標函數在此過程中，學習到工人表示向量任務種類表示向量和模型參數、根據式(5)計算出表示組意識的個人社交影響力的系數然后根據式(4)相應的計算出每個組的表示向量最終，將每個組的表示向量和每個任務種類的表示向量做點積，以獲得每個組對每個任務種類的偏好值；

可用工人組集合的產生：

獲得每個任務的可用工人；由于工人可達范圍、工人可用時間和任務失效時間的約束，在某個時刻每個任務只能由一小部分工人完成；因此，首先在不違反約束的情況下獲得能夠完成該任務的工人集合；任務的可達工人子集，可用表示，且應該滿足以下條件：

(1)工人在任務s失效前，到達任務s的地點，即

(2)任務s在工人的可達范圍內，即

(3)工人在自己的有效時間內，到達任務s的地點，即

其中，表示當前時間，表示從工人位置和位置之間的行駛時間，而是給定的位置和位置之間的行駛距離；上述三個條件保證工人可以在任務失效之前且在工人的可用時間內直接從其位置行駛到任務的位置；

并且是Reachable Worker sets，表示可達工人集合，即由于時空約束，每個任務只能由一些工人來完成，是一個整體式；前面提到的不指定某個任務，即對于空間眾包中的所有工人；

獲得每個任務的可用工人組集合；給定每個任務s的可達工人，在組內工人可用時間和允許分配的執行任務的工人數量的約束下，接下來查找可用工人組集合，用表示，中的可用工人組應滿足以下條件：

(1)

(2)

其中，表示中工人數量；上述兩個條件保證一個組內的工人到達任務的位置而不會影響互相的可用時間。