近期，全球AMR引领者极智嘉(Geek+)联合北京航空航天大学和新加坡管理大学提出全新AMR集群智能规划算法，并成功获选大数据领域国际顶级会议ICDE 2022，在坚持前沿技术自主创新之道上再次取得新突破，高筑大规模机器人集群协作算法技术壁垒。

ICDE(IEEE International Conference on Data Engineering)是大数据领域顶级学术会议之一，是IEEE(电气电子工程师学会)的旗舰会议，和SIGMOD、VLDB 并称数据管理与数据库领域的三大国际顶尖学术会议，在全球数据库工程师群体内影响非凡。

效率瓶颈全链路感知

在线学习自适应规划

智能AMR集群规划算法是保证机器人集群系统高效运转的重要支撑。传统规划算法一方面对任务分配和路径规划过程分离处理，导致优化过程协同性差；另一方面算法的数据驱动程度不足，造成优化方法僵化。

针对上述问题，极智嘉提出全新的自适应任务规划算法。算法在任务分配过程中考虑路径规划的影响，使用在线强化学习(Online Reinforcement Learning，Online RL)方法挖掘订单需求特点，并自适应调整任务分配策略，实现对全局效率瓶颈的精准感知，使优化过程更具有针对性、实时性，从而提高了AMR的运行效率。

文章提出基于距离的剪枝策略和路径压缩技术，有效减少了算法的计算耗时和资源占用，任务和路径规划效率得以大幅提升，助力多元、异构、大规模AMR集群调度场景落地。该算法目前已经成功应用于极智嘉全柔性货箱到人RoboShuttle+P40解决方案，并实现了上万平米、数百台异构机器人高效混合协同调度。

▲ 点击全屏观看效果更佳

算法成果详解

算法流程如图1所示。整个算法流程分为四个步骤：信息收集、模型训练、任务选择、路径规划。首先，算法收集拣货员、AMR和货架的时空信息(例如拣货员的拣货时间、货架的任务预计完成时间、AMR的位置信息等)。其次，收集完成后，自适应规划模块基于马尔可夫决策过程模型(Markov Decision Process, MDP)对时空信息建模，并使用强化学习中的Q-Learning方法训练价值函数。之后，算法基于价值函数选择合适的任务分配给AMR，最后基于选择方案为AMR规划路径。

▲ 图1 算法流程

其中马尔可夫决策过程模型中的状态建模中综合考虑了货架和拣货员的工作状态，该建模方法有助于让强化学习智能体(Agent)更好地感知从搬运到拣货全流程中的效率瓶颈。此外，采用在线学习的方法及时更新状态-动作价值函数，进一步提高了算法的自适应性。图2表明了效率瓶颈随时间在不同阶段变化的现象。

▲ 图2 效率瓶颈变化

新算法在人工和真实数据集上取得了显著效果，为了全面真实的模拟仓库环境，本研究建立了测试环境，实现了对拣货过程的全链路模拟验证。实验结果表明其性能大幅超越了多智能体路径规划和时空任务分配领域的相关算法（图3）。

▲ 图3 实验结果

关于ICDE 2022

国际数据工程会议（IEEE International Conference on Data Engineering, ICDE）将于2022年5月在马来西亚吉隆坡举行，吸引众多国际顶级高校、公司和研究机构展示前沿研究。会议内容覆盖数据挖掘、知识发现、面向机器学习的数据库技术等。该会议属于中国计算机学会（CCF）推荐的A类会议，是数据挖掘/数据库领域知名国际顶级会议。