多机器人存取系统研究现状

　　文 北京科技大学机械工程学院 孙阳君、赵宁
　　来源文 物流技术与应用
　　在电子商务繁荣发展的今天，利用多机器人存取系统可以节约人力成本、提高拣选效率、提高存储密度、降低碳排放，因此许多电商企业选择布局多机器人存取系统，通过＂机器换人＂，实现＂货到人＂拣选。随着多机器人存取系统在企业内的应用发展，多机器人存取系统也成为近年来的热点研究问题。本文重点介绍了多机器人存取系统中的热点研究方向，总结了现有的解决方案，最后对未来研究进行了展望。
　　最早的移动机器人在1953年被美国basrrte公司开发成功，它能够沿着布置在空中的导线完成任务，但不能自主随意移动。自20世纪初，自寻址技术的出现对传统的移动机器人实现了技术革命。自寻址技术可以不预先铺设轨道，以非接触的方式实现车辆的智能寻址和定位，大幅增加了移动机器人的智能程度和应用范围。随着自寻址技术的发展，移动机器人可广泛用于车间、码头、仓库等系统中，系统内的机器人数量也从几台扩展到上百台。
　　2008 年，Kiva systems公司首次将上百辆互相协作的移动机器人同时用于亚马逊的仓储作业中[1]，即最早的多机器人存取系统。2012年，亚马逊收购Kiva公司将多机器人存取系统部署在北美的各大配送中心内。国内也紧随其后，菜鸟、京东、极智嘉和快仓等公司已经成功应用多机器人存取系统完成相关业务。
　　近年来，多机器人存取系统的销量也在不断增长。《2019年世界机器人报告》[2]显示，仅2018年就卖出了超过十万的多机器人系统，其中大多数都被用于电子商务仓库中，为电商公司提供存取服务。2020年，COVID-19疫情进一步推动了多机器人存取系统的市场，《2020年世界机器人报告》[3]显示，电商仓库内的移动机器人交易额增长了110％，达到19亿美元。按预测，未来的交易额增长可能达到每年40％甚至更高。
　　种种迹象都表明，多机器人存取系统已经成为应用热点，对多机器人存取系统的研究也日益增多。本文首先介绍了多机器人存取系统，描述了多个热点研究方向和解决方案，最后对现有研究进行了总结和展望。
　　一、系统简介
　　多机器人存取系统利用货架存储商品，通过移动机器人搬运货架，工作人员只需要在工作站等待，不用进入存储区域，工作完毕后移动机器人再将货架搬运回存储区域。这样一来，就大大减少了工作人员的劳动强度，减少人员行走距离。如图1所示，移动机器人依靠扫描地面的二维码定位，根据指令向任意方向行驶。按照任务要求，执行搬运、升降货架、等待等操作。
　　图1 多机器人存取系统
　　图2 多机器人存取系统工作流程
　　在电子商务的订单拣选中，系统的目的就是尽可能提升拣货效率，更快更好地完成客户的订单。如图2所示，系统的工作流程可以概况为：根据客户下达的订单，指派工作站完成订单，按照订单上的商品确定机器人需要执行的任务，通过机器人搬运货架至工作站完成拣选，再搬运货架回储区。在系统运行中，如果订单需求的货物量超过了安全库存，还需要进行补货操作。如果机器人的电量不足，需要充电，确定充电策略。除了工作流程中的策略和优化方法外，还需要确定货架和商品存放在哪些位置，并进行储位优化。此外，系统的布局模式、机器人的数量、拣货站的数量、货架的位置等都会对系统效率造成影响。因此，还需要对系统整体布局中的工作站位置、货架位置、充电站位置等进行优化。
　　二、研究方向
　　按照图2系统的工作流程，可以对系统本身和系统内的各个环节进行研究，主要包括以下研究方向：布局优化、订单指派、任务分配、路径规划、冲突消解、储位优化、充电策略、实时调度等。这些研究方向涉及到系统运行前的整体布局和系统运行中的各个流程。
　　1.布局优化问题
　　图3 多机器人存取系统俯视图
　　一个普通的多机器人存取系统的俯视图见图3。布局优化就是对系统内的机器人、货架、工作站等的位置、数量、比例等进行设计，确定最合适的布局，以提高拣货效率，增加系统吞吐量，更快完成订单。
　　对于系统的布局研究，包括以下几种情况：
　　（1）工作站所处的位置和数量。图3中工作站是在货架的一侧，但在布局中，可以两侧都摆放货架，也可以四周都有工作站[4]。不同数量的工作站会对拣选效率有影响。
　　（2）货架布局方式。a.货架长宽比，货架区域的设置影响车辆运行的路径，可以通过建立排队网模型计算不同长宽比对拣货效率的影响[5]。b.布局模式。图3展示的是传统的布局模式，还有很多新型布局模式可以考虑，特殊的布局模式可以增加拣货的效率或系统的存储密度。例如图4展示的V型布局[4]、鱼骨型布局[6]、多深布局[7]等。
　　图4 几种新型布局模式
　　（3）仓库内道路布局。道路布局有很多需要考虑的地方。如a)道路方向。图3展示的道路都有具体的方向，即单向道。通过单向道避免发生相向冲突和死锁。除单向道外，道路也可以采用双向道布局方式，机器人可以沿任意方向运行，能够减少机器人的绕路，加快运行效率。考虑到双向道内的相向冲突较为严重，也可以将两者结合布局，部分区域采用单向道，部分区域采用双向道[8]。b）车道数量，图3中，只有在工作站和存储区域的道路是双行道，存储区域都是单行道，即只能容纳一辆车通过。双行道可以更大程度上避免机器人的冲突，但浪费了存储面积。c）是否有交叉口。交叉口同样降低了存储密度，但机器人移动时可选择的路径比无交叉口时更多，能够避免机器人间的拥堵。单向单行道和双向单行道、有交叉口和无交叉口的对比可以参考Lienert等[9]的研究。
　　2.订单指派问题
　　订单是多机器人存取系统的输入，完成订单是系统运行的首要目的。单张订单每件商品按顺序拣选的完成方式会大大降低系统效率，不同订单有同一件商品时，完全可以一同拣选，即使没有一样的商品，两张订单需要拣选的商品也可能位于同一个货架上。因此，就需要对订单进行整合和指派，确立订单内商品在哪些货架上，哪些订单可以在同一个工作站内拣选[10-11]。优化订单的顺序还能减少机器人的数量，降低系统运行成本[12]。为了提高系统效率，订单内的货物甚至可以被拆分到不同的工作站完成[13]。
　　3.任务分配问题
　　任务分配是在订单指派后，将订单拆分成涉及到具体货架的任务，将任务分配给机器人进行执行。系统内同时有多个任务和多辆机器人，一辆机器人在同一时间只能搬运一个货架，任务分配情况关系到机器人未来的行动路线。在任务分配时，需要综合考虑机器人和任务要求的货架之间的距离，机器人本身的任务情况，任务间的关系等多个因素。现有的研究中，任务分配可以是采用一些策略进行分配，如基于作业速率、近似最优和最优指派策略等被用于任务分配[14]。还可以根据当前系统内任务的距离、时间、效率等状态，设计启发式规则完成任务分配[10]。此外，可以利用智能算法通过迭代优化的方式获得更好的任务分配结果，如遗传算法[15]，模拟退火算法[16]，禁忌搜索[17]等。
　　4.路径规划问题
　　图5 机器人的不同路径
　　机器人接取任务之后，就需要执行任务，按照任务要求对运行路径进行规划。机器人的运行路径规划是多机器人存取系统的核心。好的路径规划方案能够大幅度提升系统效率，减少机器人的能耗。如图5(a)所示，机器人完成任务需要三段路径，首先要从当前位置到货架所在位置，再从货架所在位置到工作站，之后带着货架返回储区。这期间，机器人由无数条路径可以完成任务，例如图5(a)是最短路径，但也可选择图5(b)的其他路径，但最终完成任务的路径受到多方面影响。由于仓库内不只一辆机器人，多辆机器人之间会造成冲突问题。最短路径可能有其他机器人频繁经过，产生严重的冲突问题。因此机器人运行的最短路径并非就是最好的，还需要综合考虑其他机器人的情况。常用的路径生成方法包括动作依赖图[18]、路线图生成算法[19]、A*算法[20]、Dijkstra＂s 算法[17]等以及对这些算法的改进。
　　5.冲突消解问题
　　图6 机器人间的冲突情况
　　多辆机器人运行时，由于运行路线有交错，必然会发生冲突。机器人间的冲突可以被归为以下几类：赶超冲突、交叉口冲突、相向冲突，如图6所示。针对这些冲突，有多种启发式规则可以采用，如设立优先级进行避让[21]，任务少的机器人等待[22]，或是采取多种方式比如离开、绕路和启动前等待以避开不同冲突[20]，利用通道协议避免一条通道内的机器人冲突[23]等。
　　6.储位优化问题
　　货架的存储位置决定了机器人将其搬运至工作站时行走的距离，货架离工作站越近，搬运耗费的时间越少，系统的效率越高。但是，如果货架都在工作站附近，机器人搬运时也聚集在工作站附近，反而会造成工作站附近的拥堵。因此，储位优化也成为研究的热点问题之一。对货架存储位置设置不同的策略，对实际运行时的影响不同[24]。现有研究中，采取的策略包括：
　　（1）固定位置存储。货架固定在某一确定位置存储；
　　（2）随机存储。货架从工作站离开时，随机选择空位存放；
　　（3）最近存储。货架从工作站离开时，选择离工作站最近的空位存放；
　　（4）分区存储[5]。按照货架上货物被拣选的频率，对储区进行分区，高频区靠近工作站，低频区远离工作站，货架按照区域存储，在区域内部也可有＂固定位＂、＂随机＂、＂最近＂等存储策略。
　　7.充电策略问题
　　机器人虽然不用像人类一样需要休息，但机器人的运行需要依靠电能，图3右下角就是机器人的充电区。机器人的充电策略涉及到以下两部分：
　　（1）充电时机，即机器人还有多少电量时需要充电[25]。如果充电时机选择的过晚，就会出现有机器人因为电量耗尽而停留在储区或工作区内的情况，会直接影响任务的完成和其他机器人的运行。过早的充电虽然可以避免机器人没电停止，但机器人频繁的充电影响系统效率，同时也影响电池寿命，而且充电区的容量也是有限的，频繁充电可能导致充电区发生堵塞。
　　（2）充电模式。机器人可以选择在充电区充电，也可以直接换电池。现有研究的实验表明，换电池比充电更能提升系统性能[26]。
　　8.实时调度问题
　　实时调度是在系统实际运行时进行调度，对调度的时效性要求较高。因此，多采用一些规则处理系统运行中遇到的各种问题，如利用分配任务极为快速的令牌传递算法[27]；通过得到的当前机器人的状态，进行动态路径规划，避免机器人间的冲突[7,28]；实时调整机器人的优先级以协调冲突[29]。还有一些和系统输入相关的问题，例如紧急订单的出现，紧急订单优于其他订单进行指派，优于其他任务被分配给机器人完成[30]。此外，在实际运行中还会出现机器人故障、货物跌落等突发事件。
　　三、总结和展望
　　多机器人存取系统具有更高的拣货效率、更好的系统可扩展性和柔性，因此成为近年来备受关注的研究领域之一。本文描述了多机器人存取系统中的布局优化、订单指派、任务分配、路径规划、冲突消解、储位优化、充电策略、实时调度等问题。除此之外，还有多个方面有待关注。
　　1.协同优化
　　现有的仓库规模不断扩大，机器人数量逐渐增多，系统运行流程复杂，问题之间联系紧密，单个机器人的最佳路线、单个问题的最优策略在系统全局运行时并非最优。因此，需要进行协同优化，找到系统运行时最合适的策略组合，确定同时考虑多辆机器人多个问题的优化方法，共同提升系统效率。
　　2.数字孪生系统
　　数字孪生是近年来的热点方向，数字孪生可以将虚拟系统和现实系统结合起来，利用虚拟系统模拟物理系统运行。多机器人存取系统内人类活动少，机器人行为可以预测，进而实现对整个系统运行情况的预测。通过对物理系统状态的预测，可以提前处理未来可能发生的问题，从而指导物理系统运行。
　　3.机器学习
　　多机器人存取系统本身是一个复杂系统，系统内的问题很多。机器学习和人工智能的发展为系统运行提供了新思路。通过对大量经验数据的学习，将复杂问题简单化，快速做出决策，将是未来研究的新方向。