DPS调度算法详解

实际上AGV调度系统问题已经被研究的很多了，这个问题的有很多相关的纯数学研究，如 Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling。在Simple的调度逻辑中，我们使用以下思路：

1. 定义交管问题为资源的获取和释放。一个场景中具有多个路点。一台车可以拿着一个或多个路点的占用权。当一台车只拿着一个路点的占用权时，它只能呆在原地不懂。如果它拿着一个或多个路点的权限时，则可在这些路点间任意移动。车不应该处于它没有拿到路点权限的位置。（ai配图）
2. 将交管需求简化为该数学问题：“有N个进程，每个进程各自有M_{n}个要顺序获取的资源R_{mn}，每个进程拿到了下一个资源就会释放上一个资源。问是否存在至少一种资源获取序列，使得所有进程都能拿到最后一个资源？”。（ai配图-问题A）

我们先考虑两车间的情况：两台车A,B分别要顺序获取m,n个资源。容易想到用一个m*n的矩阵就可以穷尽A,B两车的全部获取资源的状态。于是我们可以得到问题A中N=2的情况的精确解：

使用动态规划方法来规划两车之间的通行顺序。

使用动态规划方法来规划两车之间的通行顺序。设通行矩阵D[i,j]表示车A获得了第i个资源、车B获得了第j个资源时的状态。D[i,j]=1表示该状态可达，D[i,j]=0表示该状态不可达。那么有如下状态转移方程：

D[i,j] = 1 当且仅当：

• (i,j)位置的资源不存在直接冲突

• 满足下列条件之一：
  • D[i-1,j]=1 且 车A从i-1到i的路径不与车B在j位置发生冲突
  • D[i,j-1]=1 且 车B从j-1到j的路径不与车A在i位置发生冲突

$D[i,j]={\begin{cases}1,&{\text{if and only if all the following conditions are satisfied:}}\\&(i,j){\text{-th resource has no direct conflict}}\\&\quad {\text{and}}\\&(D[i-1,j]=1\land {\text{path of A from }}i-1{\text{ to }}i{\text{ does not conflict with B at }}j)\\&\quad \lor \\&(D[i,j-1]=1\land {\text{path of B from }}j-1{\text{ to }}j{\text{ does not conflict with A at }}i)\\0,&{\text{otherwise}}\end{cases}}$

边界条件为D[0,0]=1，意为AB辆车初始状态没有冲突。如果D[m,n]=1则说明存在可行的通行顺序。（ai配图-动态规划状态转移）

这个动态规划算法的时间复杂度为O(mn)，空间复杂度为O(mn)。在实际实现中，我们使用一个1024x1024的二维循环数组来存储这个状态矩阵，并用位运算来记录更多的状态信息（如是否检查过该状态、是否存在道路冲突等）。

这种动态规划方法可以处理大多数冲突类型：如基于包络判断运动路线冲突、可达性等；只要能将这些约束规约为两车之间的约束的都能使用通行矩阵表达。这些冲突类型仅仅是增加了一些状态递推时判断的条件。

使用搜索方法来预测/规划多车之间的通行顺序。

虽然使用动态规划方法已经能够遍历地处理两车之间地通行情况，然而当车辆数量超过2台时，问题的复杂度会急剧上升。对于N台车的情况，如果仍然使用类似的动态规划方法，需要一个N维的状态矩阵，时间复杂度将达到O(M^N)，其中M为平均每台车需要获取的资源数量。这在实际应用中是不可接受的。

SimpleCore中采用了一种启发式的"推进"算法来处理多车的情况：

• 首先使用上述动态规划方法计算任意两车之间的可行通行顺序

• 当一台车请求获取新资源时，系统会模拟其他车辆的推进过程，检查是否存在死锁风险

• 如果所有车辆都能推进到各自的目标位置，则允许该车获取资源；否则视情况拒绝请求这种方法虽然不能保证找到最优解，但能在可接受的时间内找到可行解，且能有效预防死锁的发生。在实践中，我们还引入了"汇点"（永远允许通过）和"逃生路径"（当检测到死锁风险时的备选路径）等机制来提高系统的鲁棒性。（ai配图-推进算法示意）

实际工程需要处理地细节问题

以上是一个大致的系统描述，在实际工程应用中还需要处理以下问题：

1. 每个“进程”，aka，车：虽然最少拿到两个资源。不一定会拿到下一个资源时立刻释放上一个资源。
2. 路线可能只发一半，可能到了某个位置后才会确认车辆接下来继续走到哪里，但那个位置会堵塞交通，导致路线规划不了。（使用escape）
3. 比较复杂的冲突关系，包括业务冲突、运动路线冲突等。（使用包络）
4. 路线可能会因为业务的改变而中途改变，立刻停车位置可能堵塞交通，继续行走浪费里程（使用劫持）
5. 有些车因为业务需要，需要相对于其他车提前到达某个点来操作。（使用资源冲突矩阵）
6. 配发资源的时候需要最优化发放顺序。虽然可能多种方案都可行，但可能有些方案更好。（Johnson's rule）https://en.wikipedia.org/wiki/Johnson%27s_rule