智能车间AGV运送任务序列分配及路径规划

Task Sequence Allocation and Path Planning of AGV Transportation in Intelligent Workshop

摘要: 针对智能制造车间多自动导引小车的调度和路径规划问题，需要同时考虑每台AGV的工作是装卸和运输工件，提出了AGV分步任务调度及路径优化模式，首先基于最小化最大运送完工时间为优化目标建立数学模型算法和基于工件加工紧急程度的物料运输任务分配算法，将货架和加工设备间的所有工件运送任务序列分配给相应的AGV，生成每台AGV初始可行路径。然后设计AGV冲突检测及防碰撞算法，规划多台AGV在车间工作场所全局无碰撞行走路径，并可以根据运送任务动态调整路径。最后通过算例验证方法的有效性，能有效解决多台AGV任务分配和基于运送任务序列避免冲突碰撞的路径规划，提高AGV工作效率。

Abstract: In order to solve the scheduling and path planning problems of multi AGVs in an intelligent manufacturing workshop, it is necessary to consider loading and unloading, and transporting the workpiece of each AGV at the same time. A step task scheduling and path optimization mode of AGV is proposed. The process is as follows: Firstly, a mathematical model algorithm and a material transportation task allocation algorithm based on the degree of workpiece processing urgency were established for the optimization objective, and all workpiece transportation task sequences between shelves and processing equipment were assigned to the corresponding AGV to generate the initial feasible path of each AGV. Then, the AGV collision detection and anti-collision algorithm are designed to plan the global collision-free walking path of multi AGVs in the workshop, and the path can be dynamically adjusted according to the delivery task. Finally, an example is given to verify the effectiveness of the method, which can effectively solve the task allocation of multi AGVs and avoid collision path planning based on the transportation task sequence, and improve the work efficiency of AGV.

1. 引言

自动导引小车(Automated Guided Vehicle, AGV)被广泛应用于智能制造生产车间，凭借其高灵活性、稳定性、高效性，协同实现车间柔性自动化生产 [1]。AGV具有的按需求灵活自动呼叫、信息实时传感、根据环境控制运输节拍等功能，能够提高生产车间物料搬运传输效率。但是，如何设计智能制造车间AGV工件运送任务调度的优化算法和规划在车间工作场所内工件运送的行驶路径，准确及时地执行并完成生产物料运输任务，是智能制造车间AGV工作亟待解决的问题。

基于制造执行系统(Manufacturing Execution System, MES)的智能制造生产车间，AGV的工作主要是装卸和运送工件到达指定位置，保证工件及时运送到设备工作台或将完工工件及时运送到货架，和车间设备协同工作，避免机械设备空闲或生产延期，保障加工设备的工作效率。AGV的任务调度以最小化AGV工件运送总时间为目标，确定工件运送任务的执行顺序和AGV运送工件时的行驶路径，防止多台AGV行驶过程中发生冲突和碰撞。

关于AGV的研究文献有很多。殷文正等 [2] 应用启发式算法、李天童等 [3] 应用栅格地图求解了路径规划问题。文献 [4] [5] [6] 应用神经网络进行路径优化模型的求解，提高了路径规划求解速度。文献 [7] 应用改进遗传算法提高了路径规划解的质量。文献 [8] 将决策理论和随机时间路径规划结合，调控最佳行驶路径。文献 [9] [10] 应用混合PSO-GA算法、文献 [11] 应用多目标协同进化算法解决AGV的调度问题。文献 [12] 提出了协同AGV的新型控制策略。

综上AGV路径规划的文献，多是在已知障碍物的静态环境下规划AGV防冲突碰撞路径，对于多台AGV协同工作的智能制造生产车间不适用。已有文献的调度算法在智能车间适用性不强。AGV是智能制造车间生产中装卸和运输工件及物料的必备设备，因此，在智能车间对多台AGV中的工件运送任务分配、任务排序、运送路径规划及行驶过程中防冲突碰撞问题进行研究。对于拟解决的问题所构建的算法，在AGV任务调度和路径进行优化并提出AGV冲突检测及防碰撞算法，能有效地解决在智能制造车间多个AGV共同工作产生的相关问题，从而能够提高智能制造车间AGV的工作效率。

2. AGV调度及路径优化框架

在车间实际生产过程中，会有多个工位同时需要多台AGV向各工位运送工件，需要对AGV运送工件的顺序进行分配，并对AGV运送工件时的行驶路径进行优化和防冲突碰撞研究，使AGV执行任务总的行驶路径更短的同时，为所有工位或货架完成工件运送及装卸服务。针对AGV路径规划与任务分配问题，结合制造业生产线工艺流程，设计分步优化算法模式，如图1所示。

