DPS调度算法详解

--AI gen introduction--

实际上AGV调度系统问题已经被研究的很多了，这个问题的正式名字叫 Flowshop scheduling:https://en.wikipedia.org/wiki/Flow-shop_scheduling

为了解决以上调度问题，我们使用以下思路：

1. 定义交管问题为资源的获取和释放。一个场景中具有多个路点。一台车可以拿着一个或多个路点的占用权。当一台车只拿着一个路点的占用权时，它只能呆在原地不懂。如果它拿着一个或多个路点的权限时，则可在这些路点间任意移动。车不应该处于它没有拿到路点权限的位置。（ai配图）
2. 将交管需求简化为该数学问题：“有N个进程，每个进程各自有M_{n}个要顺序获取的资源R_{mn}，每个进程拿到了下一个资源就会释放上一个资源。有一个资源冲突矩阵C，定义资源两两间是否能同时获取。问是否存在至少一种资源获取序列，使得所有进程都能拿到最后一个资源？”。（ai配图）
   1. 首先考虑冲突矩阵就是单位阵（不考虑过于复杂的冲突情况）。
   2. 使用动态规划方法来规划两车之间的通行顺序。
   3. 使用搜索方法来预测/规划多车之间的通行顺序。
3. 实际工程时，处理以下细节问题：
   1. 每个“进程”，aka，车：虽然最少拿到两个资源。不一定会拿到下一个资源时立刻释放上一个资源。
   2. 路线可能只发一半，可能到了某个位置后才会确认车辆接下来继续走到哪里，但那个位置会堵塞交通，导致路线规划不了。（使用escape）
   3. 比较复杂的冲突关系，包括业务冲突、运动路线冲突等。（使用包络）
   4. 路线可能会因为业务的改变而中途改变，立刻停车位置可能堵塞交通，继续行走浪费里程（使用劫持）
   5. 有些车因为业务需要，需要相对于其他车提前到达某个点来操作。（使用资源冲突矩阵）
   6. 配发资源的时候需要最优化发放顺序。虽然可能多种方案都可行，但可能有些方案更好。（Johnson's rule）https://en.wikipedia.org/wiki/Johnson%27s_rule