工业移动机器人多机调度系统性能指标定义及性能优化

2022-07-11张慧

电子技术与软件工程 2022年10期

张慧

（南京中兴新软件有限责任公司江苏省南京市 210012）

1 前言

AGV/AMR 是广泛应用于仓储和生产线进行智能搬运的移动机器人，是物流自动化升级的利器。通常，在一个项目中会存在多个AGV/AMR 同时运行，由调度系统进行协同调度管控。小型的多机协同项目，对调度系统的要求不是很高。但在大型多机协同项目中，尤其要求同时调度超过100台，甚至1000 台时，调度系统的性能就会成为一个瓶颈。由于不同的工作场景、任务类型差异很大，业界并没有一个标准来定义调度系统性能指标。所以，本文分析调度系统性能影响因素、试图建立一种标准的参考业务模型，在此模型下进行性能指标的计算和定义，并提出性能优化的方法进行验证。

因为自然导航方式的移动机器人AMR，较自动导引车AGV 的功能更加复杂，所以，下文以激光SLAM 导航的AMR 为例进行分析。

2 调度系统性能影响因素

2.1 移动机器人与调度系统的控制架构

在实际应用场景中，会存在多台移动机器人同时运行。但上位机MES 或WMS 等系统发布作业任务时，需要由调度系统来完成多台机器人之间的协同，进行任务分配、路径规划以及交通冲突的预防和解决。如图1 所示，移动机器人和调度系统之间有集中式和分布式两种控制架构。集中式那就是有一个统一的调度系统来完成调度工作，分布式调度是一种更自主式更灵活的调度方式。当前集中式的调度系统占绝大多数，分布式调度对算法、计算资源、通信都有较高的要求，目前还不成熟。所以，本文以集中式调度系统为研究内容。

图1：机器人与调度系统之间的控制架构

2.2 调度系统的组成及性能影响分析

调度系统包括一些地图管理、车辆/站点配置、任务查看、统计分析等非实时业务功能，但是影响性能指标的主要是实时性要求高和多并发的调度任务。

一次调度任务主要包括如图2 几个部分：

图2：调度任务流程

（1）任务分配：收到MES 等外部调度任务时，需要按照任务分配策略进行分配。分配策略可以有很多种，目前比较常用的策略是，先要寻找空闲的AMR，如果有多个，需要在其中计算出一个离目的地最近的AMR；如果没有空闲的AMR，进入任务等待列表，并不断扫描未执行任务列表。这个过程，如果空闲的很少，有空闲的就被分配了任务，那没有太多耗CPU 资源的操作。如果空闲的较多，则与下述路径规划中最短路径的计算相关。