Figure 1. AGV scheduling and path step-by-step optimization mode

图1. AGV调度及路径分步优化模式

首先，设计时间最小化的数学模型算法或基于工件加工紧急程度的物料运输任务分配算法，将货架和加工设备间计划时间内所有工件运送任务，按规则分配给当前正处于空闲状态的AGV，动态更新当前AGV任务序列，并生成每台AGV初始可行的工件运输任务的运送路径。然后，设计AGV冲突检测及防碰撞算法，规划多台AGV在智能车间规定工作区域内全局无碰撞行走路径，并可以动态调整AGV运送路径。

2.1. AGV初始可行路径

2.1.1. AGV运送任务序列生成

1) 基于时间最小化数学模型的AGV任务分配根据生产计划，将工件运送任务分配给合适的AGV，确定其任务执行顺序，构建AGV任务分配模型，模型的目标为AGV完成所有物料运送任务的时间最短，相关设置和假设如下。

a) 各AGV相同，运输速度相同且匀速；

b) 行驶过程保持安全距离，等待时间较短，忽略不计；

c) 忽略设备开工准备时间；

d) 每台AGV每次最多执行一个工件运送任务，同理，同一工件运送任务只能被一台AGV执行；

e) 行驶通道上每个方向不超过两辆AGV，避免拥堵和冲突，超出容量则自动重新规划路径；

f) 设定生产车间栅格化处理，AGV沿栅格行驶，行驶速度假定每个时间单位行驶一个栅格，按走过的折线距离统计路程；

g) AGV工作时不断电，不会发生故障；

h) AGV运送任务完成后自动返回停靠位置。

建模使用的符号说明如下。

P和D分别表示工件上设备进行加工的运送任务及将完成的工件运送回货架的任务集合，分别表示为 $\left\{1,2,\cdots ,n\right\}$ 和 $\left\{n+1,n+2,\cdots ,2n\right\}$ ；N是运送工件任务集合，N = PUD；K是AGV集合，表示为 $\left\{0,1,2,\cdots ,m\right\}$，0表示停靠位置；A是车间位置点集合，A = NU0； $B_i^k$ 和 $E_i^k$ 是AGV k执行任务开始时间和完成时间， $i\in N,k\in K$ ； $\left(X_i,Y_i\right)$ 表示位置坐标，AGV每秒行驶一个栅格，则可 $X_i+Y_i$ 以表示行驶时间； $X_{ij}^k$ 为0-1变量，值为1时，k执行运送任务i后再执行任务j， $i\in N,j\in N,k\in K$，值为0时表示其他情况； $t_i$ 是执行任务i最小行驶时间； $T_{ij}^k$ 表示任务i完成位置到j开始位置最小行驶时间； $P{t}_i$，工件加工时间； $e_i$ 生产计划中工件的计划加工时间或计划完工时间

构建数学模型，确定AGV的运送任务及执行顺序。

$\min Z=\underset{k\in K,j\in A}{\max }{E}_i^k+\left(X_i+Y_i\right)$ (1)

${\displaystyle \underset{j\in N}{\sum }{X}_{0j}^k}=1,{\displaystyle \underset{i\in N}{\sum }{X}_{i0}^k}=1\forall k\in K$ (2)

${\displaystyle \underset{k\in K}{\sum }{\displaystyle \underset{j\in A,j\ne i}{\sum }{X}_{ij}^k}=1\forall i\in N}$ (3)

${\displaystyle \underset{k\in K}{\sum }{\displaystyle \underset{i\in A,i\ne j}{\sum }{X}_{ij}^k}=1}\forall j\in N$ (4)

$E_i^k\ge Z_i^k\left(B_i^k+t_i\right)\forall i\in A,k\in K$ (5)

$E_i^k\ge e_i\forall i\in P,k\in K$ (6)

$B_{n+i}^k\ge E_i^k+P{t}_{i}i\in P,\forall k\in K$ (7)

$B_{n+i}^k\ge e_i\forall i\in D,k\in K$ (8)

$B_j^k\ge X_{ij}^k\left(E_i^k+T_{ij}^k\right)\forall i,j\in N,k\in K$ (9)

$X_{ij}^k,Z_{ij}^k\in \left\{0,1\right\}i,j\in A,\forall k\in K$ (10)

$B_i^k,E_i^k\ge 0\forall k\in K,i\in A$ (11)

式(1)为模型的目标函数，为各AGV完成运送任务的最大运送时间最小；其他为模型的约束条件函数。式(2)表示AGV从停靠位置出发，工件运达后返回原位；式(3)和(4)表示工件运送任务没有被遗漏；式(5)、(6)是确保任务执行的时间先后符合逻辑；式(7)和(8)作用同上；(9)是AGV按顺序执行任务，完成前序任务i后按栅格行驶到后序任务j，所以确保任务执行的时间先后也要符合逻辑；式(10)、(11)表示变量类型要求。

