基于禁忌搜索的多AGV系统路径优化算法

陈 展，公建宁，刘媛媛，徐京邦

机械科学研究总院 机科发展科技股份有限公司，北京100044

自动导引车（Automated Guided Vehicles，AGV）定义为配置导航定位功能的自动导引装置，能够沿系统规划的路径行驶，具有安全保护且能完成各种装卸作业的自动设备[1]。在现代化输送系统的自动化和智能化中起着不可或缺的重要作用，日益广泛应用在制造业、航空航天、物流服务等行业。

多AGV 系统的路径规划技术包括作业任务的分派、最短路径搜索和交通管理的相互配合，不仅需要保证作业的安全性，同时还要保持系统的高效运转。其中AGV 的路径搜索需要在复杂的现场环境下，依据工艺地图路线，按照作业时间最短、系统运行成本最低和全局作业流畅的评价标准，规划一条从起始点到目标点的行驶路径[2]。

多AGV 系统的路径搜索是一个涉及约束条件、附加条件和现实条件的复杂非确定性多项式（Nondeterministic Polynomial，NP）问题。相比于传统经典算法，智能优化算法能够更有效地解决路径规划的多约束问题，通过将寻找最优路径转化为寻找函数最优值，从而实现多AGV 系统路径规划中的最短路径搜索[3]。本文在保证合理任务分配机制和稳定交通管理策略的前提下，对比经典寻路算法，提出基于邻域搜索的禁忌路径搜索算法，通过仿真实验证明该方法的优越性和必要性。

1 介绍

随着AGV系统应用的日益广泛和作业任务的日益复杂，AGV集群之间的相互配合与协作，成为系统项目中不可避免的重要问题，而多AGV 的路径规划技术就是AGV 系统的核心技术之一，可分为环境信息完全已知的全局路径规划和环境信息完全未知或部分未知的局部路径规划[4]。

在多AGV 系统的环境信息已知的全局路径规划中，任务调度算法、路径搜索方法和交通管理的性能直接决定系统的整体效率。本文通过对路径规划技术中的路径搜索算法在同等耦合条件任务分配和交通管理策略下进行设计优化，完成基于特定的环境模型，搜索出一条能耗低、用时少，尽量避免阻塞障碍的AGV作业路径。

全局路径规划下的路径搜索算法发展历程如图1所示，从传统的Dijkstra 和启发式的A*等经典算法，经过基于采样和图论的随机路标图法（Probabilistic Road-Μaps，PRΜ）、快速搜索树法（Rapid-exploration Random Tree，RRT）等，发展到日益成熟的智能仿生优化算法和强化学习[5]。但实际应用过程中的任何路径搜索算法都存在局限性，在具体的应用方向上，进行针对性的优化改善，或是融合优化多种算法，可以快速有效提升算法性能[6]。

图1 路径搜索算法发展历程

在多AGV 系统下的路径规划中，当中央控制系统派发任务时，首先按照就近原则进行约束排序，来选择匹配一辆移动机器人进行任务分配。这样的规划方法在一定程度上利用多移动机器人系统的优势，节约了AGV 电量和车体磨损等物流成本资源[7]。采用基于路径资源分配机制以排除交通管理的调度策略对路径规划性能的影响，依此设计基于禁忌算法求解多AGV 系统的全局路径搜索。

本文的主要内容包括：

（1）构建地图模型拓扑结构生成XΜL 文件存储包含信息。

（2）设计禁忌搜索算法原理步骤，基于目标函数求解最优路径。

（3）进行不同规模算例下的分组实验，验证禁忌搜索算法对路径能耗属性、时间属性和路径负载均衡目标参数的优化效果。

2 方法

为系统构建环境模型是AGV路径规划过程的重要组成部分，是将实际工厂作业环境的物理空间抽象模拟为算法可处理的数据环境，具体实现物理空间和数据环境的相互映射。

环境信息已知的多AGV 路径规划，路径规划流程为上位机依据任务分配准则匹配相对应的AGV，分配准则为固定的均衡任务分配顺序，顺序依据为先到先得，订单就近原则匹配起始点最近的AGV，上位机调度系统进行最短路径搜索并逐段下发可行驶的路径资源。之后AGV 再向调度系统申请下一路径资源，调度系统对竞争路径资源的AGV的集合进行优先级排序和判断阻塞区域类型，进行交通管理。通行方向相同的AGV或者是只允许单辆AGV通行该区域，将线段或是阻塞区域等路径资源分配给优先级最高的AGV，其他AGV 排队等候。AGV 每驶离占用的路径资源，便上行报告上位机，上位机调度系统释放该资源。进入循环流程，直到所有分配订单的AGV完成作业，自动泊车。

