Do We Run Large-Scale Multi-Robot Systems on the Edge? More Evidence for Two-Phase Performance in System Size Scaling
作者: Jonas Kuckling, Robin Luckey, Viktor Avrutin, Andrew Vardy, Andreagiovanni Reina, Heiko Hamann · ICRA 2024
许可协议
- 开放获取
- 论文: CC BY 4.0
以下内容均依据论文全文，按其 CC BY 4.0 许可协议使用；其中的图已注明作者。
一句话总结
对三个多机器人系统的仿真表明，在临界群体规模下，性能分化为接近最优和接近零的两类运行；一个种群模型把这一现象与分岔和漫长的暂态联系起来。
为何重要
为追求最高吞吐量而调校机器人车队或群体的运营者，可能在不知情的情况下让系统运行在崩溃边缘，而漫长的暂态会让这样的系统在崩溃前的一段时间里看起来很正常。该模型还预测了迟滞现象，因此在运行期间增加或移除机器人（某些稳健可扩展性方法会这样做）可能导致性能突然跳变。
问题
群体性能通常以随群体密度变化的平均值来报告，它先上升，在临界系统规模处达到峰值，然后下降。这个平均值可能掩盖一种双峰结果：在临界规模附近，一些运行几乎达到最优，另一些则陷入拥堵而崩溃，因此一个按平均性能峰值调校的系统可能离崩溃很近。
提出的方法
作者仿真了三个系统（一个由 3000 多台悬挂在轨道上的 AFLE 存储机器人组成的仓库、使用 lasso 方法的群体物体聚类，以及朝向光信标的涌现趋性（emergent taxis）），并绘制性能随群体规模变化的完整分布，而不是平均值。随后他们用两种方式对该效应建模：一个服务时间取决于队列长度的 M/M/1 队列，以及一个三状态种群模型（solo、grupo、fermo），该模型写成常微分方程，并用非线性动力学工具进行分析。
关键见解
- 在临界系统规模附近，结果呈双峰分布：各次运行要么接近最高性能，要么崩溃到接近零的性能，几乎没有介于两者之间的情况。
- 在种群模型中，鞍结分岔意味着增加一台机器人就可能使系统从高生产率切换到低生产率，而移除机器人只有在群体规模更小时才能使其切换回来（迟滞）。
- 暂态时间在临界状态附近呈超指数增长（临界慢化），作者将其追溯到 (N, k1) 参数空间中一个余维 2 的尖点分岔；因此一个系统在崩溃之前可能是在“借来的时间”上运行。
- 一个简单的修正 M/M/1 队列就已经再现了线性增长以及在临界到达率处的崩溃，其曲线与种群模型的曲线相似。
主要结果
- 仓库（每个到达率重复 96 次）：吞吐量随到达率线性上升，直到每小时约 10⁴ 个 AFLE，此后一些运行陷入拥堵、吞吐量接近零，而另一些仍保持在最高水平。
- 物体聚类（每个群体规模 1000 次运行，1 到 20 台机器人）：最佳性能出现在约 6 台机器人；从 10 台机器人起，结果分化为成功和不成功的运行。
- 涌现趋性（每个群体规模 800 次运行，2 到 40 台机器人，数据来自早期工作）：在约 15 台机器人时达到最高速度，此时出现了第二个低速相。
- 修正的 M/M/1 队列（平均到达率 0.4 到 0.9，每个 500 个样本）：在约 0.65 的临界平均到达率处崩溃。
- 使用默认速率的种群模型：solo 机器人的数量在 N = 31 时达到峰值，随后迅速下降；当 k1 = 0.001 时，两个鞍结分岔界定了一个双稳态区间，图 6 展示了位于该区间内 N = 40 时的状态空间。
局限
- 作者表示，哪种模型最能描述两相性能仍是未解决的问题，未来的研究必须表明这种效应在工业应用中是否真实存在且具有相关性。
- 三个场景都是仿真；仓库模型是一个单向通行、没有物理的网格世界，且没有对存储轨道段建模。
- 涌现趋性的结果沿用自之前的一篇论文，而不是重新运行的。
- 队列常数被描述为任意选取，两个模型都被称为只是定性地刻画了该行为；论文没有用仿真数据拟合它们。
对领域的影响
获得 IEEE ICRA 2024 多机器人系统最佳论文奖，被引用 14 次。论文链接了其物体聚类仿真器的开源代码和一段视频；没有提到发布仓库仿真器。
摘要
随着越来越多的移动机器人进入真实世界的应用，更多机器人在同一空间中共存、交互，并可能协作。为此类系统提供系统规模可扩展性的方法是已知的，例如来自群体机器人学。示例策略包括自组织行为、严格的去中心化方法以及限制机器人之间的通信。尽管采用了这些策略，任何多机器人系统在超过某个临界系统规模（即机器人数量）时都会崩溃，因为太多机器人共享同一资源（例如空间、通信信道）。我们基于仿真提供了额外的证据，表明在这些临界系统规模下，系统性能分化为两个相：接近最优的性能和最低的性能。我们推测，在按最优系统规模配置的真实世界应用中，看似高性能的系统实际上可能是在靠借来的时间维持，因为它正处在通向崩溃的暂态过程中。我们提供了两种建模选项（基于排队论和种群模型），可能有助于支持这一推理。
链接
- arXiv 2310.11843: https://arxiv.org/abs/2310.11843
- DOI 10.1109/ICRA57147.2024.10610771: https://doi.org/10.1109/ICRA57147.2024.10610771
- PDF: https://arxiv.org/pdf/2310.11843v1
- 代码: https://github.com/avardy/cwaggle_lasso