2) 基于加工优先级的AGV运送任务分配

以工件按生产计划完成最快为目标，提出基于工件加工紧急程度的AGV任务分配算法，图2为算法流程。基于智能车间制造执行系统制定的工件加工计划时间和完工时间，对所有运送任务按加工的紧急程度进行排序，形成全体工件任务序列。根据空闲即分配规则，将工件运送任务分配给已完成前序任务正等待任务分配的AGV，同时更新AGV的任务序列。重复上述过程直到所有工件运送任务分配给相应AGV，任务循环分配过程停止，最后形成各AGV的工件运送任务序列。

Figure 2. AGV transportation task allocation based on processing urgency

图2. 基于加工紧急度的AGV运送任务分配

2.1.2. AGV初始路径生成

为便于路径规划和路径的表达，将智能车间区域进行栅格化处理，各功能区用栅格表达，并按照所处的栅格位置进行编码，如图3所示。每个栅格表示一个位置节点，该节点可以是设备，也可以是AGV的行驶通道或货架。设备和货架前的栅格是AGV操作工位，AGV在此工位完成放料和取料动作。AGV空闲时停在停靠位，当收到任务指令时，AGV按运送任务序列编号将工件从当前位置运送到指定栅格位置，然后进行取料或放疗的操作。AGV在车间可行区域(图中1~12栅格节点)运送工件，按任务序列完成指定工件的装卸和运送。为确保车间生产线加工过程稳定，AGV在工作区按指令行驶，遵循在车间栅格通道行驶先横向后纵向原则，确定AGV执行每个任务的初始运行路径，并按此路径有序运行，降低在车间栅格通道行驶时的碰撞概率，高效完成工件运送任务。如当前运送任务是将货架2上的某一工件运送到设备1上进行加工，AGV的执行该任务的初始运送路径是栅格节点7→8→9→4→3，在起点7位置取货架上指定编号的工件，然后按此路径行驶到栅格终点3，将工件放置在设备1的机前指定位置。各AGV根据已分配的全部任务序列，形成全部运送任务的初始运送路径，用栅格节点编号按顺序表达。

Figure 3. Plane of grid intelligent production workshop

图3. 栅格化智能生产车间平面图

2.2. AGV冲突检测及防碰撞算法

AGV冲突的检测目的是对AGV初始运送路径进行实时更新，使车间AGV行驶场地中不存在两台AGV同时处于同一栅格位置的情况。通过 < position, time > 记录形式表示AGV在车间的当前栅格位置和行驶时间，position和time为非负整数。图4为AGV冲突检测及防碰撞算法。

Figure 4. AGV conflict detection and anti-collision algorithm

图4. AGV冲突检测及防碰撞算法

3. 算例验证

仍以上述栅格化智能车间作为两台AGV的工作场地，模型采用启发式算法，用Matlab编码求解。为比较2.1两种任务分配方法的效果，分别求解并比较计算结果，如表1，表中n为车间工件运送任务总量，用p1、p2表示AGV初始路径规划和防冲突碰撞两个阶段，t1、t2表示各阶段任务完成时间、d1、d2是对应时间差异率。在AGV初始路径生成阶段，两种任务分配方法计算AGV初始路径运行的总完成时间稍有差别，最大差异率是1.06%。经过AGV防冲突碰撞调整后两种调度方法计算得到的总时间相同。

Table 1. Comparison of calculation results

表1. 计算结果对比

智能车间多台AGV运行受冲突碰撞等约束的限制，执行工件运送任务最终完成时间要考虑经过约束检测调整路径后的运送任务完成时间，本算例两种调度方法经过AGV任务调度分配及路径分步优化得到的结果相同，能有效解决车间多台AGV任务调度及路径规划问题，具有很好的实用性。

4. 结语

本文在现有AGV路径规划基础上，针对智能车间AGV运送任务调度及路径规划问题，在保证AGV协同工作基础上分别按照以最小化最大运送任务完成时间为优化目标建立的相应的数学模型和工件加工紧急程度两种方式，确定每台AGV的工件运送任务序列，根据算法进行任务分配，动态调整AGV工作路径。考虑多台AGV运行时防止冲突和避免碰撞，提出冲突检测和碰撞算法。最后通过算例验证了多台AGV任务分配和基于运送任务序列避免冲突碰撞的路径规划的可行性和有效性，大幅度提高工作效率。

基金项目

辽宁省教育厅2021年度科学研究经费项目(No. LJKZ0532)。

NOTES

^*通讯作者。