沙宗軒 薛菲 朱杰

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

關(guān)鍵詞：云機(jī)器人;強(qiáng)化學(xué)習(xí);Q學(xué)習(xí);并行計(jì)算;任務(wù)調(diào)度;CloudSim

中圖分類號： TP242.6

文獻(xiàn)標(biāo)志碼：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 引言

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

傳統(tǒng)機(jī)器人系統(tǒng)框架如圖1所示，調(diào)度中心分配任務(wù)給機(jī)器人執(zhí)行，當(dāng)執(zhí)行的任務(wù)越來越復(fù)雜、需要更強(qiáng)的計(jì)算能力時(shí)，一種解決方式是提升每臺機(jī)器人的性能，但是會導(dǎo)致整體系統(tǒng)成本的大幅提升;另一種方式是采用云機(jī)器人框架。

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

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

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

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

1 基于并行強(qiáng)化學(xué)習(xí)的調(diào)度策略

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

4 結(jié)語

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

盡管本文的調(diào)度策略在實(shí)驗(yàn)中取得了一些成果，但是隨著狀態(tài)空間繼續(xù)擴(kuò)大，還是會遇到計(jì)算瓶頸;另一方面，如何對更復(fù)雜狀態(tài)空間的情景型任務(wù)的子問題進(jìn)行劃分也是后續(xù)研究的重點(diǎn)。

參考文獻(xiàn)：

[1] 陳康，鄭緯民.云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào)，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ì)算安全：架構(gòu)、機(jī)制與模型評價(jià)[J].計(jì)算機(jī)學(xué)報(bào)，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] 周風(fēng)余，尹磊，宋銳，等.一種機(jī)器人云平臺服務(wù)構(gòu)建與調(diào)度新方法[J].機(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學(xué)習(xí)和蟻群優(yōu)化混合的無線傳感器網(wǎng)絡(luò)移動代理路由算法[J].計(jì)算機(jī)應(yīng)用，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] 王超，郭靜，包振強(qiáng).改進(jìn)的Q學(xué)習(xí)算法在作業(yè)車間調(diào)度中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，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.