基于并行強化學習的云機器人任務調度策略

沙宗軒 薛菲 朱杰

摘 要：為了解決機器人完成大規模狀態空間強化學習任務時收斂慢的問題，提出一種基于優先級的并行強化學習任務調度策略。首先，證明Q學習在異步并行計算模式下的收斂性;然后，將復雜問題根據狀態空間進行分割，調度中心根據所提策略將子問題和計算節點匹配，各計算節點完成子問題的強化學習任務并向調度中心反饋結果，實現在計算機集群中的并行強化學習;最后，以CloudSim為軟件基礎搭建實驗環境，求解最優步長、折扣率和子問題規模等參數，并通過對實際問題求解證明在不同計算節點數的情況下所提策略的性能。在使用64個計算節點的情況下所提策略相比輪詢調度和隨機調度的效率分別提升了61%和86%。實驗結果表明，該策略在并行計算情況下有效提高了收斂速度，并進一步驗證了該策略得到百萬級狀態空間控制問題的最優策略需要約1.6×105s。

關鍵詞：云機器人;強化學習;Q學習;并行計算;任務調度;CloudSim

中圖分類號： TP242.6

文獻標志碼：A

Abstract： In order to solve the problem of slow convergence speed of reinforcement learning tasks with large state space， a priority-based parallel reinforcement learning task scheduling strategy was proposed. Firstly， the convergence of Q-learning in asynchronous parallel computing mode was proved. Secondly， complex problems were divided according to state spaces， then sub-problems and computing nodes were matched at the scheduling center， and each computing node completed the reinforcement learning tasks of sub-problems and gave feedback to the center to realize parallel reinforcement learning in the computer cluster. Finally， the experimental environment was built based on CloudSim， the parameters such as optimal step length， discount rate and sub-problem size were solved and the performance of the proposed strategy with different computing nodes was proved by solving practical problems. With 64 computing nodes， compared with round-robin scheduling and random scheduling， the efficiency of the proposed strategy was improved by 61% and 86% respectively. Experimental results show that the proposed scheduling strategy can effectively speed up the convergence under parallel computing， and it takes about 1.6×105s to get the optimal strategy for the control probelm with 1 million state space.

Key words： cloud robot; reinforcement learning; Q-Learning; parallel computing; task scheduling; CloudSim

0 引言

近幾年機器人進入了快速發展時期，人力成本的上升催生了使用機器替換人力的需求。目前由于機器人的能力，尤其是智能水平和期望相差很遠，導致商業機器人的應用主要集中在汽車和電子設備等大規模重復生產領域[1]。隨著云計算的廣泛使用，無論是租賃公有云還是部署本地云，都為大計算量的任務提供了解決方案[2];同時隨著機器學習等技術的進步，擁有充足計算資源的機器學習算法可以滿足機器人更高智能化程度的要求。

傳統機器人系統框架如圖1所示，調度中心分配任務給機器人執行，當執行的任務越來越復雜、需要更強的計算能力時，一種解決方式是提升每臺機器人的性能，但是會導致整體系統成本的大幅提升;另一種方式是采用云機器人框架。

在2010年的Humanoids會議上，卡耐基梅隆大學James Kuffner教授提出了將云計算和機器人學相結合的“云機器人”框架[3]，被看作是機器人學下一個發展趨勢。該框架將機器人需要的計算能力和存儲資源卸載到云端以降低本身負擔：利用云端的計算資源不僅可以加快計算速度、有效減少每臺機器人成本，還可以做到知識共享[4-7]。整體系統框架如圖2所示。

