关键词：云边协同；调度；智能物流；路径规划；避障

Abstract: This paper designs a solution of multi-AGV logistics distribution system based on cloud-edge cooperation technology, the task scheduling system of multiple AGV vehicles is put on the cloud and the edge to finish the collaborative calculation, which connects the personnel of complex intelligent processing workshop, AGV vehicle, processing equipment and process flow, the dynamic obstacle avoidance and autonomous navigation tasks of AGV are placed on the side of edge server, which reduces the operation burden and delay problem of central cloud platform. The experiments show that the response of AGV in the process of logistics distribution is faster and the utilization of resources is more reasonable.

Key Words: Cloud edge coordination; Scheduling; Intelligent logistics; Path planning; Obstacle avoidance

1  引言

人工智能与物联网技术在智能制造领域中已经得到成熟的应用，随着机器学习、深度学习在无人驾驶技术领域的不断渗透，各国学者都在寻求用云边协同技术去提高用户在云平台上随时按需获取资源的能力。云计算是通过网络“云”，将巨大的数据计算处理程序在分割成多个小程序并将其分布在多个服务器组成的系统上，小程序负责对数据的处理和分析，然后将其结果通过网络系统反馈给用户。边缘云计算的产生是为了解决中心云平台的计算与网络压力而导致的延时等问题，它是对云计算的一个补充。在本文设计的物料配送系统中，生产人员仅仅需要把物料的起始点和物料配送的目标录入中心云平台，通过云边协同计算技术，就可完成航空加工车间的小车调度任务及路径规划任务，且在调度过程中实现资源与需求的合理匹配，小车的路径规划距离最短的目标。

2  物流配送系统总体设计

本文设计的航空加工车间AGV小车物流配送系统采用云边协同计算技术实现，用户管控侧通过服务器设备将物流配送信息同步到中心云平台上和边缘云平台上。同时，边缘侧服务器将现场AGV小车的位置信息和路径规划信息上传给中心云平台，中心云平台根据调度算法，匹配最合适的小车去完成配送任务，并将计算结果通过网络发送给边缘云服务器集群和用户侧，边缘云服务器接到任务后，启动调度算法选择的小车，并在小车运输过程中，给AGV小车规划好最短路径，用户侧收到中心云的反馈信息后可以监控整个物流配送过程。在AGV小车设备侧安装了多种传感器信息，这些传感器信息实时分类按需上传给中心云服务器和边缘云服务器集群。本文设计的基于云边协同计算架构下的物流配送系统整体信息框图如图1所示。

图1  云边协同计构下物流配送系统总体设计

3  中心云计算模块设计

基于复杂加工车间内的调度任务复杂且计算量大，理想的调度结果是将用户上传的配送目标点优先与距离最近或者即将最快完成任务的AGV小车进行匹配^[1]。中心云平台的主要计算任务是根据AGV小车现场运行数据及用户传的物流目标点数据，通过调度算法计算，完成现场所有AGV小车调度任务工作，并将其结果发给边缘云与用户，用户可以通过手机端的APP实时监控现场运行情况^[2]。边缘云可以得到具体启动哪一台AGV小车及小车的目标点数据。

本文设计的中心云模块中的硬件选用的处理器是：Intel(R) Core(TM) i5-7200U @2.50GHz 2.70GHz、双核处理器、8GB的内存、64位操作系统。调度算法是随机的、动态的、系统的请求资源合理分配的一个决策求解过程，这里的调度算法主要考虑时间和距离、资源的最优匹配，而这些考虑因素都是调度算法的约束条件。在云边协同计算的调度算法的模型中，假设用户上传的任务数据是j，t_ES(j)表示任务最早可能开始的时间，任何小车都必须在完成前一个任务后才可以进行下一个任务。t_EF（j）表示任务最早可能完成的时间^[2]。任务按最早开始时间所能达到的完成时间的计算公示如公式(1)所示。

            (1)

用户上传任务按最晚开始时间所能达到的完成时间的公示如公式(2)所示。其中，t_LS(j)表示j任务最迟开始的时间，这个任务j是在不影响整个任务按时完成的大前提下，必须开始的最迟时间。t_LF(j)是任务j的最晚完成任务所需要的时间。

                (2)

公式（1）是从任务调度的起点向终点递推的一个过程，而公式（2）是从终点向起点逆推的一个过程。本文的通过合并公式（1）和公式（2）来找到DAG合并图的关键路径，DAG是一个包含边和顶点的一个有向图，顶点表示的是任务，边表示的是通过该边链接的两个顶点之间的关系^[3]。在本案例中，我们将DAG的合并图理解为关键任务集合CTS(Critical tasks set)和非关键任务集NCTS(Non-critical tasks set),这里的任务集的类型有云端的任务CST(Cloud-side tasks)和边端任务集EST(Edge-side tasks)，其DAG合并图的关键路径模型公式如公式(3)所示。

                       (3)

