物流机器人大规模集群调度研究

物流机器人大规模集群调度研究果表明系统效率受机器人规模影响显著,量化分析了不同比例异构机由于劳动力成本上升，众多企业已转向自动运营，选择机器人代替工人完成物流任务，自动导据市场研究机构ABIResearch统计，全球已有超过400万台物流机器人安装在5万多个仓库。国内的物流机器人市场也步入快速销售规模约为221亿元，同比增长4.25%,销售数量为139000台，同比增长11.2%。随着市场需求扩大，物流机器人的应用场景从单机作业、小批量部署，正在逐渐变成群体作业、大规模调度。国内的设备制造企业通过优化成本，进一步降低了机器人产品价格，最当前，大规模物流机器人的应用场景已覆盖多个领域，如图1所示。在制造系统中，为减少对地面空间的占用，通过空中搬运天车(OverheadHoistTransfer,OHT)系统传递物料，天车轨道甚至长达50公里，上千台天车每日要完成近百万次搬运任务，对调度障碍物，导致机器人间冲突严重，系统容易发生局部死锁。在码头系统中，多种类的机器人需要共同完成装卸作业，对机器人间的协突出，被广泛用于各类制造、仓储系统中，但设备成本较高、传感性高，但在光照变化剧烈或特征单一的环境中，导航稳定性易受影图1不同系统中物流机器人的应用现场图随着机器人规模持续扩大，大规模集群调度面临着诸多亟间有限，但机器人数量多，导致系统内机器人密度大，高密度机器人运行时，机器人间的冲突问题日益严重，在狭窄通道、交叉路口等关键区域，多台机器人的路径规划易出现重叠，频繁引发拥堵、等待甚至碰撞风险，不仅会降低单台机器人的作业效率，更对整个物流系统的稳定性造成负面影响。现有调度系统的算力与数据处理能力难以匹配成百上千台机器人的实时状态反馈与动态调度需求，单次运输任务甚至会调用上百次路径规划算法。调度算法耗时长，调度资源不足，导致大规模集群调度效率低。二、大规模机器人调度研究1.大规模机器人场景物流机器人在各类存取、分拣和码头等系统中都有大规模应用实例。物流机器人集群场景通常以其内部机器人类型的不同，可分为同构机器人集群和异构机器人集群。其中，同构机器人集群指的是由相同类型、具有相似功能和特性的机器人组成的集群，以执行相似的任务或协同工作，如型号相同的机器人。异构机器人集群即具有不同能力的机器人，如无人叉车和托盘机器人等，能够在复杂任务上进行协作。不同品牌机器人的调度系统因技术标准、通信协议、数据接口的差异，普遍存在难以互通的问题。因此，异构机器人集群又有两种协同模式：同品牌多类型机器人协同运行和多品牌多类型机器人协同运行。现阶段，同构机器人集群常用于存取系统、分拣系统等，如亚马逊的kiva机器人系统、京东的亚洲一号无人仓等，而异构机器人集群相比之下应用较少，主要集中于立体库、仓储中心等，如快仓的QuickPick智能机器人系统。不同类型物流机器人集群调度情况对比，见表1。表1不同类型物流机器人集群调度情况同构机器人同型号机器人协同运行堵，需要减少调度资源消调度和维护同品牌多类型机伏机器人多段举升合完成多种任务区、分拣区等立，机器人间通讯效率低，2.物流机器人调度物流机器人调度主要包括任务分配、路径规划、冲突协调三个问题，如图2所示。图2物流机器调度问题、目标和组织结构任务分配是将系统外部到达的任务分配给机器人完成，保证每个任务都有机器人接取。这些任务都是由上层控制系统下发的，任务已经被拆分成具体的运输任务，并确定了任务起终点、优先级、截止时间等信息。任务分配方法包括禁忌搜索算法、模拟退火算法、遗传算法、花授粉算法等智能算法，以及接受一派遣规则、任务优先级、基于拍卖的方法、启发式的平衡机制、最低总成本等启发式路径规划是规划机器人从当前位置到目标位置的运行路径，由于当前位置到目标位置的可行路径不止一条，因此需要规划出最合适的路径供机器人运行。路径规划算法最常使用的是A*算法及其改进，也有部分研究利用时空网络、蚁群优化、Dijkstra算法和Q-Learning算法的集成、无冲突路径规划等方法实现路径规划。但全部采用最优路径反而会造成更多的冲突和拥堵，也有研究考虑到和其他机器人发生碰撞，同时也要避免系统内出现死锁。冲突协调策略包括两类：一是事后调度，即发生冲突后利用一些启发式规则化解冲突，如优先级低的机器人等待或减速、利用交通规则启动和式。如图2所示，集中式是通过一个控制中心控制所有机器人的运行，能够实现全局优化，保证系统高效、平稳、最优化运行，但在的响应速度较慢。分布式是每个机器人各自控制自己的动作，机器场景，但机器人自身最优不能代表全局最优，且不同机器人的决策容易存在冲突，影响调度效率。混合式综合了集中式和分布式的特点，部分指令由控制中心下发，部分行动由机器人自主决策，机器人间也会产生信息交互，能够合理利用机器人能力，减少控制中心调度耗时，但仍有可能发生决策冲突，且难以获得全局最优调度方案。根据系统环境和机器人数量，研究者和从业人员会选择不同的系统组织结构。3.机器人调度方式不同的系统组织结构，决定了不同的机器人调度方式。不同调度方式的适用场合和优劣比较，见表2。表2不同调度方式的适用场合和优劣比较一个控制中心调度所有机器人，协调的场景三、大规模机器人仿真案例本文针对二维码导航的物流机器人，构建参数化模块化仿真模型，仿真大规模同构机器人集群系统和异构机器人集群系统的运行情况，并在分拣系统和存取系统中进行实验验证。仿真环境的硬件配置如下：Intel(R)Core(TM)i9-12900HCPU@2.50GHz、16.00GB内存、Intel(R)Iris(R)Xe1.参数化模块化仿真建模参数化和模块化仿真建模方法，是按照一定的规则将复杂的大系统分解为小的系统基本单元，然后针对各个系统基本单元进行规范化、通用化的模型搭建。形成通用的仿真模块后，再将这些基本单元模型赋予原系统的各项关键参数。因为复杂的现实系统由有限的子系统组合而成，将所开发模块和子系统对应起来，每个模块中包含子系统中的全部要素，再将有限的模块按照原来系统的逻辑进行有效连接，得到原来复杂大系统的仿真模型。系统内的机器人、人员、各功能区域等都可以独立建模为各个模块。2.大规模机器人集群调度仿真平台构建仿真平台的构建包括建立地图、机器人、功能区域、仿真动数据交互和分析等部分，利用启发式的任务分配规则、基于改进A*的路径规划算法和冲突协调与死锁避免策略等调度方法，实现物流机器人大规模集群调度。(1)地图地图构建是环境初始化的核心步骤，涵盖基础模块定义、布局模式选择、数据场景导入和作业节点生成等方面。由于物流机器人采用二维码导航的方式，系统内部的地图可以通过栅格法建模，每个小方格代表一个路块，可以作为地图中的基础模块，组成不同功能区域。以存取系统为例，如图3所示，每个格子内包含道路方向信息，红色为物料存储区域S,灰色为不可达路块一及立柱路块#,黄色为工作站，包括人员位置路块W和人员操作路块P。将表格直证各功能区域和道路方向。道路方向通过“^”“v”“<”“>”,333日333日图3按照Excel表格内场景数据生成仿真平台的地图(2)机器人机器人模块是物流机器人集群系统的核心组成部分，负责控制机器人执行调度方案、状态管理、环境感知、日志记录等功能。执行调度方案前需要按照调度算法获得的调度方案，包含机器人选择的路块，等待、通行、转弯、升降货架等行为，以及在每个路块上的时间。状态管理实时获取并同步更新机器人位置、任务状态、行进动作和目标点信息，通过当前状态数据和调度方案数据对比，能环境感知负责探测环境中的障碍物、其他机器人以及功能区块，并根据这些数据协助机器人判断其路径或动作是否可能发生碰撞。日志记录负责记录机器人运行过程中的关键事件和操作日志。为后续(3)功能区域部任务。目前被划分为机器人存储区域、机器人移动区域、物料存储区域、人员操作区域、系统设施设备区域等。机器人存储区域是所有机器人的初始位置和完成所有任务的终止位置。机器人只有在移动区域才能完成各类物流运输任务。机器人的移动区域由多个二维码组成，每个二维码路块都有指定的可移动方向，且必须保证机器人在物理上也是可移动的。物料存储区域、人员操作区域多为搬未粘贴二维码的区域，这些位置无法供机器人和人员经过，属于不可达区域。(4)仿真动画察其运行情况、避障行为和调度方案执行过程。本文按照时间推进仿真流程，以0.5s为1帧。(5)数据交互和分析数据交互主要是输入系统的地图、机器人设置、算法运行参数等数据，系统输出的调度方案执行情况、仿真统计数据等，以及仿真模型和调度算法之间的数据交互。数据分析用于对仿真过程中产生的各类数据进行整理、分析和评估，帮助系统优化性能、评估不同策略的有效性，并为后续的实验调整提供数据支撑。(6)调度方式本文采用混合式的调度架构，利用启发式的任务分配规则，集中分配任务；每个机器人接到任务后，基于改进A*的路径规划算法自行完成路径规划；机器人间出现冲突时，利用冲突协调与死锁避免策略集中判断如何避让。启发式的任务分配规则如下：考虑到任务的紧迫性，为优先级最高的任务分配机器人。这些任务需要优先处理。在所有优先级最高的任务中，选择机器人的规则是按照可用开始时间、与附近未分配任务的距离、任务货架路块与工作站的距离或随机的顺序排列；选择任务的规则，是根据任务货架路块与机器人当前路块的距离、任务货架路块与工作站的距离或随机的顺序排列。此时，使用曼哈顿距离估算距离，不考虑方向和冲突。由于机器人和任务的数量都很多，许多任务都有一个与机器人初始路块重叠的相应货架路块。如果机器人离开当前路块，而去接取另一个任务，就很容易出现死锁。因此，在分配任务时，这些机器人会首先接取这些任务，以避免冲突甚至死锁。改进后的A*算法用于路径规划和路径重规划。在路径规划时，更新可达路块集合时，不考虑其他机器人，以避免出现找不到可行路径的情况。如果因为出现冲突，需要路径重规划，在更新A*算法的可达路块集时，要考虑其他机器人，以避免机器人与其他机器人再次发生冲突和调用重规划算法。下一个路块的选择规则是，在可达路块集合中，选择曼哈顿距离最小，且转弯次数最少的路块。冲突协调与死锁避免策略，包括按优先级等待和路径重规划两种。优先级低的机器人必须等待优先级高的机器人离开，然后才能继续运行；或者不等待，直接重新规划路径，到达指定的终点路块。确定优先级的方法是综合考虑机器人是空载还是负载、是转弯还是直行，以及后续路径的长度等因素的权重。负载、直行或路径较长3.同构机器人集群仿真以存取系统为例，进行同构机器人集群调度仿真实验。在仿真系统中建立如图4所示的地图，整体布局为194×84,每个小方格代表一个路块，可以存放一个机器人、货架、拣货架或人员工位。机器人数量在600到1000之前，初始情况下，机器人随机位于某个货架下方，且无货物无搬运任务。任务数量为1000,随机生成任务机器人动作/时间对应如表3所示，简化了机器人的运行情况，通过表3机器人动作/时间对应表时间/s3图4同构机器人集群调度仿真实验(存取系统)有任务都被顺利完成。即机器人间无冲突，系统内不出现死锁，能够完成所有任务。表4展示了不同数量机器人的运行数据，每个实验组独立10次实验取平均值。可以看出，随着机器人数量增加，任务完成时间逐步降低，代表系统效率增加，但由于系统内机器人数量多，边际收益逐步降低；但仿真运行耗时和路径规划算法调用频次也逐步升高，说明大规模机器人运行时，对调度资源消耗量逐步增加；机器人总停车频次和等待时间的增长，也说明大规模机器人表4不同数量机器人运行数据时间/s仿真运行机器人总停车耗时/s频次/10调用频次/10⁴时间/10⁴时间/ms以图5所示的分拣系统为例，验证异构机器人集群调度情况。分拣口数量为94个，投递格口数量为550个。任务数量3000,按照7:3的比例分为小型任务(类型1)、中型任务(类型2)。配置群总量为200的前提下，动态配置类型A与类型B移动机器人的比表5展示了不同比例异构机器人运行数据，每个实验组独立10次实验取平均值。可以看出，机器人A、B的比例为3:2时，总任务完成时间最少，系统效率最高。仿真平台可以测试与验证不同比例的异表5不同数量机器人运行数据时间/s总等待时间长度/10⁴0AGV集度系统