摘要

摘 要：科技的进步促使拥有众多优势的 AGV（Automated Guided Vehicle，自动引导车）逐步替代人工搬运，但随之产生的多AGV 路径规划、协调问题也应运而生。针对上述问题，依据 AGV 行驶特征，构建笛卡尔坐标系环境，以传统 A*算法为基础模型，通过引入 3 轴-2象限、路线转向数剔除无效备选点、平滑行驶路径；以系统总工作时长最小为目标制定冲突判断标准与协调策略，实现系统运行效率的最佳。通过实例分析，改进A*算法单AGV线路最多可减少10.9%搜索点数、350%转向数；以时间最小为目标的协调策略能够有效避免因主观因素制定的优先度而导致系统陷入局部最优现象。

1 引言

随着科技的发展，机器人逐渐替代人工搬运，AGV因其具有任务执行、精确定位、环保高效、智能运作等特点为广泛使用，尤其在货物运输领域[1]，被公认为是实现物流运输的最佳之选[2]。AGV系统可通过控制平台实现对各AGV运行状况、地理定位、任务派遣的监控与更改，具有投资小、占地少、搭建周期短、安全、便捷等特点[3]，若将其合理地运用于车间物流运输，通过科学地改进线路算法与系统协调策略，能够有效地减少人力需求，极大提高生产工作效率，降低生产损耗与成本。
秦珅等[4]利用双向同步A*算法实现路径起终点同步搜索，以提高路径规划效率。李强等[5]通过引入象限概念，通过筛选、剔除无效拓展备选点，实现搜索效率的提高，但是由于约束条件限制只搜索与目标点同象限位置的拓展点，导致该方法的普适性大幅降低。王子意[6]通过区分 AGV 直行、转弯速度将路径转弯列入 A*算法估计函数，利用实例证明在一定环境下单AGV线路可减少超 60%转向次数。

上述方法大多针对单AGV情况，由于运输路网为多台AGV共用，运行期间将存在线路间的时空冲突，需制定一定的协调策略避免车辆间碰撞、死锁等冲突现象的发生。常见算法有A*算法[7]、遗传算法[8]、Dijkstra算法[6]、人工势场法[9][10][11]等。Draganjac等[12]通过对低优先级的车辆采用等待或者移除的策略解决路径冲突。Banaszak 等[13]提出资源共享和流量排序的协调策略，以解决动态环境中的冲突、死锁等现象。袁洋等[14]通过引入负载量优化 A*算法，实现路网的负载均衡，有效降低AGV发生冲突的概率，提高系统工作效率。贺丽娜等[15]通过将时间窗原理引入 Dijkstra 算法实现多 AGV无碰撞路线规划，结合实例证明了进入时间窗的有效性。许伦辉等[16]以下达任务的时间先后顺序降序设置优先级，并以优先级从低至高依次对冲突路径进行协调，此方案能够有效消除路网中所有冲突，但仅以下达任务时间作为线路协调顺序标准易导致系统完成所有任务的所需总时长大幅增加。

基于此，本文依据路网及车辆行驶特性，构建笛卡尔坐标系环境；通过提出一种以3轴-2象限为筛选约束的改进A*算法，在保证普适性的前提下通过约束条件剔除无效搜索点，达到提高搜索效率的目的，并引入转向数指标优化路径平滑度；以改进算法为基础，结合所建环境，对车辆冲突类型、判别进行量化分类，借鉴时间窗原理，以系统总工作时长最短为原则制定相应的协调策略，寻求系统运行效率最佳。

2 构建坐标系地图模型

栅格法由 WEHowden 提出[17]，利用单位栅格对地图进行划分，结合灰度值区分自由、障碍栅格，栅格的大小对精度具有决定性作用，缩小栅格能够提高精度，但会导致地图的信息量呈几何式增长[18]，从而降低路径规划效率。基于栅格法思想，结合AGV运行线路的正交性、定位精准性，构建改进笛卡尔坐标系地图模型作为规划环境，即以笛卡尔坐标系第一象限作为电子地图，利用二维坐标完成 AGV 运行的精确定位，此地图模型还能满足线路的正交性、路径长度便捷计算等要求。

3 改进 A*算法

3.1 提高搜索效率

传统A*算法是以当前所在点为中心，对其各方向上限定范围内的点作为拓展备选点进行遍历，本质与八码数问题相同。目前AGV运行路径多为正交线路，基于坐标系地图，若以八码数遍历原则进行路径规划，则会导致对角线上的 4 个无效点（图 1）仍然会进行先运算、再剔除的无效运算过程，从而降低规划效率。

图 1 传统 A*算法拓展备选点示意图

李强等[5]通过引入象限概念筛选拓展备选点，但由于只选取与目标同象限的周边点，导致其适用范围有所限制。鉴于此，本文提出正负象限概念，构建 3 轴-2 象限搜索法实现拓展备选点的筛选，即以当前点为次坐标轴原点建立