（2）路径规划：这个过程对CPU 资源消耗较大。AMR通过激光SLAM 形成地图，并在地图中已规划好的可行驶线路图，包括节点和线段，并指定了线路的方向。对于任务起始A、B 点之间有多条路径，系统需要比较每条路径的最优化选择。如果AB 两点之间越长，线路节点(交叉点，以及长线段中的中间节点）越多，计算就会越复杂。最极端情况，与2（n 为节点个数）成正比。

（3）交通管制：AMR 运行过程中，每隔一个时间间隔（各厂家有不同，几十到几百毫秒）上报给调度系统当前位置和行驶方向。调度系统后计算这辆车和其他AMR 的距离，判断是否有碰撞风险。最极端情况，需要N*C(N,2)次计算（N为AMR 的台数）。

综上，影响调度任务性能的客观因素是任务频次、地图规划线路的交叉点及节点数以及AMR 个数，主观因素就是算法本身的合理性。

3 调度系统性能指标定义

3.1 模型的考虑

从上述分析可以看出，每个项目中的地理空间大小、路径多少、任务的频次、AMR 个数的不同，调度系统呈现出来的性能表现将会不同。但我们仍然需要有一个客观的指标来表征调度系统的性能，所以，我们需要在一个标准的“业务模型”下测试并表征出我们调度系统的性能。

“业务模型”的抽取尽可能是影响因素相互正交。我们可以看出：

Performance ∝ Efficiency CPU ∝ F& N& Duration& N

性能Performance 越高，CPU 效率越高，完成任务数F、通过的节点数N、能执行任务时长Duration 越多。因为路径的节点数N、单任务执行时长Duration，客户是不可能在实施前告知，但客户是能告知业务执行的节拍，即调度任务的频次F和工作区域的面积Area 的。

∵ N、N∝ Area

∵ Duration ∝ Area

∴ 当F、Area 确定时，Performance ∝ N，即调度系统的性能可以用同时支持的AMR 数来表征。

3.2 标准模型的设定

Area 的模型，我们可以参照一些项目，折算N800个货架/10000m，则折算系统的节点数N按1000 计算。（单位面积中货架数可以根据部署的合理性进行调整）

F，正常情况下应是客户给定。但在上述10000m的假设条件下，我们可以估算一个调度任务的节拍。

10000m空间，长100m*宽100m，

考虑到站点位之间距离最长390m，最短10m，接任务先从停车场或充电区或途中到任务起始点。则推算单任务平均运行距离S=（390+10）/2+40=240m；

平均速度是1.2m/s，加上对接货架2 次，每次20s，另外需要考虑充电时间影响的效率因素。充电2 小时，跑6 小时，效率为0.75。则单任务时间

Duration= （240/1.2+2*20s）/ 0.75 =240s/ 0.75 =320s

按前期讨论10000 平米，合理AMR 数不超过50 台。则

Ftask = 3600s/(320s/50)=562.5 次/h ≈560 次/h

综上，我们可以按10000 平米，800 个货架，每小时560 次调度任务为一个标准模型。

3.3 性能指标

在这个标准“业务模型”下，我们的性能指标就可以AMR 个数来表征。我们需要测试出单个业务单AMR 的CPU 占用。对应到相应的F、N、Duration 下每AMR的CPU、CPU、CPU。计算出系统能支持的最大AMR 数，这就是对应到标准业务模型下的性能指标。这个不同实现方式的不同厂家可以在同一基线上进行比较了。

对于具体的项目而言，也可以更快地计算出调度系统的硬件资源的需求和进行合理规划。比如，可以根据和标准模型之间的折算，计算出合理配置的AMR 个数。若超过系统的性能极限，就需要想办法划分区域、分多个调度系统等的规划。

4 性能优化分析

4.1 路径规划

以最常用A*算法为例。A*算法是在加权图的最小路径计算中最常用的经典图搜索算法之一。该算法采用加权图的形式，包括节点和节点之间的线段，包含节点间线段的开销、权重。该算法从初始起始节点开始，逐级访问评估下一个相邻节点来完成整个路径规划。

可以考虑的在基础算法上进行的优化：

4.1.1 静态路径表

（1）固定站点之间的路径，可以通过事先配置形成路径表，程序启动时，读到内存中，供每次路径规划直接查询使用；

（2）非固定路径，如AMR 在完成任务后回停车场途中接受到任务，可以分区设定虚拟固定站点，分段计算和查询路径表。

4.1.2 全局规划与局部规划结合

以一个实际工业应用中的地图为例，如图3。

图3：地图示例

（1）主干道、干线交通由调度系统集中规划；

（2）由AMR 自主路径规划支路上的路由。尤其在仓储库位、停车场区域，节点密集，交叉点多，易发生交通冲突。结合分布式交通管制（下一节描述），自主式避障，绕障的局部规划，更适合由AMR 来完成。

①局部路由区域，可以实现定义。区域的路径表，也可以配置成静态内存表。正常情况下，按路径表中选择路径。

②增强AMR 的感知能力（可考虑增加接近传感器），自主感知交通冲突。等发生交通冲突后，AMR 自行进行局部路径规划，可以停止等待，可以进行局部绕障路径规划。可以采用VFH 算法（以AMR 为视角的障碍物密度进行方向选择）进行绕障。

通行优先级可按一定交通规则，如东西向让行南北向，先至交叉口者优先等原则；在双向道路上相向冲突，制定如北向绕道让南向AMR 等原则；或者设置全局各AMR 的优先级等等规则。

AMR 自己进行停障或绕障（推荐），绕障方式可以减少等待时间，让整体效率更高。

4.2 交通管制

交通管制是为了防止发生AMR 之间的交通冲突，如果全局计算AMR两两之间的交通冲突，会非常消耗资源。所以，可以考虑多种算法的优化：

4.2.1 缩小到冲突区检测

划分不同的冲突区，将可能出现冲突的交叉口周围画成冲突区，不在同一冲突区范围内或不在冲突可能范围的AMR 就不需要计算。

4.2.2 局部闭锁

在节点密集的库位、停车场等区域，进行局部闭锁的方式。以图4 某项目中的停车区为例。停车场有P1 到P14，14 个停车位，当需要同时出来的时候，就会相互锁死。

图4：停车场站点示意图

我们可以尝试一下高铁和地铁的闭锁方式。将停车场这个区域设为闭锁联动区。假设当P6 的AMR 要出库，就请求将S6、S5、S4、S3 闭塞，当没有更高优先级的AMR 同时申请，则调度系统确认闭塞。调度系统若收到有该区域的AMR 上报位置信息，即通知闭锁区域。假设此时有P4 的AMR 要出库，判断路径规划中有S4、S3 被闭塞，则等待闭塞取消。这样做的好处是，当有多台同时出入时，调度系统只需广播闭塞信息，由AMR 自行计算是否停止等待。

4.2.3 分布式管制

同上一节。增强AMR 的感知能力（可考虑增加接近传感器），自主感知交通冲突。等发生交通冲突后，AMR 自行进行局部路径规划，可以停止等待，可以进行局部绕障路径规划。可以采用VFH 算法（以AMR 为视角的障碍物密度进行方向选择）进行绕障。