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

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

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

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

虽然使用动态规划方法已经能够遍历地处理两车之间地通行情况，然而当车辆数量超过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
7. 调度内核运行原理
   
   
   
   跳到导航跳到搜索SimpleCore保证静态的任务和路线一定能够完成，从而简化了机器人车队调度的开发困难。静态指路线一旦下发一般不会改变，交管保证满足该路线一定能执行到位且不会发生死锁（即通过死锁预防算法），相对于“解死锁”方法，“死锁预防”方法可以满足在大量工业场景中的工艺需求，如过风淋门、叉车等不允许折返的场景。当然，SimpleCore也支持动态更改路线的需求。所有路线的增加和变更都会进行交通规划计算，保证场景的正常运行。SimpleCore也提供了多种方便路线设计和变更的机制。
   目录
   
   1交管计算原理
   2可编程的路径搜索算法
   3路径编译
   4总体任务逻辑
   5总结
   交管计算原理
   SimpleCore使用动态规划和搜索方法（DPS算法）进行交通管制。首先使用动态规划计算双车间的通行矩阵，然后在实际车辆需要上锁时，通过进行剪枝的搜索算法进行多车死锁可能性检测并决策。详细的算法可以参考DPS调度算法详解。
   用户可以完全不再关注交管，DPS算法几乎在所有情况下得到正确交管顺序。不过由于算法的取向较为保守，可能在多车长路径交管冲突上选择要求人工介入判断，也可通过调整参数强制要求算法自动判断。
   可编程的路径搜索算法
   在SimpleCore框架中，路径搜索算法采用了一种高度可编程的方式，通过Heuristics（启发式）系统来实现灵活的路径规划。其核心是基于A算法的变体，结合了反射机制和特性（Attribute）系统，这种设计允许开发者为不同类型的车辆和场景定制搜索行为，而不需要修改核心搜索算法。详细的对路径搜索用法可见使用手册 – 寻路启发器功能 – MDCS wiki。 系统采用的是启发式优先搜索算法（类似A*），通过以下关键组件实现：
   优先队列（Heap）：维护待探索节点，按优先级（代价+启发值）排序
   上下文信息（SearchStat和Container等）：表示搜索状态，包含当前位置、累计代价、优先级、路径信息、状态标记等
   启发式函数：通过自定义方法计算节点的评估值，指导搜索方向
   路径编译
   路径编译器将计划路线（表示为站点和路线的序列）转换为 AGV 可以理解和执行的可执行代码。这种转换过程可通过模板或插件的方法完成，类似于编译器。其使用方法见：使用手册 – Simple:coder（路径编译器）机制详解 – MDCS wiki路径编译的方法允许：
   车辆特定行为：不同的车辆类型可以有不同的代码生成策略
   站点特定操作：在特定站点的特殊操作（如装载/卸载，调整避障范围，或者为了解决一致性问题对站点微调等）
   轨道特定参数：速度控制、方向控制等
   复杂条件：可以使用javascript或者c#程序判断复杂条件（如一口气生成全向磁导航车的控制序列）
   总体任务逻辑
   下发任务流程图
   下发任务时，首先进行寻路，如通过FindRoute生成一个SegmentPlan，或者手动构造一个SegmentPlan。然后调用Compile方法得到CarProgram。Compile方法默认会做交管规划，若在参数中给了forecast:false，接下来可以Append多个SegmentPlan来继续延长路线并增加事件。
   无论Append与否，由于CarProgram需要做交管规划，若参数中给了forecast:false，则需要调用Forecast。调用Forecast时可以给一个escape参数，为一个SegmentPlan，用来设定逃逸路线，该路线只参与交管规划而不执行（可参见交管规划原理）。最后需要调用Queue进行提交。
   CarProgram一旦经过规划，必须提交，否则不允许后续生成针对该车的CarProgram。执行期间和Simple设计的交互几乎仅限于交管，详见AGV任务运行逻辑 – MDCS wik
   对于每个车，当前运行的CarProgram执行完毕后，可以继续执行下一个CarProgram。
   总结
   SimpleCore调度将AMR调度转换为“图的资源占用与释放”问题。首先启发式深度优先搜索寻路，可同时搜索可行区域、进行热力计算，并做好流量分配。资源（站点）获取顺序动态规划预计算，执行任务前通过动态规划预先搜索通行顺序的解空间，可通过包络、可达性预计算避免车体和静物之间的物理冲突。最后资源（站点）序列编译为动作脚本，而动作脚本可以完全离线执行，机器人仅在资源上锁/解锁时需要与调度通信。这使得本预计算集群调度具有以下优势：
   高抽象化 将AMR调度的底层数学问题剥离，软件工程架构更有优势。更容易针对不同车型和业务场景进行交付适配，可应对业务和资产快速变更的时代需求。
   高适用性 自动通行顺序预计算，无需针对不同业务场景人工配置交管规则。
   低通信复杂度 通信次数极低。AMR的任务已经预计算，网络波动时，不会导致AMR动作失控，AMR将在网络恢复后接续最新交管信息。
   低算力需求 相对于“遥控作业型”调度，预计算调度的算力需求低。数百台AMR的交管可在普通个人电脑上运行，无需高配置的服务器工作站。