近日，全球AMR引領者極智嘉(Geek+)聯(lián)合香港大學提出全新適用工業(yè)場景的多機器人路徑規(guī)劃算法，并在云計算與智能系統(tǒng)國際會議IEEE CCIS上成功發(fā)表論文，科研實力再獲權威堅實認證。

該創(chuàng)新算法側重考慮機器人運動不確定性的多機器人路徑規(guī)劃問題，并提出相應的最優(yōu)算法決策，這使算法得以更加適配實際工業(yè)應用場景，為學術研究與工業(yè)應用之間搭建起落地橋梁，推動人工智能領域朝實用方向發(fā)展。

效率瓶頸全鏈路感知

在線學習自適應規(guī)劃

智能AMR集群路徑規(guī)劃算法是保證機器人集群系統(tǒng)高效運轉的重要支撐。傳統(tǒng)規(guī)劃算法通常假設AMR具有固定的移動速度，忽略了AMR運行速度的不確定性。這種簡化的假設可以大大降低系統(tǒng)模型的復雜度并減少運算耗時度，然而同樣會帶來大量規(guī)劃結果與AMR實際行走的沖突，導致算法結果無法應用于實際場景。

事實上，實際的AMR應用場景中存在著多種不確定性。例如，自身定位不準確及周圍環(huán)境建模不完備、AMR速度的時變性和不確定性等。本論文主要針對AMR速度的時變性和不確定性，通過對不確定性的數(shù)學建模以及重規(guī)劃時機的選取配合，更好的規(guī)劃出高冗余度的路徑行走方案并隨時跟進更新保持不確定性的范圍可控。

論文提出的算法具備普適性、可并行、且可解釋性強，更加適用于工業(yè)現(xiàn)場，已經成功應用于極智嘉全柔性倉儲物流以及工業(yè)搬運解決方案。

▲ 極智嘉提供覆蓋倉儲及制造的全品類機器人產品

算法成果詳解

整個算法由三個模塊組成，分別是路徑規(guī)劃模塊、沖突檢測模塊、重規(guī)劃模塊。建模不確定性的關鍵在于路徑規(guī)劃模塊，論文將其建模為基于正態(tài)分布的沖突概率計算損失函數(shù)(圖1)，并將其與經典的A*算法相結合。這是來源于實踐且非常有效的方法，直覺上可認為機器人在一定時長內的行走通常是可預測的，自主行走時長越長預測偏差越大。通過這個損失函數(shù)，路徑規(guī)劃的計算中將更側重于初期的路徑結果，為每一個AMR規(guī)劃出初期沖突盡可能少的路徑。

▲圖1 基于正態(tài)分布的沖突概率計算損失函數(shù)

然而，這種基于概率的方法并不能消除所有的沖突，并且速度的不確定性會不斷產生新的沖突。為了解決這些問題，論文提供了另外兩個模塊。沖突檢測及重規(guī)劃模塊基于規(guī)則定期檢測存在沖突的AMR并重新規(guī)劃路徑。當多個AMR同時預留同一節(jié)點時，調度模塊確定預留的優(yōu)先級。

▲圖2 常見的多機器人沖突形式

實驗結果

論文將所提出的算法含有80個智能體的30×30的網格地圖中進行測試，測試環(huán)境如下圖3所示。

▲圖3 算法測試環(huán)境

本文講所提出的算法與其他三個工業(yè)上常用的算法進行了定量化的對比：所提出算法（PA）、具有不同損失函數(shù)計算方式的算法（ADCC）、合作A*算法（CA）、基于優(yōu)先級搜索（PBS）。極智嘉使用這四種算法在進行測試，實驗結果如表1和圖2所示。多次實驗結果表明其性能大幅領先（圖4，圖5）。

▲圖4 四種算法在不同下完成時間的平均值

▲圖5 四種算法在不同v下完成時間的箱線圖 (a) v=1, (b) v∈[0.5,1], (c) v∈[0,1], (d) v=0.5, (e) v∈[0,0.5]

關于IEEE CCIS 2022

第八屆IEEE云計算與智能系統(tǒng)國際會議作為連接智能計算領域學者和企業(yè)的橋梁，為促進國內外學者的交流提供了一個全球性的平臺。本屆大會涵蓋數(shù)據挖掘、深度學習、計算智能、計算機視覺等領域的熱點研究問題。