2.1 模型构建

AGV任务的规划决策建立在已知环境信息的基础上，地图的构建就是对环境信息的描述过程，地图建模方法直接决定着环境信息表达的精确性和复杂度，影响着路径搜索的效果与效率。常用的方法有几何建模法、栅格建模法和拓扑建模法。几何建模法就是将环境信息抽象为多点折线或圆弧等几何特征对地图进行描述，从而简化地图的表示，适用于小尺度或静态环境下的应用；栅格建模法是将环境空间均匀地划分为若干大小相等且固定不变的栅格，每个栅格具有唯一的位置信息，但信息分辨率较低，数据结构复杂；拓扑建模法是将关键站位的状态和位置信息抽象为节点形式，相邻节点用有向线段连接，表征连通状态，从而形成点线相连的关系网[8]。不同建模方式均存在各自的优势与不足，如表1所示，需根据具体应用场景选择适应系统方案的建模方法。

表1 常用建模方法

针对仓储环境站位密集布置的应用场景，拓扑建模法优势明显，具有计算效率高、内存空间小和构造过程简洁的特点，尤其适用于关键站点的多联通状态，地图表达更加紧凑。同时考虑系统实现订单规划决策、AGV位姿监控、可视化地图管理等功能，采用拓扑地图法进行系统模型的构建，将作业环境下的AGV 导航定位构建的复杂电子地图和现场物理空间抽象建立拓扑结构，拓扑结构节点组成如表2 所示。拓扑地图在搜索计算最短路径时的复杂度取决于环境中可通行的节点的数量，系列节点和连接节点依次表示功能站点和行驶路径节点，连线节点线段的权值表示具体的路径代价。

表2 拓扑结构节点

结合实际的生产车间环境，将作业环境下的AGV导航定位构建的复杂电子地图和现场物理空间抽象建立拓扑结构模型，绘制行驶节点和各个功能站点组成的强连通性的有向带权图。在构建系统拓扑结构时，考虑AGV 转弯角度限制，利用二次贝塞尔曲线函数对设计的曲线路径做平滑处理，使得AGV 在规划的可行路径上平稳自然运动。模型地图信息存储为xml文件，包含路径搜索需要的节点、站点、路径线段信息、阻塞信息，如图2所示。

图2 地图存储信息

拓扑模型有向带权图表示为F(xl)＜F(xbestl)，如图3所示，其中P={1,2,…,n,n+1} 表示节点和站点集合，Point集合表示中继、交叉的行驶路径节点，节点坐标为(x,y)；Location 集合表示工作站，站台属性为(x,y,m)，(x,y)表示该点在地图中的空间位置坐标，m 表示在该点AGV 所要完成取卸货和充电的功能动作；将路径描述为有向带权线段E，箭头表示有向路径的方向，路径权值采用cost(Length,Maxvelocity)的形式，表示AGV行驶路径线段的时间成本，其中Length 表示路径节点间的实际距离，Maxvelocity 表示路径设置的速度阈值。

多AGV系统的路径优化问题的基础约束保证系统状态正常及功能完备。容量约束为每一个作业订单只对应一辆AGV。工作时长约束为AGV 从起始点出发到完成作业订单的时长不能超过设置阈值[9]。

2.2 禁忌搜索算法

2.2.1 算法介绍

传统的经典算法Dijkstra 算法于1959 年由荷兰科学家Dijkstra提出，该算法是单源路径算法，用来求解一个顶点到其余各顶点的最短路径问题，它以起始点为中心向外层层扩展，直至扩展到终点为止，计算得到最短路径。Dijkstra 算法能够简洁有效地找到最优解，但不足之处在于O(n2)的计算复杂度，当数据节点庞大时所需的节点繁多，效率随着数据节点的增加而下降，耗费大量内存空间与计算时间，并不能很好地满足多AGV动态路径规划的系统需求[10]。

