基于多智能體深度強化學習的空間眾包任務分配

趙鵬程, 高 尚, 于洪梅

(吉林大學 計算機科學與技術學院, 長春 130012)

眾包(crowdsourcing)是一種利用人群智慧完成任務的計算范式. 隨著移動互聯網的快速發展和移動設備的普及, 空間眾包(space crowdsourcing, SC)[1]成為一種新興的眾包類別. 在SC系統中, 首先請求者將時空任務提交到平臺； 然后在差旅預算、 任務期限和技能要求等約束條件下進行任務分配或選擇； 最后工人在截止日期前趕往指定地點完成任務并獲得報酬. 目前, 任務分配作為空間眾包中最基本的挑戰, 得到廣泛關注. 現有的工作存在以下不足： 1) 大多數只考慮工人或請求者單方面的利益, 若只考慮工人利益, 則會導致偏遠地區的任務難以完成； 若只考慮請求者利益, 則任務分配可能會對某些工人不公平; 2) 通常只考慮強制工人合作或禁止工人合作的單一場景, 前者忽略了工人的情感和偏好, 而后者不利于工人和請求者利益的最大化； 3) 精確算法由于復雜度過高而難以在實際中應用, 而貪婪算法僅注重眼前利益, 只能得到次優解.

研究表明, 多智能體系統(multi-agent system, MAS)與眾包系統的關鍵要素和過程聯系緊密[2], 多主體技術可用來提高眾包系統的自適應性和自組織性, 并解決任務分配、 任務分解、 激勵機制設計等眾包中的典型挑戰. 此外, 深度強化學習(deep reinforcement learning, DRL)以Markov決策過程為理論框架, 考慮了動態環境下的即時回報和未來回報, 根據與復雜環境交互的經驗, 直接擬合參數化模型學習最優策略, 在許多復雜的實際問題中……