仓库搬运机器人调度优化及仿真

亚马逊无人仓和KIVA搬运自动机器人的出现掀起了仓库AGV调度研究及应用的热潮。先进的搬运机器人智能调度算法是无人仓系统高效落地应用的关键，市场需求极大。本文作者基于多年的专业研究提供了仓库搬运机器人调度优化与仿真的相关建议以供行业参考。

一、仓库搬运机器人与无人仓系统

在现代自动化仓库中，各种类型和功能的机器人已逐渐开始普及应用，例如自动导引运输车（Automated Guided Vehicle，简称AGV）、码垛机器人、拣选机器人、包装机器人等。AGV是指配备电磁、光学或计算机视觉等自动导航装置，能够按一定的路线或者规则行驶，且具有安全保护以及各种移载功能的运输车，属于轮式移动机器人（Wheeled Mobile Robot，简称WMR）的范畴，AGV可通过充电获得其动力来源，通常可通过电脑来控制其行驶路线及其他行为。

亚马逊成功研发和应用KIVA机器人系统掀起了仓库AGV调度研究及应用的热潮。而国内多家电商企业和科技公司在无人仓和AGV调度方面也取得了令人瞩目的成果，京东物流全国规模最大的自动机器人仓群已投入使用，不同层级的无人仓数量已超过50个；菜鸟已经上线了第三代无人仓，实现了从商品存储到直接发货的全流程自动化，还有昆船智能、极智嘉、快仓科技、新松机器人、海柔创新等。

亚马逊无人仓

虽然如上文所说，国内多家企业自称已成功研发并应用了先进的无人仓系统，并且大大提升了存拣货效率，但企业外部的人员，包括关注无人仓技术发展的笔者，却无法从相关报道或者学术文献中获得真实的测试数据和结果，从而无法验证其无人仓系统的高效性，无法对比其与传统仓库的效率。这让人不禁怀疑，机器人在实际运作时究竟能否像宣传视频中一样流畅地作业呢？而且根据某些业内人士透露的信息，目前传统仓库仍占绝大多数，无人仓实际上并没有被广泛地应用起来。

为什么如此先进的无人仓没有被广泛地应用？主要有两个原因，一是无人仓硬件成本过高，机器人本身的造价非常高；二是搬运机器人调度算法不成熟，当无人仓中搬运机器人的密度增加到一定程度，高效地调度搬运机器人的难度也随之增加，对算法的要求就更高。因此，要想使无人仓真正地普及开来，除了不断降低硬件成本之外，研发先进的搬运机器人智能调度算法极为关键，这也是笔者多年的研究领域之一。

仓库示意图

二、仓库智能规划和仿真系统需求加大

仓库搬运机器人的调度主要包含两个部分，即将存拣货任务分配给机器人和为机器人规划行驶路径。调度搬运机器人的一个必要条件是需要有强大的仓库管理系统（Warehouse Management System，简称WMS）支撑，通过WMS我们可以实时地（通常是秒级或更快）获取仓库的状态，主要包括：

（1）每个库位的状态，即是否有货物存储，存储的货物类型及数量等；

（2）存取货任务信息，即哪些存取货任务正在等待，哪些正在被执行等；

（3）搬运机器人的状态，即搬运机器人的剩余电量，所处的位置，正在执行哪个任务，当前规划的行驶路径，任务列表中有哪些任务等；

（4）充电桩被占用的情况等。

市面上某些WMS系统可能会提供一些机器人调度算法，但是这些算法通常基于一些经验的规则来调度机器人，较为初级。此外，机器人厂商也会提供路径规划算法，但是其算法通常是为单个机器人规划最短的存取货路径，而不会全局考虑各个机器人的状态，当多个机器人共同作业时，便往往会在仓库内形成拥堵。

