AI算法丨数据驱动的序贯决策在智能物流中的应用

近日，极智嘉副总裁、AI研究院院长谭文哲博士受邀出席中国物流科技年度盛会“2022全球物流技术大会”，在“运筹学物流应用论坛”上发表主题演讲，分享运筹学在智能物流机器人中的应用，并在圆桌讨论环节与阿里巴巴、华为及顶尖高校专家学者，共探运筹学在企业应用中的经验。

“2022全球物流技术大会”由中国物流与采购联合会主办，作为业内前沿技术创新的风向标，本届大会云集了全球的学术泰斗和专家，共话最新技术成果和未来研发方向。

在运筹学论坛上，普林斯顿大学荣誉退休教授Warren B. Powell和清华大学工业工程系赵磊教授均强调，运筹学中的序贯决策模型(Sequential Decision Model)已成为当前物流管理中一种有效的建模与分析手段。随后，极智嘉谭文哲博士着重展开介绍了序贯决策模型在机器人智能物流中的应用，并且通过数据驱动的方式不断提升系统决策的智能性，有效助力客户降本增效。

▲ 极智嘉谭文哲博士分享运筹学在智能物流中的应用

序贯决策在极智嘉的应用

基于机器人的智能仓可以建模成典型的序贯决策模型(图1)，每个时刻系统都可以收集诸如订单、工作站、库存、机器人等信息，同时基于这些信息做出诸如派单命中、任务分派、路径规划调度等系列决策，而下一时刻的环境信息又是基于这些决策产生新的变化。

▲ 图1 智能仓中的序贯决策问题

这个过程不断循环，最终完成智能仓储系统功能。每个时间片都面临着海量的信息，需要做出非常复杂的涉及各个系统的决策，极智嘉将系统解耦成几个关键的步骤分步攻克。

任务分派和派单命中是其中最典型的两个问题。任务分派(如图2)指的是仓库中货架搬运任务与机器人之间的分配问题，旨在建立多任务与多机器人的映射关系，这是一个非常经典的运筹优化问题。

▲ 图2 任务分派示意图

第二种是智能仓中面临的派单命中问题，旨在建立订单-工作站-库存三者之间的决策匹配关系(如图3)。这两个典型问题以往的决策现场往往仅考虑当时的情况并基于人工设定规则，如果考虑决策对后续过程带来的影响是否有更好的决策表现呢?在谭文哲博士的报告中展开介绍了极智嘉对任务分派序贯决策的系列探索。

▲ 图3 派单命中示意图

探索一：历史数据驱动的任务分派

▲ 图4 任务分派

任务分派是极智嘉无人仓运行的基础，任务分配决策的好坏直接决定了现场的订单完成时间、机器人利用率等效率指标(图4)。为了兼顾各方面的需求，极智嘉通常考虑现场交通、订单优先级、货架热度等多重因素进行分配。在不断落地的实践中，极智嘉也持续在思考一个问题：仓库现场面临着时刻不同的不确定性，不同仓库、不同工作站排队情况、甚至不同的拣货速度下，任务的价值是否也应该不同？

▲ 图5 使用贝尔曼方程为智能仓任务分派问题建模

极智嘉通过丰富的场景落地和持续的技术创新，提出了数据驱动的全局智能任务分派模型(图5)。算法首先收集了不同仓库、不同时刻、不同场景的大量历史数据，并对其当时的情形进行回顾性挖掘分析，生成预期价值函数。而在实时运行过程中，算法又将实时计算当前时刻的即时价值并综合考虑通过预期价值函数生成的预期价值，最后的匹配中使系统奖励值最大的方案将被采用。

运行数据将积累入历史数据库中，更新训练价值函数，形成算法优化的闭环，且不需要实施人员专门针对特定仓库进行预先的规则设定，完全由数据驱动自适应仓库的特点，大幅减少了项目的实施周期。新的综合价值综合考虑了当前的状态与预期的影响，有助于更好地感知不同时刻任务状态与时序预期状态，在抽样场景中实现了相同条件下效率15%以上的提升(图6)。

▲ 图6 抽样场景中相同条件下效率提升15%以上

探索二：自适应价值函数驱动的任务分派算法

探索1成功带来了可观的效率提升，同时引发了极智嘉进一步的思考，任务的价值函数是否可感知订单和机器人密度等环境信息，并随着系统运行自适应改变？

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

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

▲ 图7 完整算法流程图

其中序贯决策模型中的状态定义中综合考虑了货架和拣货员的工作状态，该建模方法有助于让强化学习智能体(Agent)更好地感知从搬运到拣货全流程中的效率瓶颈。此外，采用在线学习的方法及时更新状态-动作价值函数，进一步提高了算法的自适应性。

▲ 图8 效率瓶颈随时间在不同阶段变化的现象

一直以来，极智嘉都在积极探索在任务分派模型的算法上的创新，目前同场景数字孪生环境下已带来20%以上的提升。未来，极智嘉将坚持初心，不断优化提升，更好地为智慧物流赋能。