可以預見在未來需要機器人執行任務的計算量越來越大的情況下，使用云機器人框架更加合理，這也成為了目前的研究熱點。Yan等[8]探討了中小企業云機器人相關的主要技術，研究了云機器人計算負載分配機制和基于云平臺的群體學習等內容，研究結果有助于云機器人智能調度與控制以及面向群體學習的云架構設計;2011年初由Waibel等[9]聯合埃因霍溫大學、慕尼黑工業大學等學校和飛利浦公司發起的RobotEarth項目致力于打造一個機器人之間消息共享和相互合作的平臺，提高學習效率并提出了機器人之間的語言，異構機器人也可以對同一個數據庫資源進行訪問，實現信息共享;2016年由Google旗下DeepMind公司開發的Alphago人工智能程序擊敗了韓國圍棋世界冠軍選手驗證了深度強化學習的強大能力[10];加州大學的Keho等[11]利用Willow Garage公司推出的機器人結合Google的目標識別引擎實現了三維空間的機器人抓取任務;2017年周風余等[12]提出了一種機器人云平臺框架，將云平臺的功能封裝成網絡服務對外提供，達到了計算資源復用的目的。

為了提高云機器人的智能化程度，采用強化學習中的表格解決算法（Tabular Solution Method， TSM）解決高維狀態空間的復雜問題往往收斂時間長，很多學者在同一范疇內提出了基于近似解的解決方法，或者與其他方法結合提出了新思路如深度強化學習等。但在一些實際場景下仍需要得到解決問題的準確最優策略，如倉儲物流領域的無人倉系統大量使用自動導引運輸車（Automated Guided Vehicle， AGV）取代人力[13]，系統采用云機器人架構，AGV通過讀取地上的二維碼確認自身位置，二維碼陣列構成柵格地圖，在對AGV進行路網規劃、避障規則設置和倉庫貨位分配之前需要對地圖進行學習，評價不同任務下采取不同動作的價值，得到的知識可直接使用或者用作其他功能的先驗知識。這種情景型任務（episodic tasks）采用表格解決算法可以解決，但隨著狀態空間擴大，完成學習需要的時間快速增加，實際應用中無法接受太大的時間開銷;而近似解決方法利用有限狀態空間的經驗進行有效推廣，在遇到未知情況時從之前遇到的情況中歸納類似情景，關鍵在于問題的泛化，難以得到關于整體問題的最優策略。

為了得到精確的最優策略使用表格解決方法，并盡可能減少時間開銷，文本利用云平臺的并行計算資源，提出了一種基于并行強化學習的云機器人任務調度策略，由云端的調度中心將復雜問題分割成若干子問題，調度策略分配agent對各個子問題并行學習，通過異步方式將學習結果反饋給調度中心，達到縮短復雜問題學習時間的目的。云平臺的可擴展性保證了充足的計算資源，可根據需要增加計算節點、增強計算能力;同時每一個接入云端的機器人均可獲取整體問題的學習結果，實現學習知識復用，滿足云機器人的一般需求。

1 基于并行強化學習的調度策略

強化學習是指從環境狀態到動作映射的學習，使動作從環境中獲得累積獎勵最大，該方法通過agent與環境交互來尋找最優策略，在過程控制、任務調度、機器人和游戲等領域應用廣泛[14-16]。假設環境是馬爾可夫型，那么強化學習問題可以通過馬爾可夫決策過程建模，根據在學習過程中是否需要精確的環境模型分為基于模型法和模型無關方法。基于模型法需要準確的狀態轉移概率來評價當前狀態的好壞，在強化學習問題中往往環境模型是未知的，故基于模型法的適用性有限。模型無關方法針對環境未知的情況，根據agent何時對知識進行更新分為時間差分（Temporal Difference， TD）方法和蒙特卡羅（Monte Carlo， MC）方法。MC方法直到情景（episode）結束才進行知識更新，如果情景過長會產生較大的更新延遲;TD方法則是在一個時間步（time step）完成之后立刻更新當前獲取的知識，通過迭代解決時間信度分配問題[17-18]，這種快速更新知識的方式使得TD方法及其改進型在強化學習中應用廣泛。TD方法根據值預測和動作選擇時是否遵循同一策略分為在策略（on policy）和離策略（off policy）兩種方式，分別對應Q-Learning和SARSA（State Action Reward State Action）算法，采用離策略方式的Q-Learning使學習數據更具多樣性。綜合以上算法特性和本文的研究背景及實際需求，采用Q-Learning作為子問題學習算法。

4 結語