当今企业运营的仓库面积通常很大，可达几万平方米，存储位高达几万个，甚至是立体的存储位，日均入库和出库量高达几十万次，装卸月台达几十个，搬运机器人的数量可超过百台，而仓库的运营是一个动态的过程，即入库和出库操作随着时间的推移连续不断地进行，因此库内搬运机器人调度的实时性要求非常高。不难想象，仓库虽然大，但是其中不可能专门腾出空间只为了方便机器人通行，那么在机器人任务量越来越大之后，规划的效果会越来越差，如果不优化，甚至会出现死锁的情况。对此，WMS系统优化的方法有两种：

一是可以把任务分配和规划路径结合起来，考虑到机器人的当前位置和任务的紧急性、需要花费的时间等等来决定任务分配给哪一个机器人，这样把全局因素都加入算法中进行计算，规划的效果会有很大地提升，但这个方法暂未有比较好的成果。

二是提升调度算法的性能，提升调度算法的性能可以在不增加硬件投入的情况下提升仓库的运营效率，从而创造收益。这个方法的研究比较深入，算法效果也比较好，所以目前企业的WMS系统主流优化方向都是提升调度算法的性能。

从笔者了解的情况来看，目前很多企业已经建成智能仓库，并且部署有完善的WMS系统，但是仍然没有把高效率全局调度多个机器人的智能算法应用于仓库，上文说到调度算法的优化研究比较深入，算法效果也已经比较好，但是为什么没有应用到实际呢？这是因为仿真系统的缺失，当一个算法应用到实际的时候，需要具体适配和验证算法的性能，而由于实体机器人的成本太高经不起试错，所以仿真系统是必不可少的。也就是说，机器人调度算法的研究者首先要构建相应的仓库仿真系统，使用相关企业的历史数据来进行仿真模拟，并且比较使用优化算法前后的仓库效率，测算出优化算法对仓库运营效率的提升程度，最终帮助企业测算出使用优化算法带来的效益，从而使企业更放心地在其WMS系统中集成智能优化算法来指导实际操作。此外，仓库仿真系统有助于算法研究人员研发和测试不同类型的算法，也便于算法研究人员调试算法。可以看到，如果有一个好的仓库仿真系统，无论是研究还是实际应用，都会便利许多。

三、仓库搬运机器人优化调度与仿真前沿

1. 机器人路径规划算法

仓库内机器人的调度也称为多Agent路径规划（Multi-Agent Path Finding, 简称为MAPF），即给定一个图，一些数量的智能体，每一个都有多个任务，每个任务有指定的起点和终点，目标是为每个智能体规划能完成任务而不会碰撞的路径，从而最小化总成本。从问题属性来看，MAPF属于较为复杂的组合优化问题，该问题的状态空间随着问题中智能体的增加而呈指数增长，已被证明为NP-Hard问题。MAPF在物流、军事、安防、无人驾驶、车联网、无人港口等众多领域有着大量的应用场景。

总的来说，MAPF的研究可以分为理论与实践两大方面。先谈理论方面，首先需要先假设时间和地图都是离散化的，这是算法成立的前提条件，其次定义智能体在每一个行动点有两种动作，一种是移动到相邻的位置，一种是在当前位置等待，而且完成动作的耗时是固定的，同时给出智能体碰撞的两种类型：一种叫点冲突，即在任意时刻内，有两个智能体在同一时间达到同一位置；另一种叫边冲突，即两个智能体在同一时间交换彼此的位置。

规划机器人路径时，我们容易想到一些求最短路的算法，如Floyd算法、Dijkstra算法等等，这些算法都是求最优解的，但是规划时并不需要最优，只需要快速求出一个优质的、满足要求的路径规划结果来满足系统的动态性。所以在规划中一般采用A*算法，A*算法是广度优先搜索和Dijkstra算法的结合，是一种启发式算法，它节省了时间的同时牺牲了一点解的质量，即解并不一定为最优解。