有了调度算法模型公式，中心云端的计算主要任务就是将这个模型公式进行求解，调度算法的模型有很多种，本文使用的CECTS(Cloud and Edge Collaborative Task Scheduling)算法是通过云平台计算与边缘侧协同计算，从而实现调度任务的高效计算。其具体做法就是将中心云平台的DAG任务集与边缘服务器集群中的DAG任务集通过合并、分割和处理器分配3个步骤来实现，其中的DAG任务集合并的主要目的是减少处理冗余任务所造成的时间消耗^[4]。

4  边缘云计算模块设计

边缘侧服务器集群的主要任务是接收来自中心云服务器发送的任务调度指令和每个服务器所对应的AGV小车的控制，包括小车的自主定位、动态避障及自主导航，其中小车的实时位置数据和正在完成的任务的导航路径需要计算出结果后，发送给中心云平台，这些数据都是调度算法里的一部分^[5]。本文在边缘服务器中安装有AGV小车物流配送控制的仿真软件，服务器安装的是Linux系统及三维仿真软件GAZEBO。

4.1  边缘计复侧杂加工车间场景的搭建

本文仿真的加工车间实际建筑外墙尺寸为；L*W=120m*50m，在仿真空间中的车间外墙尺寸为L*W=60m*25m，仿真空间中的工作台、数控机床、加工车床与实际车间的数量相同，本文在仿真空间搭建的环境模型如图2所示。

图2  仿真空间的整体环境模型

4.2  小车模型的搭建

本文所搭建的AGV小车是通过URDF(Unified Robot Description Format)对AGV小车进行统一描述。在Gazebo仿真软件中有可以解析URDF文件中使用的.XML格式描述文件，同时ROS操作系统也提供了URDF文件的C++解析器^[6]。本文所搭建的AGV小车的模型如图3所示。

图3  仿真空间的AGV小车模型

4.3  AGV小车自主定位及建图

在边缘侧的服务器集群中的一个主要的任务是完成对小车的控制。而小车的自主定位及实时构建地图是小车自主导航及避障的基础，也是中心云平台需要上传的数据之一^[7]。本课题中AGV小车自主定位及实时构建地图（SLAM）问题研究中主要是通RBPF（Rao-Blackwellized Particle Filters）-SLAM算法实现，这属于滤波算法的一种，是将SLAM问题分解成小车的定位问题和基于位姿估计的环境特征位置估计问题^[8]，其算法的联合概率密度公式如公式(4)所示。

          (4)

公式（4）中的Z_1:t是传感器的观测数据；U_1:t是小车的里程计数据；P(X_1:t，m|Z_1:t，U_1:t)是联合后验概率密度函数；P(X_1：t|Z_t-1，U_t-1)是运动模型；P(m|X_1:t，Z_1:t)是观测模型。根据AGV小车上的编码器的当前位姿值和最后时刻的相对值、陀螺仪的数据来估算出小车位置概率分布，根据小车上激光雷达的观测到的数据来与地图的比对，从而得到小车更准确的自我定位^[9]，小车所构建的环境地图及自我定位如图4所示。

图4  AGV小车自我定位概率分布图

图4中的灰色浅色的区域就是可以通过的无障碍物的区域，深绿色的图案周围包围的部分是障碍物，障碍物周围粉色包围的区域是人为设置的障碍物膨胀区域，障碍物的膨胀系数可以根据实际情况调整，图4中红色的物体就是AGV小车，而比较密集的绿色箭头区域就是小车通过概率密度公式估算得到的小车可能的位置区域。

4.4  AGV小车动态避障及自主导航

小车的导航是在其准确定位的基础上进行的，小车能在自主导航的过程中，还有能力避开动态的障碍物，且在边缘侧的服务器中还要为小车规划出最短最优路径，这些都是导航算法的约束条件。本文的路径规划采用为全局路径规划和局部路径规划相结合的算法，其中全局规划路径的算法是找到对小车最优最短路径，而局部路径规划算法的目标是避障，小车全局路径规划的算法是A^*算法^[10]，这种算法非常适合栅格地图的导航，它是主要使用下面的公式(5)概率估计函数来作为路径的评价指标的。

                    (5)

公式（5）中的g(n)是从初始节点到当前节点的最小代价值；h(n)是从当前节点到目标节点的代价值；n是当前位置节点坐标；代价值可以通过距离度量算法得到。本文代价值是采用欧几里得距离算法，表示目标点和当前位置点的真实距离，即该点到原点的距离，其二维空间依据公式(6)计算。

            (6)

