### 根据调度系统对资源的高效利用，容错性等设计需求。调度方法应该遵循以下常用原则：
* #### 总行驶路径最短
#### 在对任务进行调度时，遵循总的行驶路径最短的原则对任务进行路径分配和优化。
* #### 等待时间最短
#### AGV系统中任务的生成是动态且随机的，当任务请求过多而可用AGV数量较少时，就会出现任务等待的现象。并且AGV在运行过程中出现冲突也会出现等待的现象。要保证运输效率则需要降低任务等待和冲突等待的时间。
* #### AGV配置数量最少
#### 根据工作强度权衡AGV配置数量。AGV数量过多会存在部分AGV处于闲置状态，造成资源浪费。如果AGV配置数量太少则会使任务排队时间边长，影响系统效率。所以在保证运输任务效率的前提下啊，尽可能减少AGV数量。
* #### 成本最少
#### 减少成本的本质是提高系统的运行效率。总行驶路径最短，等待时间最短和AGV配置数量最少都是为了让系统的成本最少。
>
### 根据上述原则，几种常用的任务分配调度算法如下：
1. #### 先来先服务算法：
#### 由任务生成时刻的早晚将决定任务优先级的高低。即任务生成时刻越早优先级越高，任务执行的先后顺序取决于优先级。调度系统通过维护一个队列数据结构来存放待执行的任务，队列中的任务为先进先出。当存在闲置AGV时，调度系统将队列中的首位任务派发给相应AGV。重复上述流程直至待执行任务列表为空。流程图如下图所示：
:-: 
Fig. 1 FCFS 算法流程
>局限：先来先服务由于使用固定优先级，忽略了任务执行时间的约束，总的任务等待时间不一定最短。
2. #### 贪心算法：
#### 贪心算法只顾眼前的利益。对于一个需要逐步解决的问题，贪心算法在每一步都会选择以某种原则看来当前的最优解。即贪心算法每一步都选择局部最优解。通过这样的方式获得的解不一定是全局最优解，但会是全局最优的近似解。比如以成本最少为原则，算法的流程为基于先来先服务的基础上，调度系统会选择将队列首位的任务分配给距离目标点（任务开始位置）最近的闲置AGV执行，确保每次调度AGV移动成本为当前最低。流程图如下图所示：
:-: 
Fig. 2 贪心算法流程
>通过贪心算法得到的总成本不一定是最小的。
3. #### 基于动态优先级的智能调度：
#### 先来先服务等算法使用的优先级都是固定值不够灵活，且不一定适合实际使用场景。优化解是根据任务本身的需求和应用场景来设计合适的调度算法，显然使用动态优先级更合理且更有利于提升系统效率。
## 一种待执行任务动态的实时优先级方法
#### 设计原则如下：
1. #### 待执行任务的相对截止期越小则任务的实时优先级越高。
2. #### 对于相对截止期优先级完全相同的任务，任务的生成时刻越早的，任务的实时优先级越高。
#### 为了设计优先级，首先我们可以设计待执行任务的满意度指标：
:-: 
Fig. 3 待执行任务的满意度
#### 如Fig. 3所示，`$ t_{born} $`代表一个任务生成的时间， `$ t_{wait} $`表示该任务的最大等待时间和 `$ t_{dead} $`表示该任务截止期（过后任务被放弃）。而任务分配阶段的系统满意度会随着等待时间的增长而降低。注意：大于等待时间后还没分配给AGV则此任务无法在截止期前完成也应该不再参与调度分配。那么待执行任务的优先级（同样是动态）可以做如下设计：
:-: 
Fig. 4 待分配任务优先级
#### 其公式可以表示为：
```[tex]
f(t) =
\begin{cases}
0,\quad t < t_{born}\\
\tfrac{2(t - t_{born})}{t_{wait} - t_{born}} , \quad t_{born}
\leq t \leq \tfrac{1}{2}t_{born} + \tfrac{1}{2}t_{wait} \\
1 , \quad \tfrac{1}{2}t_{born} + \tfrac{1}{2}t_{wait}
\leq t \leq t_{wait} \\
0, \quad t > t_{wait}
\end{cases}
\tag{1}
```
#### 该公式的表达含义为：一个任务从`$ t_{born} $`开始直到此任务 `$ t_{wait} $`（相对于任务生成时刻）的一半为止，该待执行任务的优先级线性增大（从0到1）。从此任务 `$ t_{wait} $`（相对）的一半到 `$ t_{wait} $`为止，该任务优先级转将转变为最高优先级（加急）。若任务由于各种原因直到`$ t_{wait} $`也任处于等待状态，则将其优先级转变为负值（确保如果在队列中只存在该任务也将不再参与调度分配）直到`$ t_{dead} $`时刻被放弃。
#### 任务分配调度算法：所有任务的默认初始优先级为0，一旦任务生成其优先级就会根据函数变化，越早生成的任务优先级越先开始增加。对于需要强制优先分配的任务则赋予该新任务初始优先级为2。并且一个任务设计的截止期越小，任务的优先级会变化更快。对于同样处于最高优先级的待分配任务将分别计算它们的剩余可等待时间`$ t_{rest,i} = t_{wait, i} - t_{i} $`，且`$ t_{rest,i} $`最小的任务最先选择AGV进行分配。AGV选择方法：（1）当闲置AGV只有一个时，待执行任务分配给该AGV；（2）当存在多个闲置AGV时，待执行任务分配给离目标点/任务开始位置最近的AGV。以上算法满足设计原则1和2。注意：当存在足够大量的闲置AGV时，此算法会等同于先来先服务算法。而在AGV负载较饱和的系统下，每个待分配任务的实时优先级是唯一且确定的数值。
>#### 同时该满意度指标也可以用来对系统的执行效率进行评价：
>#### 例如统计`$ t $`时间段内满意度`$ g(t) $`并计算其平均值。那么：如果`$ g(t) $`的平均值>很大则说明处于闲置的AGV数量较多，可以适当减少AGV的数量来降低成本；如果`$ g(t) $`的平均值很小调度系统的效率很低，需要增加AGV的数量以保证运输的效率；如果`$ g(t) $`的平均值为0则调度系统的稳定性出现问题，需要系统自检和诊断。（智能调度）
```
```
### 根据上述原则，路径规划算法如下：
1. #### 基于合作的A*方法
#### 由于路径规划算法设计上的原则是总行驶路径最短，调度系统高效及避免冲突的发生。使用A*算法能为每一个AGV搜索最优最短的路径。由于A*算法在路径规划层面没有考虑避免冲突，在多AGV运行系统中需要为每一个AGV内置协调器。由此可以改进为基于合作的A*算法：将原本二维地图变为三维（加上t时间维度），AGV会获取其他机器人的A星搜索路径并查询是否存在t时刻会导致和其它机器人发生碰撞。如果经过预测存在碰撞时刻，其中一个机器人在协调器的作用下会进行路径规避，此时该AGV会将另一个机器人的t时刻后的运行方向当作临时障碍物，并进行路径的重规划。基于合作的A*方法可以视为路径规划 + 协调调度的算法。
> #### 基于合作的A*方法需要先对每一个AGV做出最短路径规划，而后还要进行一次路径重规划。这样做的缺点很明显：对通信的要求很高；每一个AGV路径的重规划都可能导致其它AGV也要做出路径调整，增加计算成本降低系统稳定性；路径规划初期只考虑单机最短路径，使得在经过路径重规划后的AGV总路径不一定是全局最短路径。这种方法不如在考虑各节点是否可用的前提下进行全局最短总路径规划。
2. #### 时间窗口算法：
#### 可以通过认为调度过程中的路径节点拥有两种状态——被占用状态和可用状态，进而将每一个路径节点划分为由占用状态和可规划状态的时间组成的离散时间序列。在一段连续的时间内，一个路径节点只能被一辆AGV占用，将小车从驶如该节点到驶出该节点的时间段称为时间窗。而在多AGV调度系统中，系统根据当前路径规划的结果计算出地图中每个路径节点的时间窗，最终获得每一个路径节点的可规划时间段。后续AGV的路径规划将参考每个路径节点的可规划时间段，理想状况下AGV在运行过程中不会产生任何节点冲突。时间窗口法属于基于预测式、估算式的控制方法，以全局角度对调度系统进行优化，且存在总路径最短的全局最优解。
> #### 局限：时间窗口法应用过程中，假定了AGV匀速运行来计算节点时间序列。实际应用中AGV难以全局维持恒定恒定速度运行，这会体现在估算时间序列的误差累积上（无上限）。而误差累积可能导致节点冲突现象的产生，进而影响系统稳定性。
#### 时间窗口如下图所示：
:-: 
Fig. 5 时间窗口
#### 时间窗口是AGV从驶入节点到驶出节点的时间段。如Fig. 5所示，虚线所示正方形区域为占用区域，其边长为`$ D $`（`$ D $`应该略大于AGV的车宽）。当没有AGV出现在该区域时，其所在节点为可用状；一旦该区域内出现AGV，其所在节点变为占用状态，AGV处于驶入状态。故时间窗口可以理解为AGV从进入占用区域到完全离开该区域所用时间`$ t $`。假设AGV驶入占用区域的初始速度为`$ v_o $`，`$ t $`的计算公式如下:
```[tex]
t = \tfrac{L + D}{v_{o}}
\tag{2}
```
#### 实际上，AGV经过节点的方式共有三种分别为：直线通过节点（同上述方式），转向通过节点和从起始节点出发。转向通过节点的方式如下图所示：
:-: 
Fig. 6 以转向通过的方式占用节点
#### 假设AGV转向经过占用区域的路径为以下圆弧路径：
:-: 
Fig. 7 转向通过节点路径
#### 如上图所示，转弯路径的长度为`$ \tfrac{\pi \cdot D}{4} $`，假设AGV转弯速度为`$ v_1 $`,那么转向通过节点的时间`$ t $`的计算公式如下：
```[tex]
t = \tfrac{L + \tfrac{\pi \cdot D}{4}}{v_{1}}
\tag{3}
```
#### 从起始节点出发的占用解点方式如下图所示：
:-: 
Fig. 8 从起始点出发的方式占用节点
#### 因为在这种情况下AGV的初始速度为`$ 0 $`，假设AGV从静止状态加速到以恒定速度`$ v_0 $`延指定方向直线运动的时间是`$ t_{delay} $`，那么通过节点所用时间`$ t $`的计算公式如下：
```[tex]
t = \tfrac{\tfrac{L}{2} + \tfrac{D}{2}}{v_{0}} + t_{delay}
\tag{4}
```
>
#### 时间窗口优化方法：
1. #### 实时更新节点法
#### 由于AGV实际经过节点的时间相较于估算结果存在误差，可以采用AGV每经过一个路径节点都向调度系统发送信息，使调度系统得到AGV到达该节点的准确时间信息，并基于此更新剩余路径节点的时间窗信息。以此消除由于估计速度的偏差或突发事件对时间窗口的不良影响。
> #### 由于偏差一直存在，导致频繁的更新（每个AGV每经过一个节点就要进行一次更新），这种方法会极大的增加中央调度器的计算负担。而且频繁的更新也可能大量的AGV路径重规划流程，复杂且不利于系统稳定性。路径重规划的缺陷也使得上述优化方法有悖于时间窗口算法全局最优的设计初衷（重规划的路径不再是之前全局最优解）。
2. #### 预测式 + 柔性的控制方法
#### 经分析，时间窗口算法假设AGV以恒定速度行驶并不合理。因为AGV以恒定速度在指定时刻到达指定位置的假设反过来限制了时间向全局最优的逼近。那么可以考虑替换AGV匀速运行的假设为：假设AGV不一定以匀速运行，但一定在指定时刻到达指定节点处（到达节点时刻与假设AGV匀速运行来估算的时间窗相同）。使用柔性的控制方法可以使AGV在路径上的运行过程中保证在指定的时间到下个路径节点，确保调度系统中时间窗信息不会产生偏差。
> #### 时间窗口法结合柔性的控制方法与实时跟新节点相比不使用路径重规划，不仅简化了流程，还能够更好的落实时间窗口法预测的路径规划最优解。
```
```
### 根据上述原则，协调调度算法如下：
#### 如果由于路径规划层面上的问题而导致无法避免地发生了冲突，此时需要协调调度算法来进行冲突处理。因为在系统环境建模层面上避免了相向冲突现象的发生（使用单向图），只用考虑节点冲突和赶超冲突的协调调度。这相当于只需要对发生冲突的AGV做出相关决策，让其中一辆或多辆AGV优先行驶就能解决阻塞和预防死锁。在协调调度决策模块中，起到决定哪一个AGV先走，哪一个AGV等待的作用的是优先级。与先前任务分配的优先级相同的理由，AGV移动过程中同样不适合使用固定的优先级。由于综合的因素，在运行过程中AGV的优先级可以是变化的。以下是一种实时的动态AGV移动优先级算法：
## 一种AGV执行移动任务期间动态的实时优先级方法
#### 首先可以设计对任务的满意度指标来对AGV运行系统效率进行评价：
:-: 
Fig. 6 AGV运行过程满意度
#### 其公式可以表示为：
```[tex]
f(t) =
\begin{cases}
0,\quad t < t_{alloc}\\
\tfrac{t - t_{alloc}}{t_{best} - t_{alloc}} , \quad t_{alloc}
\leq t \leq \tfrac{1}{2}t_{alloc} + \tfrac{1}{2}t_{wait} \\
\tfrac{t_{dead} - t}{t_{dead} - t_{best}} , \quad t_{best}
\leq t \leq t_{dead} \\
0, \quad t > t_{dead}
\end{cases}
\tag{5}
```
#### 如Fig. 6所示，任务满意度的取值范围是0 ~ 1。图中三个时间结点的意义是：`$ t_{alloc} $`代表AGV接到系统分配任务的时间， `$ t_{best} $`表示任务指定AGV到达目标地点的时间和 `$ t_{dead} $`表示任务因迟迟未完成而被放弃（到了截止期）。在这个分段线性函数中，时间段`$ t_{born} - t_{best} $`和`$ t_{best} - t_{dead} $`的长度相等且均为系统预测机器人从接到任务直到到达目标地点消耗的时间。
>#### 该函数主要表明AGV在指定时间到达指定位置则系统的满意度最高。其重要性在于机器人在`$ t_{best} $`时刻到达目标点是基于预测的控制方法以及柔性的控制方法等调度算法的最>优解。此外，也可以统计一段时间内的AGV运输过程满意度来计算平均满意度`$ g $`：如果 `$ g $`值接近1则说明当前系统中AGV数量合适；如果 `$ g $`偏小则要分析当前系统中AGV数量是否过少/多，并适当增加/减少AGV数量以提升效率/防止冲突频繁发生。
#### 然后可以设计AGV运输过程中的优先级（动态）如下图所示：
:-: 
Fig. 7 AGV运行过程优先级
#### 如果在超过`$ t_{best} $`时刻后AGV还未到达目标点，则AGV的优先级会转变为最高优先级。若在任务截止期后仍未到达，则任务将被放弃，同时AGV在接到下次任务前（如果是one shot任务类型）的优先级也会变为最低。
#### 冲突解决调度算法 （交通规则）：
#### 根据节点冲突的两种类型，出现节点冲突时按以下交通规则法解决冲突：
#### 两个AGV自身尺寸`$ d $`距离节点的距离分别为`$ d_1 $`和`$ d_2 $`，如果`$ d_1 $`和`$ d_2 $`同时小于`$ d_0 $`时触发交通规则：
1. `$ d_0 > d > d_1 $` 或 `$ d_0 > d > d_2 $`即两辆AGV中一辆驶入节点另一辆驶出节点，则距离交叉点小于自身`$ d $`的小车先通过，另一辆则停止等待直到前一辆车尾离节点距离`$ > d $`
2. `$ d_0 > d_1 > d $`即两辆AGV同时驶入节点，两辆机器人都可能通过。此时优先级高的先通过，当先通过机器人车尾`$ > d $`后接触另一小车等待；如果两车优先级相等，比较`$ d_1 $`与`$ d_2 $`大小，较小者先通过。
#### 赶超冲突的解决方法：
#### 预设定碰撞距离为`$ L_1 $`，安全距离为`$ L_2 $`。当前方AGV与后方AGV的距离小于`$ L_1 $`时后方AGV触发碰撞防护停车。后方AGV等待到与前方AGV间距大于`$ L_2 $`后开始继续执行当前任务。且碰撞距离与安全距离的关系为：`$ L_1 < L_2 $`（为了避免后方AGV间歇性的停车）。
## 一种AGV优先级的改进方法：
#### 为使调度系统更稳定，可以将小车驶入交叉点的初始速度和小车此时距离目标点的距离考虑进优先级，则优先级变为：
```[tex]
f_{1}(t) = f(t) + \alpha \cdot v_{init} + \beta \cdot d
\tag{6}
```
#### 其中系数`$ \alpha $`和`$ \beta $`分别为初始速度和目标距离所占优先级权重。根据此算法，具备初始速度较大的AGV将可能优先同通过。为了避免有AGV由于停车而速度为0导致持续让行具备速度AGV的恶性现象发生，我们可以将停车等待时长也考虑入优先级函数：
```[tex]
f_{1}(t) = f(t) + \alpha \cdot v_{init} + \beta \cdot d + \gamma \cdot t_{halt}
\tag{7}
```
#### 上式中`$ \gamma $`是停止时间的权值。如此，当AGV随着停止时间的增加，也能够使其具备大于拥有初始速度的AGV，可以避免因没有初始速度引起的长时间等待。
