浅谈AGV的路径规划

李景，程瑞嘉，张文忠

（安徽工业大学电气与信息工程学院，安徽 马鞍山 243032）

随着电子商务、快递、互联网以及新能源技术的日新月异，人们对物质生活的需求也会越来越高，电商行业的订单迈向多种类，小层次，高频次的步伐。这种消费模式给传统“人到货”的拣选方式带来巨大挑战，为了应对这种问题，现代的智能仓储系统提出了“货到人”的拣选理念。

在这种智能仓库中，大多采用定制的仓库机器人（AGV）代替人工来实现货物的拣货、分拣、搬用到派送等一些操作。根据仓库订单，利用中央处理单元对仓库机器人进行分配任务，其次对整个仓库研究分析，建立基础地图模型,分配好机器人任务，建立好地图模型并对AGV进行路径规划，主要有总体路径规划［1］以及局部的路径规划［2］，本文针对整体流程做出简介。

1 AGV地图模型的构建

构建仓库地图模型是相当重要的，也是之后对其调度路径规划的基础。在研究众多文献后，大致可以得出以下几种方法：

（1）简易模型栅格化。（2）有向图的模型地图。（3）时空地图模型。

1.1 简易模型栅格化

将整个仓库假定为区域a，以最左下角为坐标原点，横轴为X轴，纵轴为Y轴，建立XOY狄克尔坐标系，机器人为一小格，等同于一像素点。而货架等同于几个像素点不可通过，设机器人步长为u，仓库最大面积等于Xmax*Ymax，所以可得栅格数则为N C=Xmax/u,Nl=Ymax/u。故机器人的运动可以看成点在坐标系的运动模型。即如图1所示。

图1 简易栅格图

1.2 有向图的模型地图

机器人运行空间由不同类型且相同尺寸的单位块组成，这些单位块用来表示站点中的出发点、分拣格口、缓冲区、路径等。我们用端点来表示所有的单位块，并且用有向边来相互连接。注意同一时间内一个单位块只能通过一辆AGV。

首先，多辆AGV机器人可以在出货口同时装捡快件或暂时停靠。叉号标示的单位块表示分拣格口，由单行单方向的所有的路径块都被赋予了通行方向，并且AGV机器人在每个时间插槽内只能够停靠一辆。其次字母B单位块表示缓冲区块，AGV机器人在这里可以暂时停靠，避免与其他工作机器人发生冲突。

1.3 时空地图模型

利用二维元胞数组记录各节点占用时间段集合，其中节点（x,y）的占用时间段集合表示为：

式中tin、tout分别为AGV进入、离开节点（x,y）的时刻，i表示占用节点的AGV编号。其时空地图模型如下图2所示：

图2 时空地图

2 AGV调度的路径规划

在为机器人分配任务以及建立好仓库地图模型之后，接下来更重要的一步也是整个AGV调度中最为重要的一步就是关于AGV调度的路径规划问题。许多学者对这部分的研究大体分为两种：第一种是集中式系统规划［3］，这种方法对中央处理单元要求性能较高，在仓库这种级别中无法要求处理单元性能优异。第二种就是分布式系统规划［4］，这种方法对每一台智能机器人要求性能较高，既要规划路径又要接受任务分配等工作，所以工作量大。

现在更多的学者偏向于将全局路径规划以及局部路径规划结合起来使用，常用的方法有：基于双种群遗传算法的路径规划，基于时空地图的路径规划与基于时间窗的路径规划。

2.1 基于时间窗的路径规划

通过加入时间窗的方法来实现其路径规划，具体过程如下：

对于单机器人多负载路径规划。步骤1：每一个AGV都要有两条及以上的备选路径；步骤2：每条路径都会涉及到多个路径块，每个路径块都有各自的空闲时间窗，通过统计全部空闲的时间窗可以算出Sch（pk），即每条备选路径pk的通行时间安排；步骤3：选出用时最短的备选路径，及时预定此路径涉及到的所有路径块。对于步骤1，为了避免预约通行的其他AGV在相同的时间相遇，采用基于A*的带惩罚算法来生成候选路径集，即对每个时间格加入权重，最后通过寻找权重小的路径展开，寻找到最合适的路径。对于步骤2，我们给出两种时间窗搜索的算法，分别是前向时间窗搜索算法以及重选择时间窗搜索算法，在此基础上再去计算路径调度。

而对于多机器人负载时：首先在出发点获取多个快件，通过每个负载快件互异的目的点，系统会自动规划出无冲突的路径方案传递给机器人执行，之后AGV根据路径行走完所有目的地后返回出发点重新加货。

3 结论

以上讨论的方法以及模型大多数是建立在如下所示的理想模型下进行的，在现实世界中存在着很多的不确定因素，故上述很多方法都是失效的或者说效果不佳的。理想模型：（1）AGV只能沿直角方向（即横纵向）跨越栅格，AGV不能斜向跨越栅格。（2）将每个AGV的装载时间、卸载时间理想化为零。（3）所有包裹在零时刻到达，所有AGV在零时刻可用。（4）AGV运行过程中保持匀速。（5）不考虑包裹到达投递区之后的出库过程。（6）不考虑机器人空载以及负载情况下的运货速度，以及机器人充电时间。

今后机器人的目标就是向着这个方向改进，首先需要考虑机器人充放电情况，虽然在这方面有一些相关的介绍，但是过于简单，不能加以推广应用；其次就是机器人运动过程中可能存在一些均加速以及均减速的情况，这样机器人在面对碰撞冲突问题上可以不用通过停下来等待来解决节点冲突以及相向冲突问题，此时也会多了一个追击冲突。这种情况将会更加复杂，有待于进一步研究。