本文的局部路径规划算法采用的是DWA算法，即在边缘侧的服务器集群上先通过A^*算法进行一次路径规划，规划出从初始点到终点的全局路径;在相目标点运动的过程中，根据激光雷达传感器观测到的障碍物信息后，采用DWA算法进行二次路径规划，实时避开障碍物^[11]。DWA算法主要包含2个方面的工作，一个方面是产生可通过的搜索区域，这里的可通过的搜索区域指的是AGV小车在无碰撞的条件下所用时间最短的区域^[5]。算法的另外一个工作就是在搜索区域内选择优化方法，其目的是保证小车能在短时间内避开障碍物并到达终点。

5  设备侧模块设计

复杂加工车间的AGV小车是物流配送控制系统中的执行者，所有云端和边缘端的输入的原始数据信息都来自设备侧，设备侧的数据主要是来自于传感器。本文的设备侧的传感器信息有安装小车上的激光雷达、里程计、编码器、深度相机、惯性检查单元IMU，加速度计等传感器及网络交换机。用户可以通过手机APP程序或者现场服务器将目标点上传至云端，云端通过计算得出的决策可以通过网络下发给边端和用户端，用户可实时监控现场生产调度情况。

6  结束语

本文设计的基于云-边动态协作的AGV物流配送系统是人工智能和物联网技术深度融合的产物。随着5G时代的来临，云-边-端的信息交互技术会更高效，基于云边协同计算的技术也会在各个领域得到应用。本文的设计符合《中国制造2025》对制造过程提出的智能、高效、协同、安全的目标，为未来研究智能云制造提供一个参考。

参考文献：

[1] KEIVANI A，GHAYOOR F，TAPAMO J R. A review of recent methods of task scheduling in  cloud computing[C]. 2018 19th IEEE Mediterranean Electrotechnical Conference (MELECON). IEEE, Marrakesh,2018：104-109.

[2] PREMSANKAR G，NCESCO M D，TALEB T，Edge computing for the Internet of things：A case study[J]. Internet of Things Journal，2018，5(2)：1275-1284.

[3] 庄存波,刘检华,熊辉. 分布式自主协同制造-一种智能车间运行新模式[J]. 计算机集成制造系统, 2019,25(08)：1865-1874.

Zhuang cunbo，Liu jianhua，Xiong hui. Distributed initiative and collaborative manufacturing: new paradigm for intelligent shop-floor[J]，Computer Integrated Manufacturing Systems，2019，25(8)：1865-1874. (in Chinese).

[4] MAURYA A K，MODI K，KUMAR V，et al. Energy-aware scheduling using slack reclamation for cluster systems[J]. Cluster Computing, 2019, 29(7)：1-13.

[5] 赵龙乾，满君丰，彭成，薛振泽. 基于云端协同计算架构的边缘端I/O密集型虚拟机资源分配方案[J/OL]. https://doi.org/10.19734/j.issn. 1001-3695.2019.04.0107,2019-04-15/2019-09-20.

Zhao longqian，Man junfeng, Peng Cheng，Xue Zhenze.Edge-side io-intensive virtual machine resource allocation scheme based on cloud and edge collaborative computing architecture[J/OL]. https://doi.org/10.19734/j.issn.1001-3695.2019.04.0107, 2019-04-15/2019-09-20.(in Chinese).

[6] DING K，ANG X，CHAN F T S，et al. Training a hidden Markov model-based knowledge model for autonomous manufacturing resources allocation in smart shop floors[J]. IEEE Access，2019，7(1) 47366-47378.

[7] HANIF M A，KHALID F，PUTRA R V W，et al. Robust machine learning systems: Reliability and security for deep neural networks[C]. 2018 IEEE 24th International Symposium on On-Line Testing and Robust System Design (IOLTS). IEEE, 2018：257-260.

[8] YOUSEFLI A，A fuzzy ant colony approach to  fully fuzzy resource constrained project scheduling problem[J]．Industrial Engineering &Management Systems, 2017, 16(3): 307-315．

[9]Chen M H，Dong M，Liang B. Resource sharing of a computing access point for multi-user mobile cloud offloading with delay constraints[J]. IEEE Transactions on Mobile Computing，2018，17(12)：2868-2881.

[10]HaoY，Jiang Y，Chen T， et a， iTaskOffloading： Intelligent Task Offloading for a Cloud-Edge Collaborative System[J]. IEEE Network， 2019， 33(5)：82-88.

[11]Du J，Zhao L，Feng J，et al. Computation  offloading and resource allocation in mixed fog/cloud computing systems with min-max fairness guarantee[J]. IEEE Transactions on Communications， 2018， 66(4)：1594-1608.

作者简介：

吕玉江（1976-），男，硕士研究生，中国航空工业北京长城航空测控技术研究所，研究员。主要研究方向：飞行器半实物仿真运动控制技术。

韩召（1976-），女，硕士研究生，辽宁科技学院，邮编：117004，讲师。主要研究方向：机器人路径规划及导航算法