传统的启发式的A*算法搜索速度快且效率高，能在一定程度上克服搜索过程中的早熟现象，在机器人路径规划中得到了广泛应用。但A*算法同样存在限制，在路径搜索过程中，随着地图面积的增大其搜索空间会产生多余的搜索节点，导致算法效率降低，耗费大量内存空间与计算时间。相对而言，智能优化算法可以更为有效地解决路径规划的多约束问题，通过将搜索路径转化为寻找函数最优值，从而实现多AGV 系统路径规划中的最短路径搜索[11]。

图3 地图模型

1986年，禁忌搜索（Tabu Search，TS）算法由Glover教授正式提出。其通过引入一个灵活的存储结构和与之对应的禁忌准则，并通过藐视准则赦免一些被禁忌的优良状态，借此保证多样化的有效搜索来实现最终的全局优化[12]。其最主要的特点就是采用了禁忌技术和特赦规则，使得算法可以跳出局部最优解，进行有效的计算，最终实现全局的优化。禁忌搜索算法的搜索结果依赖于初始解和邻域的映射关系，计算灵活，收敛速度快，能够有效提高搜索速度和解的质量。尤其是在问题规模较为庞大、传统搜索方法不能在较短时间内求得问题的最优解，禁忌搜索算法的优势更加明显，是适应求解多AGV系统路径搜索的理想算法。

逐步寻优的路径搜索算法一般采用贪婪思想对当前解的邻域进行搜索，这样的搜索方式使得邻域的结构和初始解的选取决定了其搜索速度性能和解质量的优劣，且无法保证求解算法的全局最优。在禁忌搜索算法中，将已经实现过的局部最短方案保存至禁忌表，在后续检索相似路径时避过禁忌列表中的点，避免局部最短路径作为最优解出现，当局部最短路径成为全局最短路径时，再特赦为算法最优解[13]。

2.2.2 算法结构设计

（1）构造初始解

从起始顶点SID出发，依据地图联通信息，将各节点加入到路径列表中，直到搜索终点DID加入，即得到SID到DID的初始解路径。逐步寻优的路径搜索算法一般采用贪婪思想对当前解的邻域进行搜索，这样的搜索方式使得邻域的结构和初始解的选取决定了其搜索速度性能和解质量的优劣，且无法保证求解算法的全局最优。在禁忌搜索算法中，将已经实现过的局部最短方案保存至禁忌表，在后续检索相似路径时避过禁忌列表中的点，避免局部最短路径作为最优解出现，当局部最短路径成为全局最短路径时，再特赦为算法最优解。

（2）邻域解迭代

基于当前解在邻域中迭代搜索，邻域满足拓扑结构联通属性，计算路径搜索当前解的边属性总权重，边属性权重为AGV 理想行驶时间，用拓扑地图节点间边长和最大速度阈值作商取值。随着邻域解的迭代，基于目标函数评判所迭代邻域解对求解路径时间属性、能耗属性和系统运行稳定程度的积极性。

（3）目标函数

定义节点集合P（point）和线段集合S（segment）的路径边属性总权重值的时间评价函数d(m)为：

目标函数表达式定义为：

目标函数对于迭代邻域解的评判基于求解路径的时间属性、能耗属性和系统运行稳定程度。能耗属性参考依据为AGV 作业所行驶的物理距离，求解出的行驶物理距离越大，AGV 车体和使用电量等能耗越高。计算求解的AGV 理想行驶时间越长，路径边属性总权重值的评价函数d(x)越大，则对应目标函数值越大，积极性越小。路径网络负载分布集中程度的系数项中，随着普通节点数量的减少和交叉节点的增多，反映系统对交叉节点资源的竞争使用程度，负载集中系数项越大，则AGV 作业路径阻塞障碍更为普遍。综上，系统的高效稳定性能取决于目标函数的各个组成，且最优路径将具有最小的目标函数值。

（4）禁忌、终止和特赦规则

禁忌对象：基于连通性的搜索路径作为禁忌对象，禁忌表中收纳该局部最优解。

禁忌规则：在候选解中选出适应值最好的候选解，将其与当前最优解进行比较，目标函数如果优于当前最优解，则更新替换，并且作为下一个迭代的当前最优解，然后将对应的操作加入禁忌表；如果目标函数不优于当前最优解，就从所有候选解中选出不在禁忌状态下的最好解作为新的当前最优解，并将对应操作加入禁忌表。

禁忌长度：设置禁忌长度，限制被禁忌的对象需要进行对比的步数，其值可以根据问题的规模大小，取常数。

