沙宗轩 薛菲 朱杰

摘 要：为了解决机器人完成大规模状态空间强化学习任务时收敛慢的问题，提出一种基于优先级的并行强化学习任务调度策略。首先，证明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.