由于經典強化學習算法在大狀態空間下效率較低，結合云機器人架構，本文提出了一種并行強化學習的任務調度策略，利用隨機逼近算法的收斂性證明與Q-Learning結合，表明了在并行異步的計算方式下的收斂性。為了充分利用云端的并行計算資源，將原始復雜問題分割成若干子問題，由調度中心負責計算節點和子問題匹配以及維護Q值表，經實驗驗證了最優參數以及調度策略的可行性和效率。實驗結果顯示：將復雜問題分割進行并行計算的效率要遠好于整體計算，本文設計的調度策略對于解決并行強化學習問題的效果要優于常用的任務調度策略;同時，增加計算節點可以縮短整體問題的收斂時間，但如果繼續增加計算節點，對收斂時間的影響將減弱;最后驗證了更大狀態空間問題的計算結果。本文實驗結果及最優參數可用在同類型計算情景下，例如自動導引運輸車（AGV）和無人機得到解決控制問題的最優策略問題，并且每一個接入云端的機器人終端都會獲得完整學習結果。

盡管本文的調度策略在實驗中取得了一些成果，但是隨著狀態空間繼續擴大，還是會遇到計算瓶頸;另一方面，如何對更復雜狀態空間的情景型任務的子問題進行劃分也是后續研究的重點。

參考文獻：

[1] 陳康，鄭緯民.云計算：系統實例與研究現狀[J].軟件學報，2009，20（5）：1337-1348. （CHEN K， ZHENG W M. Cloud computing： system instances and current research [J]. Journal of Software， 2009， 20（5）： 1337-1348.）

[2] 林闖，蘇文博，孟坤，等.云計算安全：架構、機制與模型評價[J].計算機學報，2013，36（9）：1765-1784. （LIN C， SU W B， MENG K， et al. Cloud computing security： architecture，mechanism and modeling [J]. Chinese Journal of Computers， 2013， 36（9）： 1765-1784.）

[3] KUFFNER J J， LAVALLE S M. Space-filling trees： a new perspective on incremental search for motion planning [C]// Proceedings of the 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway， NJ： IEEE， 2011： 2199-2206.

[4] DU Z， HE L， CHEN Y， et al. Robot cloud： bridging the power of robotics and cloud computing [J]. Future Generation Computer Systems， 2017， 74： 337-348.

[5] QURESHI B， KOUBA A. Five traits of performance enhancement using cloud robotics： asurvey [J]. Procedia Computer Science， 2014， 37： 220-227.

[6] XU W， LIU Q， XU W J， et al. Energy condition perception and big data analysis for industrial cloud robotics [J]. Procedia CIRP， 2017， 61： 370-375.

[7] WAN J， SHEN F. Introduction to the special section on cloud robotics for industrial applications [J]. Computers and Electrical Engineering， 2017， 63： 53-55.

[8] YAN H， HUA Q， WANG Y， et al. Cloud robotics in smart manufacturing environments： challenges and countermeasures [J]. Computers and Electrical Engineering， 2017， 63： 56-65.

[9] WAIBEL M， BEETZ M， CIVERA J， et al. RoboEarth — a world wide Web for robots [J]. IEEE Robotics and Automation Magazine， 2011， 18（2）： 69-82.

[10] WANG F Y， ZHANG J， ZHENG X H， et al. Where does AlphaGo go： from church-turing thesis to alphago thesis and beyond [J]. IEEE/CAA Journal of Automatica Sinica， 2016， 3（2）： 113-120.

[11] KEHO B， MATSYKAWA A， CANDIDO S， et al. Cloud-based robot grasping with the google object recognition engine [C]// Proceedings of the 2013 IEEE International Conference on Robotics and Automation. Piscataway， NJ： IEEE， 2013： 4263-4270.

[12] 周風余，尹磊，宋銳，等.一種機器人云平臺服務構建與調度新方法[J].機器人，2017，39（1）：89-98. （ZHOU F Y， YIN L， SONG R， et al， A novel building and scheduling method of cloud platform services for robot [J]. Robot， 2017， 39（1）： 89-98.）

