多车调度基线声明（MAPF） | 仙工智能帮助中心

帮助中心主页

RDSCore 功能文档

多车调度基线声明（MAPF）

由于多车调度在不同的项目现场，有不同的业务逻辑、有不同的场地限制、不同的车型、地图、需求等，现行多车调度功能（G-MAPF）存在配置难度大等显著缺点，故在此文档对多车调度进行定义与基线声明，该文档将会详细回答以下问题：

单车调度与多车调度的基本定义，多车调度与单车调度的区别。
多车调度需要解决的基本问题。
多车调度的数学表达。
哪些场景需要做到打开参数即可，哪些场景需要研发人员介入。

基本定义

单车调度的定义

在默认的导航参数下，机器人执行运单时，会基于地图的拓扑结构，按最短路原则进行路径规划。机器人后续所有的路径是唯一确定的，当遇到障碍物时报阻挡停下，障碍物消失时继续按已规划的路线进行导航。
总结：不论场景中有多少机器人，不论使用多少互斥区或高级区域，只要路径规划的原则严格跟随拓扑地图中的最短路，都属于单车调度的范畴。

多车调度的定义

目前已经上线并正在维护的多车调度功能，只有 G-MAPF，在开启此功能时，机器人执行运单不再是完全地跟随最短路，而是会根据场景内所有机器人的状态随时更改自己后续的路线。允许机器人出现主动停车等待、提前绕路、倒车、甚至会暂时放弃执行任务一段时间等动作。
总结：路径规划的原则不再是严格跟随拓扑地图中的最短路，而是将所有路径规划的权利，100% 交由 AI 算法进行控制，这样的调度属于多车调度的范畴。

多车调度要解决的基本问题

根据上述对于多车调度的定义，多车调度本质上是对机器人进行路径规划，需要解决两个基本问题：

场景中不出现死锁。
提升订单完成效率。

多车调度的数学表达

假设，现在有辆车，是他们的联合路径，他们完成任务的代价被定义成，那么多车调度可以被定义成以下多目标优化的形式：

此处为了能够让所有人都能快速理解，我们不对求解细节进行描述。
但是，我们需要知道这个公式到底在干什么，请继续看下一小节~

一个现象

首先，联合路径就是对应现实世界的解，即，我们有了联合路径，让机器人跟随联合路径，就可以化解死锁、提高效率，但是，求出这个联合路径需要做功（即付出代价），这个代价越大，联合路径就越难求，算法就越容易卡顿。目前的 G-MAPF，刷新周期是 1.5 秒，这也就意味着，算法每时每刻都不停地在根据当前的场景信息进行计算，并周期地每过 1.5 秒输出一次找到的最优联合路径。
1.5 秒的时间，现代 CPU 可以做大约 10 的 10 次方次加法运算，可以进行大约 10 的 9 次方次连续访存操作，此处由于数据量巨大，限制我们的是访存操作，除此之外，我们将 CPU 运算转换为人类常用的概念运算，转换系数大约为 1000，故算法的性能严格上界为 10 的 6 次方次人类概念逻辑运算。
此时我们会发现出现这么一种现象，有的现场能够稳定运行 30 辆车，并且不需要进行过多的配置，但是有的现场，10 辆车算法就会出现卡顿，死锁，并且需要大量的配置场景内的点位属性，这是为什么呢？
因为不同的现场，MAPF 所做的功不同。

功的定义

为了方便现场工程师理解，我们将 MAPF 做的功定义成：

其中为：当不使用 MAPF 时，这个场景能够按指定效率，且不死锁地完成任务的普通高级区域的最低数量。

场景调度难易度分析

常见的高级区域有：

普通的互斥区。
数量的互斥区。
单向的互斥区。
指定目标点互斥（如果是要到达某个目标点则互斥，否则可以通过）。
等等

除上述之外，这些人类特色鲜明的调度逻辑，均可以被定义成普通高级区域。
根据之前我们对 MAPF 做功的定义，并假设一个普通高级区域的复杂度等价于人类逻辑概念运算，那么当现场中需要的普通高级区域数量超过 10 的 6 次方时，在普通的服务器上，使用通用参数必定无解，此时需要研发人员介入。

基线意义与现场分类

根据之前的分析，一个现场的多车调度难度，不再是我们看一眼觉得简单就是简单，而是有了明确的定量指标，通过这个定义，对现场的实施工程师也提供了一定的指导作用，我们可以提前先想想，如果通过自己画互斥区的方式，究竟需要画多少个基础的高级区域，这个数量便可以帮助我们衡量，这个业务逻辑是否可以顺利实现。
现在已经出现了一些现场，几百个互斥区虽然可以一定程度上解决死锁问题，但是无法满足效率要求，所以衡量的数量不仅仅是不出现死锁，而是能让现场按指定效率完成任务，才能算实现业务逻辑。