近日，極智嘉副總裁、AI研究院院長譚文哲博士受邀出席中國物流科技年度盛會“2022全球物流技術大會”，在“運籌學物流應用論壇”上發(fā)表主題演講，分享運籌學在智能物流機器人中的應用，并在圓桌討論環(huán)節(jié)與阿里巴巴、華為及頂尖高校專家學者，共探運籌學在企業(yè)應用中的經驗。

“2022全球物流技術大會”由中國物流與采購聯(lián)合會主辦，作為業(yè)內前沿技術創(chuàng)新的風向標，本屆大會云集了全球的學術泰斗和專家，共話最新技術成果和未來研發(fā)方向。

在運籌學論壇上，普林斯頓大學榮譽退休教授Warren B. Powell和清華大學工業(yè)工程系趙磊教授均強調，運籌學中的序貫決策模型(Sequential Decision Model)已成為當前物流管理中一種有效的建模與分析手段。隨后，極智嘉譚文哲博士著重展開介紹了序貫決策模型在機器人智能物流中的應用，并且通過數據驅動的方式不斷提升系統(tǒng)決策的智能性，有效助力客戶降本增效。

▲ 極智嘉譚文哲博士分享運籌學在智能物流中的應用

序貫決策在極智嘉的應用

基于機器人的智能倉可以建模成典型的序貫決策模型(圖1)，每個時刻系統(tǒng)都可以收集諸如訂單、工作站、庫存、機器人等信息，同時基于這些信息做出諸如派單命中、任務分派、路徑規(guī)劃調度等系列決策，而下一時刻的環(huán)境信息又是基于這些決策產生新的變化。

▲ 圖1 智能倉中的序貫決策問題

這個過程不斷循環(huán)，最終完成智能倉儲系統(tǒng)功能。每個時間片都面臨著海量的信息，需要做出非常復雜的涉及各個系統(tǒng)的決策，極智嘉將系統(tǒng)解耦成幾個關鍵的步驟分步攻克。

任務分派和派單命中是其中最典型的兩個問題。任務分派(如圖2)指的是倉庫中貨架搬運任務與機器人之間的分配問題，旨在建立多任務與多機器人的映射關系，這是一個非常經典的運籌優(yōu)化問題。

▲ 圖2 任務分派示意圖

第二種是智能倉中面臨的派單命中問題，旨在建立訂單-工作站-庫存三者之間的決策匹配關系(如圖3)。這兩個典型問題以往的決策現場往往僅考慮當時的情況并基于人工設定規(guī)則，如果考慮決策對后續(xù)過程帶來的影響是否有更好的決策表現呢?在譚文哲博士的報告中展開介紹了極智嘉對任務分派序貫決策的系列探索。

▲ 圖3 派單命中示意圖

探索一：歷史數據驅動的任務分派

▲ 圖4 任務分派

任務分派是極智嘉無人倉運行的基礎，任務分配決策的好壞直接決定了現場的訂單完成時間、機器人利用率等效率指標(圖4)。為了兼顧各方面的需求，極智嘉通?？紤]現場交通、訂單優(yōu)先級、貨架熱度等多重因素進行分配。在不斷落地的實踐中，極智嘉也持續(xù)在思考一個問題：倉庫現場面臨著時刻不同的不確定性，不同倉庫、不同工作站排隊情況、甚至不同的揀貨速度下，任務的價值是否也應該不同？

▲ 圖5 使用貝爾曼方程為智能倉任務分派問題建模

極智嘉通過豐富的場景落地和持續(xù)的技術創(chuàng)新，提出了數據驅動的全局智能任務分派模型(圖5)。算法首先收集了不同倉庫、不同時刻、不同場景的大量歷史數據，并對其當時的情形進行回顧性挖掘分析，生成預期價值函數。而在實時運行過程中，算法又將實時計算當前時刻的即時價值并綜合考慮通過預期價值函數生成的預期價值，最后的匹配中使系統(tǒng)獎勵值最大的方案將被采用。

運行數據將積累入歷史數據庫中，更新訓練價值函數，形成算法優(yōu)化的閉環(huán)，且不需要實施人員專門針對特定倉庫進行預先的規(guī)則設定，完全由數據驅動自適應倉庫的特點，大幅減少了項目的實施周期。新的綜合價值綜合考慮了當前的狀態(tài)與預期的影響，有助于更好地感知不同時刻任務狀態(tài)與時序預期狀態(tài)，在抽樣場景中實現了相同條件下效率15%以上的提升(圖6)。

▲ 圖6 抽樣場景中相同條件下效率提升15%以上

探索二：自適應價值函數驅動的任務分派算法

探索1成功帶來了可觀的效率提升，同時引發(fā)了極智嘉進一步的思考，任務的價值函數是否可感知訂單和機器人密度等環(huán)境信息，并隨著系統(tǒng)運行自適應改變？

針對上述問題，極智嘉提出了全新的自適應價值函數驅動的任務規(guī)劃算法。算法在任務分配過程中進一步考慮路徑規(guī)劃的影響，使用在線強化學習(Online Reinforcement Learning)方法挖掘訂單需求特點，并自適應調整任務分配策略，實現對全局效率瓶頸的精準感知，使優(yōu)化過程更具有針對性、實時性，從而提高了AMR的運行效率。

如圖7所示，整個算法流程分為四個步驟：信息收集、模型訓練、任務選擇、路徑規(guī)劃。首先，算法收集揀貨員、AMR和貨架的時空信息(例如揀貨員的揀貨時間、貨架的任務預計完成時間、AMR的位置信息等)。收集完成后，自適應規(guī)劃模塊基于馬爾可夫決策過程模型(Markov Decision Process, MDP)對時空信息建模，并使用強化學習中的Q-Learning方法訓練價值函數。之后，算法基于價值函數選擇合適的任務分配給AMR，最后基于選擇方案為AMR規(guī)劃路徑。

▲ 圖7 完整算法流程圖

其中序貫決策模型中的狀態(tài)定義中綜合考慮了貨架和揀貨員的工作狀態(tài)，該建模方法有助于讓強化學習智能體(Agent)更好地感知從搬運到揀貨全流程中的效率瓶頸。此外，采用在線學習的方法及時更新狀態(tài)-動作價值函數，進一步提高了算法的自適應性。

▲ 圖8 效率瓶頸隨時間在不同階段變化的現象

一直以來，極智嘉都在積極探索在任務分派模型的算法上的創(chuàng)新，目前同場景數字孿生環(huán)境下已帶來20%以上的提升。未來，極智嘉將堅持初心，不斷優(yōu)化提升，更好地為智慧物流賦能。