上图由Mathematica造作
1 AGV及其调度问题
1.1 AGV是什么？
国度尺度[ 1 ] ^{[1]}
[1]
对AGV 的界说是：
AGV（Automated Guided Vehicle 自动导引车）：设备有电磁或光学等自动导引装置，由推算机节造，以轮式移动为特点，自带头力或动力转换装置，并且可能沿划定的导引蹊径自动行驶的运输工具，通常拥有安全防护、移载等多种职能。
通俗的讲，AGV 就是一个用来运输的移动机械人，它是一个搬运工，把货物从A处运到B处，因而AGV的大部门钻研也是蕴含在移动机械人领域内的。
1.2 AGV调度系统是什么？
国度尺度[ 1 ] ^{[1]}
[1]
对AGV调度系统的界说是：
调度系统（Dispatching system）：上位节造系统中用于工作调度、车辆治理及交通治理的节造软件。
在深刻之前，为了便于理解，先说明根基概想的寓意。
● Dispatch（调派）：指派一个AGV去执行一个运输工作。
Dispatching is the process of assigning a transportation job to an AGV[ 2 ] ^{[2]}
[2]
.
● Schedule（狭义上的“调度”）：分配一批运输工作给一组AGV去执行。
Scheduling is the process of dispatching a set of AGVs to a batch of transportation jobs[ 2 ] ^{[2]}
[2]
.
The aim of AGV scheduling is to dispatch a set of AGVs to achieve the goals for a batch of pickup/ drop-off (or P/D for short) jobs[ 3 ] ^{[3]}
[3]
.
● Route（蹊径规划）：天生所有被指定 AGV 的蹊径使其能实现各自被指派的工作。在机械人领域，蹊径翻译为 path ；而在 AGV 领域通常使用 route 暗示类似的概想，翻译为“路线、轨路”，它通常暗示固定的不断时改观的蹊径。path 只能用作名词，route 还能够作为动词，暗示“为…指派蹊径”。本文我们不纠结这些奥妙的细节，统一称其为蹊径。
Routing is the process of determining routes for a set of AGVs to fulfill their respective transportation jobs[ 2 ] ^{[2]}
[2]
.
Once the scheduling decision is made, the mission of routing is to find a suitable route for every AGV from its origin to destination based on the current traffic situation[ 3 ] ^{[3]}
[3]
.
单独看一个AGV的工作并不复杂。例如机床要加工零件时通过更上层的MES节造系统给AGV的调度系统发出要求号令，后者调派（dispatch）一台 AGV 掌管把原料从仓库运送到机床。这个过程能够被称为一个工作（job），一个工作就是在一对工作地址之间移动。在这个例子中，机床只提出需要（我要在什么功夫加工什么零件），至于选择哪个 AGV 运送零件原料，AGV 该沿哪条路线活动，这些都是调度系统的工作。调度系统一旦为AGV指定好蹊径后，AGV上的车载节造器会凭据指令实现具体的活动节造工作，例如快率维持在几多，遇到路口转向时轮子怎么动弹等等。所以在一个齐全的大系统中，AGV调度系统位于上层节造系统和底层节造系统的中央，其到管家的作用。
但是对于多个AGV，调度问题就会变得极度难题，并且AGV数量越多，难度越大。因而，调度系统成为AGV行业的一个关键技术[ 4 ] ^{[4]}
[4]
。而可能调度的AGV数量也成为评价一个调度系统壮大与否的沉要指标。凭据笔者的判断，固然目前从事AGV行业的企业好多，但是拥有自主调度系统的企业并不多，而可能真正把调度系统优化的很好、可能最高效能地利用AGV系统的企业更是寥若晨星。当然，若是站在AGV厂家的态度，他们并没有太大的动力把调度系统做的很高效。由于提高伐度效能会削减AGV的投入量，这意味着卖出的AGV就少了。
对现实利用的AGV调度系统软件，它的职能通常是极度丰硕的，通常蕴含：工作治理、车辆状态监控、蹊径规划、地图编纂、数据库查问等。
1.3 AGV调度问题
大无数人固然不定相识调度的步骤和细节，但对它或多或少都有一些直觉上的感性意识。若是你在火车站或者飞机场用电脑看本文，那么你同使佚在经历两种调度过程：大量的火车和飞机必要调度，与此同时你电脑里的操作系统也在对大量的工作进行调度。当好多事务同时产生，并且存在竞争时就必要调度了。若是只有一个事务产生，那么所有资源都由这个事务摆布（火车能够在职何一条铁轨上跑），我们不必要调度 ；若是多个事务同时产生，但是没有竞争关系（美国的一列火车和中国的一列火车），我们也不必要调度，由于它们不会产生矛盾。
首先，我们应该能分辨一个问题是不是调度问题。如果工厂中只有一台AGV在工作，此时调度问题就退化成单一的蹊径规划问题了。由于不必要思考该将工作分配给哪台AGV的问题，也不必要思考在一个路口谁先走谁后走的问题。所以调度问题的前提是多个AGV共享蹊径网络，换句话说AGV之间存在资源抢夺。就像马路上的车辆一样，谁都想怎么快怎么开车，若是每个司机都只思考自己而不思考对方，那么后果很可能是谁都别想走（拥挤在一路）。因而，幼我钻营自己部门的最优解却造成了全局的最差解，所以调度是有存在的必要的，并且有时很沉要（红绿灯、交警都起到某种“调度”的作用）。
无数情况下，调度系统必要两全所有AGV的行为（上帝视角），它钻营的不是某几个AGV的最优解（当然它有能力这么做），而是整体的最优。我们能够设想一下，能不能做一款调度软件来调度一个城市里所有的车辆，让整体解是最优的（例如所有人耗费的汽油加起来至少）。这个最优解肯定存在，但是现实上却险些不成能解出来，由于有两个难点。首先，调度系统要把握海量的信息，好比张三八点从家里开车到单元，赵四九点开车送孩子，王五的车油量不够，必要中途加油等等。更难题的是这些信息是改观的，例如张三的车开着开着抛锚了把路堵死了。第二个问题是，调度问题的复杂度随着参加者的数量呈指数增长。若是只有几十辆车，此刻的算法和推算机硬件还能勉强解决，若是要处置成千上万辆车，那生怕只有上帝能力做到了。信息不足和维度谩骂是调度问题面对的重要难题。扯远一点，其实打算经济也面对同样的问题，要对经济进行打算必要决策者把握海量的信息，并占有超等大脑，在那个无数人连电脑是什么都不知路的落后年代搞打算经济必然不会太好。
正由于调度问题是极其复杂的，所以大无数时辰我们只能退而求其次找一个说的从前的近似最优解，这也是现实生涯中每个路口的交通讯号灯闪动背后的逻辑。
相向碰撞 追击碰撞 节点碰撞
2 蹊径规划
多个AGV的调度必要规划分歧AGV的蹊径，所以我们先相识下现有的蹊径规划步骤。AGV是个听话的笨伯，若是调度系统想让一个AGV从A走到B，它不能单一地将A和B站点的信息给AGV，而是要将A到B之间的齐全蹊径通知AGV[ 5 ] ^{[5]}
[5]
。目前普遍用“图”（graph 数学概想）对AGV的行驶空间进行建模，“图”由节点和边组成。所以AGV的行驶蹊径能够暗示为一系列相邻的节点。
2.1 Dijkstra步骤
Dijkstra步骤是一种经典的搜索蹊径的步骤，它的逻辑不是出格复杂，有好多介绍它的文章。但是若是照本宣科的讲它的步骤，你能够复现但不定能真正理解，由于它背后暗藏着深厚的数学布景。为此，笔者写了一篇博客解说它的道理：Dijkstra步骤入门。
3 调度步骤
由于AGV调度问题很有理论深度，所以吸引了大批的学者，他们分歧的角度会商这个问题，提出了各类花哨的步骤。不外好多理论难以转化成现实可行的步骤，所以现实和理论有很大的差距。
3.1 多机械人协调问题
AGV调度问题能够当作多机械人协调问题（Multi-Robot Coordination）的特例。多机械人共享一个环境，若何协调它们的活动使所有机械人都能能达到指标。会商多机械人协调问题是为了对换度问题有更好的理解。最早的步骤也是最单一的步骤之一，就是为分歧的机械人设置分歧的优先级（Priority）。优先级高的机械人先规划自己的蹊径，优先级低的机械人将比它高的机械人的蹊径视为阻碍物，进而再进行规划。当然这种步骤有个显著的弊端：优先级高的机械人过于霸路，它把所有的路都堵死了，以至于优先级低的机械人怎么也找不到路。这时我们就要调整优先级了。
引用文件
[1] 《GBT 30030-2013 国度尺度 自动导引车(AGV)——术语》.
[2] Comparison of Routing Strategies for AGV Systems using Simulation, Mark B. Duinkerken, 2006.
[3] Scheduling and Routing Algorithms for AGVs: A Survey, Qiu Ling, 2002.
[4] 全面解读科尔摩根NDC中国市场战术.
[5] AGV调度系统的设计，戴志存，物流技术与利用, 2015.
[6] openTCS-4.2.0.
————————————————
版权申明：本文为CSDN博主「robinvista」的原创文章，遵循CC 4.0 BY-SA版权和谈，转载请附上原文出处链接及本申明。
原文链接：https://blog.csdn.net/robinvista/article/details/73348711
