查看“DPS调度算法详解”的源代码

--AI gen introduction--

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

# 定义交管问题为资源的获取和释放。一个场景中具有多个路点。一台车可以拿着一个或多个路点的占用权。当一台车只拿着一个路点的占用权时，它只能呆在原地不懂。如果它拿着一个或多个路点的权限时，则可在这些路点间任意移动。车不应该处于它没有拿到路点权限的位置。（ai配图）
# 将交管需求简化为该数学问题：“有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-1,j-1]=1 且 两车同时移动不发生冲突
边界条件为D[0,0]=1。如果D[m,n]=1则说明存在可行的通行顺序。（ai配图-动态规划状态转移）
这个动态规划算法的时间复杂度为O(mn)，空间复杂度为O(mn)。在实际实现中，我们使用一个1024''1024的循环数组来存储这个状态矩阵，并用位运算来记录更多的状态信息（如是否检查过该状态、是否存在轨道冲突等）。''

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