在使用自动导引小车AGV(Automated Guided Vehicle)的物流仓库中，尤其是使用了多台AGV的情况下，AGV在搬运货物过程中，不可避免地会引发AGV的碰撞冲突和死锁，AGV发生碰撞冲突和死锁将直接导致物流仓库系统瘫痪。因此研究多AGV调度过程中避免冲突碰撞死锁是AGV研究问题的重要领域，不仅对于AGV调度系统理论的发展有重大促进作用，而且能够应用于实际物流仓库，解决物流仓库低吞吐量的问题。

        对于调度算法，整体上可以分为离线调度算法和在线实时调度算法。对于离线调度，系统可以在调度前构建并优化AGV的行驶路径，然而离线调度并不适用于实际应用中物流仓库的工作环境，具有较低的实际应用价值，一般适合于理论研究。对于实时在线调度，则可以根据系统实时状态信息的改变去动态调度AGV，保证AGV在实时环境变化的过程中依然能够顺利运行，实时在线调度方法比较适合于实际的应用场景。

        关于多AGV的实时在线调度算法，S.C.Daniels、G.Desaulniers、R.H.Möhring等提出的在线实时调度算法尽管能够一定程度上处理多AGV的实时调度问题，但因其时间复杂度和空间复杂性方面相对较高，因此仍然无法满足实际物流仓库系统吞吐量的需求。

        本文提供一种多AGV的实时动态解锁调度方法，时间复杂度和空间复杂度相对较低且能够提高物流仓库系统吞吐量，提高物流仓库系统的工作效率。

为实现上述目的，具体步骤包括：

步骤S1：基于图论对多AGV运行地图进行数学建模，将AGV的路径抽象为图形的边，AGV经过的站点抽象为节点，则运行环境抽象为一个由节点和边构成的图G=（V，E），V={v1，v2，...，vn}是所有节点的集合，E={e1，e2，...，em}是所有边的集合，n为节点数，m为边数，如果∈E，则表示两个节点之间的一条边，图形的存储结构通过邻接矩阵或邻接表来实现。

步骤S2：初始化地图、AGV小车列表、站点列表。

步骤S3：每一辆AGV。
步骤S4：判断当前AGV的站点序列siteSet是否为空；如果为空，表示当前AGV空闲，进入步骤S5；如果不为空，表示当前AGV忙，进入步骤S6。
步骤S5：判断任务队列是否为空，如果为空，回到步骤S3；如果不为空，从任务队列中取出任务T，通过最短路径搜索算法获得最短路径的站点序列R=(P1，P2，...，Pk)，Pk的值为当前AGV将要经过的具体站点，将站点序列R分配给当前AGV，并将当前AGV写入站点序列R经过的所有站点的站点链表ListK，站点链表数据结构表示每个站点对应各自的一个链表，链表中元素表示要经过当前站点的AGV顺序，然后回到步骤S3。
步骤S6：获取当前AGV的站点序列siteSet的头元素P1和次元素P2,根据头元素P1和次元素P2的值寻找相应站点的站点链表ListK。
步骤S7：判断相应站点的站点链表ListK的头元素是否均为当前AGV；如是，则执行调度，并删除P1对应的站点链表ListK的头元素，更新当前AGV的站点序列siteSet，回到步骤S3；否则等待，不执行调度，回到步骤S3。


从地图运行角度，以下详细阐述本方案：

（1）计算机开发环境:任意系统平台(Windows/Linux/Mac)下的任意编程语言(C/C++，JAVA，C#等)。
（2）通过计算机编程语言构建地图相关的图数据结构、站点链表数据结构、任务队列数据结构。图数据结构表示当前地图中各个站点的连接关系；站点链表数据结构表示每个站点对应各自的一个链表，链表中元素表示要经过当前站点的AGV顺序；任务队列数据结构表示存储任务的数据结构，任务队列中元素的排列顺序即为任务的先后到达顺序。

        假设两台AGV的分配顺序是agvA>agvB，第一个任务序列为(0，3，4，8)，第二个任务序列为(2，3，4，5)。agvA首先被分配任务，如图2所示的浅色路径序列，将第二个任务分配给agvB，如图2所示的深色路径序列。由于agvA的（3，4）路径和agvB的（3，4）路径是重叠路径，因此存在路径覆盖，即在调度过程中发生冲突，因此深色线条放置在浅色线条下方，表示agvB优先级低于agvA，允许agvA先通过。绘图之后，路线图如图2所示，为了方便理解，每个路径都标记了通过它的所有AGV调度顺序，例如，路径（3，4）上方的字符串“AB表示路径（3，4）存在路径覆盖，agvA先通过agvB后通过。
接下来开始使用本方案进行调度，调度系统的初始状态及每一步调度后的路径状态如图2所示。

        开始调度，每个AGV依次遍历，对于agvA，下一个调度路径为（0，3），没有路径覆盖，可以调度agvA，对于agvB，下一个调度路径为（2，3），3号站点被agvA占用，等待调度。
继续遍历每个AGV，对于agvA，下一个调度路径为(3，4)，标记字符串为“AB，存在路径覆盖，但agvA在站点链表的表头，仍然可以调度agvA，调度完agvA后，3号站点链表的表头变为agvB,对于agvB，下一个调度路径为(2，3)，agvB在站点链表的表头,可以调度。

        继续遍历每个AGV，对于agvA，下一个调度路径为(4，8)，无路径覆盖，可以调度agvA，调度完agvA后，4号站点链表的表头变为agvB。对于agvB，下一个调度路径为(3，4)，无路径覆盖，agvB在站点链表的表头，可以调度。

        继续遍历每个AGV，agvA空闲，对于agvB，下一个调度路径为(4，5)，无路径覆盖，agvB在站点链表的表头，可以调度，路径完成。