候选集合的确定：将从当前解的邻域中选择交换算子生成新搜索路径作为候选集合。

终止准则：最大迭代步数作为算法的终止准则。

特赦规则：在算法迭代产生当前最优解的同时，记录判断该解的评价函数值，当该解优于当前问题的最优解时，将其从禁忌表中特赦。

2.2.3 算法步骤流程

算法流程图如图4所示。

图4 算法流程图

算法步骤如下：

（1）初始化模块参数，禁忌列表List_T 置空，就近优先逐节点加入路径，生成最短路径初始解xl；

（2）在xl的邻域L(List_T,xl)中选出满足禁忌要求的候选集Cand_L(xl)；

2.3 算法实现

本文用Java语言实现禁忌搜索算法，代码结构分为main（）、ReadIn_and_Initialization（）、Construction（）、Calculation（）、Tabu_Search（）、Check（）和Output（）函数模块。其中main（）函数构建算法的主体框架；ReadIn_and_Initialization（）的功能是读取存储xml 地图文件并初始化所有变量；Construction（）、Calculation（）、Tabu_Search（）分别实现禁忌搜索算法中的初始解构建、对应解的适应值计算和对定义邻域进行搜索并对应标准选择禁忌；Check（）函数的功能是用来检验解是否满足对应的所有约束；Output（）函数输出结果。

3 实验

本文将通过仿真实验对这几种常用路径规划算法进行比较，并且结合机器人实际运行情况对几种算法进行分析。

运输订单的生命周期如图5所示。

图5 订单生命周期

创建运输订单后，其初始状态为RAW；设置运输订单参数，激活状态为ACTIVE；可匹配AGV 状态转换为DISPATCHABLE；UNROUTABLE 则不进行任何处理；AGV执行移动指令任务订单状态为BEING_PROCESSED。AGV 的处理运输订单失败，则将其标记为FAILED。如果AGV 成功处理了整个运输订单，则将其标记为FINISHED。AGV 总能耗用AGV 该批序列订单完成过程中的总充电次数衡量定义。任务完成时间取决于最后一个任务的结束时间，用来衡量同批序列任务从生成到全部完成的总大时间开销，任务完成时间越小则系统效率越高。

改变总节点个数、路径边数建立不同规模地图模型，做分组实验验证禁忌搜索算法性能。实验仿真触发200个任务订单，跟踪监测系统总能耗、任务完成时间、死锁情况出现概率和任务完成比率，来对标路径优化算法在能耗属性、时间属性和系统运行负载均衡属性上的优越性，测试用例执行状态跟踪表如表3～表5所示。

表3 40节点地图模型中路径搜索算法对比

表4 100节点地图模型中路径搜索算法对比

禁忌搜索算法的核心是在循环中构建一个禁忌循环列表，采用动态更新的方法来实现短期循环记忆，以避免搜索出现相同的解。经实验验证，在一般情况下，禁忌搜索算法在处理时间、系统能耗和任务完成比率上相差不大，但在项目规模较大的情况下，禁忌搜索算法相比于传统经典算法Dijkstra的计算时长优越性显著体现，相对于启发式A*算法的系统运行流畅度显著提升。随着系统规模的增大，求解路径能耗更低，用时更少，可以有效地均衡全局路径的资源使用，充分体现基于禁忌搜索的多AGV路径优化算法的必要性和优越性。

表5 1 000节点地图模型中路径搜索算法对比

4 结束语

随着5G时代和工业4.0的到来，企业智能制造的不断改造升级，AGV移动机器人扮演着相当重要的角色，而对AGV路径规划技术的依赖要求也日益增高[14]。多AGV系统的路径规划，要求其按照一定的参数指标，在任务区域求解出满足要求的优化可行路径。禁忌搜索算法在一定程度上而言，算法方案较为复杂，解的要素偏多，运算工作量较大，且智能优化算法的收敛速度和收敛效果存在一定限制。

多AGV系统的路径规划问题属于NP问题，约束条件复杂，问题规模和求解难度大，本研究有重要的学术意义，有助于Agent路径问题及相关优化问题的发展[15]。在未来的研究方向中，基于本文集中式AGV 控制系统模式的全局路径规划，结合分布式AGV 控制系统的局部路径规划，可以完善AGV的避障功能，提高系统的稳定性和抗干扰性。