A*算法流程如下：（1）定义起点和终点，从起点（初始状态）开始的距离函数g(x)，到终点（最终状态）的距离函数h(x)，以及每个点的估价函数f(x) = g(x) + h(x)。（2）每次取出一个估价函数f(x)最小的节点x，然后通过x这个节点计算与x相邻的节点的状态。（3）若x的相邻节点中有终点则结束算法，否则重复第二步。需要注意的是，这里的h(x)是我们定义的一个估计函数，在一些条件下是可以灵活定义h(x)来适应要求的，根据不同的h(x)的定义将得到不同的解。如果单纯用A*算法来规划单个机器人路径，规划结果无疑是片面的，因此需要整体考虑多个机器人的路径规划，这样才能让规划结果更优。 

基于这样的需求，人们就发明了Conflict-Based Search（CBS）算法，CBS算法是当前比较主流且有较好效果的MAPF理论算法。它本质上是一个两层A*算法，上层的节点存储智能体和地图的信息，遇到冲突后会在节点的地图添加限制（添加限制的方法如图3所示），下层则是再度用A*对两个冲突的智能体在有限制的地图上进行路径规划，消除冲突后再重新加入上层队列中。

在实践方面，我们必须考虑MAPF的实际延伸问题，即K-Robust MAPF，因为很多情况下智能体是不会严格执行每一个动作的，也就是说会产生延迟。解决延迟带来的问题的方法是要求k时间段内不让某个智能体进入某块矩形区域，也就是在某个矩形区域的边界上设定更加“厚”的限制，逼迫智能体等待或者绕路。在实践中还有一个关键的问题，如果一个智能体完成任务后，会获得下一个任务，此时如何对智能体进行路径规划呢？某文献提出了一个解决该问题的思路，即Rolling-Horizon Collision Resolution （RHCR）算法。RHCR算法每隔h个时间点处理一个窗口MAPF问题，也就是每次规划给定智能体全部路径，但是只处理w步内的冲突，且w要大于h，否则就会出现碰撞情况，任务分配中心会向智能体分配多个任务。RHCR算法有4个优点，即：（1）它适用于任何地图；（2）不需要时时刻刻重新规划，而是可以由用户决定规划的时间间隔h；（3）算法速度提升明显；（4）解的质量能够得到保证。

上述CBS、RHCR等算法都是侧重于解决离散时间离散地图下的路径规划，考虑如何在连续时间连续地图里进行路径规划也是研究的一个热门方向，但该方向暂未取得较好的成果。

2. 机器人调度仿真系统

现有仿真系统的架构一般和真实的情况类似，它连接着企业的服务器，其智能体运动的效果可以看作是真实的效果。仿真系统包含三个模块（见图4），即服务器端、客户端与可视化界面，其中可视化界面与服务器端是独立的。

路径优化算法在服务器端通过编写代码来实现，具体的通讯流程为：（1）客户端向服务端发送第一次请求，创建问题实例，即告知服务器端地图信息，机器人状态（任务、位置、已下发的路径），服务器端会返回初规划结果；（2）在运行过程中，客户端每隔一段时间会发送请求告知机器人当前状态（任务、位置等）并发布新的任务，服务器端会根据当前状态返回规划结果。

仿真系统的实现有多种方式。一种方式是采用国外商业仿真软件Flexsim或者Anylogic，其优点是这些商业软件功能强大，可以为非常多的场景建立仿真模型，并且开发速度快；但是其开放的接口可能有限，不一定能完全满足机器人调度算法的需求，一旦出现不满足需求的情况就会使仿真程序的开发出现卡壳的现象，因为这些软件厂商通常不会根据客户的实际需求定制化接口。另一种方式是基于某些编程语言（例如Java或者C#）从零开始编写特定仓库场景下的仿真程序，其优点是可灵活根据需求设计，自主可控，不会被“卡脖子”；缺点是成本较高，开发周期长。鉴于当前国际形势，我国更应该采取第二种方式。