极智嘉提出全新适用工业场景的多机器人路径规划算法

近日，全球AMR引领者极智嘉(Geek+)联合香港大学提出全新适用工业场景的多机器人路径规划算法，并在云计算与智能系统国际会议IEEE CCIS上成功发表论文，科研实力再获权威坚实认证。

该创新算法侧重考虑机器人运动不确定性的多机器人路径规划问题，并提出相应的最优算法决策，这使算法得以更加适配实际工业应用场景，为学术研究与工业应用之间搭建起落地桥梁，推动人工智能领域朝实用方向发展。

效率瓶颈全链路感知

在线学习自适应规划

智能AMR集群路径规划算法是保证机器人集群系统高效运转的重要支撑。传统规划算法通常假设AMR具有固定的移动速度，忽略了AMR运行速度的不确定性。这种简化的假设可以大大降低系统模型的复杂度并减少运算耗时度，然而同样会带来大量规划结果与AMR实际行走的冲突，导致算法结果无法应用于实际场景。

事实上，实际的AMR应用场景中存在着多种不确定性。例如，自身定位不准确及周围环境建模不完备、AMR速度的时变性和不确定性等。本论文主要针对AMR速度的时变性和不确定性，通过对不确定性的数学建模以及重规划时机的选取配合，更好的规划出高冗余度的路径行走方案并随时跟进更新保持不确定性的范围可控。

论文提出的算法具备普适性、可并行、且可解释性强，更加适用于工业现场，已经成功应用于极智嘉全柔性仓储物流以及工业搬运解决方案。

▲ 极智嘉提供覆盖仓储及制造的全品类机器人产品

算法成果详解

整个算法由三个模块组成，分别是路径规划模块、冲突检测模块、重规划模块。建模不确定性的关键在于路径规划模块，论文将其建模为基于正态分布的冲突概率计算损失函数(图1)，并将其与经典的A*算法相结合。这是来源于实践且非常有效的方法，直觉上可认为机器人在一定时长内的行走通常是可预测的，自主行走时长越长预测偏差越大。通过这个损失函数，路径规划的计算中将更侧重于初期的路径结果，为每一个AMR规划出初期冲突尽可能少的路径。

▲图1 基于正态分布的冲突概率计算损失函数

然而，这种基于概率的方法并不能消除所有的冲突，并且速度的不确定性会不断产生新的冲突。为了解决这些问题，论文提供了另外两个模块。冲突检测及重规划模块基于规则定期检测存在冲突的AMR并重新规划路径。当多个AMR同时预留同一节点时，调度模块确定预留的优先级。

▲图2 常见的多机器人冲突形式

实验结果

论文将所提出的算法含有80个智能体的30×30的网格地图中进行测试，测试环境如下图3所示。

▲图3 算法测试环境

本文所提出的算法与其他三个工业上常用的算法进行了定量化的对比：所提出算法（PA）、具有不同损失函数计算方式的算法（ADCC）、合作A*算法（CA）、基于优先级搜索（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]