[13] CARDARELLI E， DIGANI V， SABATTINI L， et al. Cooperative cloud robotics architecture for the coordination of multi-AGV systems in industrial warehouses [J]. Mechatronics， 2017， 45： 1-13.

[14] JEVTIC A， COLOM A， ALENY G， et al. Robot motion adaptation through user intervention and reinforcement learning [J]. Pattern Recognition Letters， 2018， 105： 67-75.

[15] 黨小超，姚浩浩，郝占軍.Q學習和蟻群優化混合的無線傳感器網絡移動代理路由算法[J].計算機應用，2013，33（9）：2440-2443，2449. （DANG X C， YAO H H， HAO Z J. Mobile Agent routing algorithm for WSN based on Q learning hybrid with ant colony optimization [J]. Journal of Computer Applications， 2013， 33（9）： 2440-2443， 2449.）

[16] 王超，郭靜，包振強.改進的Q學習算法在作業車間調度中的應用[J].計算機應用，2008，28（12）：3268-3270. （WANG C， GUO J， BAO Z Q. Application of improved Q learning algorithm to job shop problem [J]. Journal of Computer Applications， 2008， 28（12）： 3268- 3270）

[17] LEOTTAU D L， RUIZ-DEL-SOLAR J， BABUKA R. Decentralized reinforcement learning of robot behaviors [J]. Artificial Intelligence， 2018， 256： 130-159.

[18] DRUGAN M， WIERING M， VAMPLEW P， et al. Special issue on multi-objective reinforcement learning [J]. Neurocomputing， 2017， 263： 1-2.

[19] WATKINS C J C H， DAYAN P. Q-learning [J]. Machine Learning， 1992， 8（3/4）： 279-292.

[20] SHAH S M， BORKAR V S. Q-learning for Markov decision processes with a satisfiability criterion [J]. Systems & Control Letters， 2018， 113： 45-51.

[21] POURPANAH F， TAN C J， LIM C P， et al. A Q-learning-based multi-agent system for data classification [J]. Applied Soft Computing， 2017， 52： 519-531.

[22] KHIM S， HONG S， KIM Y， et al. Adaptive visual tracking using the prioritized Q-learning algorithm： MDP-based parameter learning approach [J]. Image & Vision Computing， 2014， 32（12）： 1090-1101.

[23] TSITSIKLIS J N. Asynchronous stochastic approximation and Q-Learning [J]. Machine Learning， 1994， 16（3）： 185-202.

[24] WU R， DOWN D G. Round robin scheduling of heterogeneous parallel servers in heavy traffic [J]. European Journal of Operational Research， 2009， 195（2）： 372-380.

[25] SOUALHIA M， KHOMH F， TAHAR S. Task scheduling in big data platforms： a systematic literature review [J]. The Journal of Systems & Software， 2017， 134： 170-189.

[26] MAMOUN M B， FOURNEAU J-M， PEKERGIN N. Analyzing weighted round robin policies with a stochastic comparison approach [J]. Computers and Operations Research， 2008， 35（8）： 2420-2431.

[27] SUKSOMPONG W. Scheduling asynchronous round-robin tournaments [J]. Operations Research Letters， 2016， 44（1）： 96-100

[28] GOYAL T， SINGH A， AGRAWAL A. CloudSim： simulator for cloud computing infrastructure and modeling [J]. Procedia Engineering， 2012， 38： 3566-3572.

[29] HE Z T， ZHANG X Q， ZHANG H X， et al. Study on new task scheduling strategy in cloud computing environment based on the simulator CloudSim [J]. Advanced Materials Research， 2013， 2249（651）： 829-834.

[30] MEHMI S， VERMA H K， SANGAL A L. Simulation modeling of cloud computing for smart grid using CloudSim [J]. Journal of Electrical Systems and Information Technology， 2016， 4（1）： 159-172.

[31] CHOWDHURY M R， MAHMUD M R， RAHMAN R M. Implementation and performance analysis of various VM placement strategies in CloudSim [J]. Journal of Cloud Computing： Advances， Systems and Applications， 2015， 4（1）： Article No. 45.