大规模多智能体系统的智能规划

目录

1. 引言
2. 自动化仓储系统
   • 2.1 物流公司自动化仓储系统
   • 2.2 解决大规模仓储系统问题的技术
   • 2.3 多机器人协同问题的挑战
   • 2.4 解决多机器人协同问题的方法
3. Mapath问题
   • 3.1 Mapath问题的定义
   • 3.2 Mapath问题的解决难度
   • 3.3 优化算法的贡献
4. Map变种问题
   • 4.1 解释Map变种问题
   • 4.2 CBS算法在Map变种问题上的应用
5. 多机器人导航任务
   • 5.1 不同形状机器人的导航任务
   • 5.2 CBS算法在多机器人导航任务上的应用
6. Map算法应用实例
   • 6.1 Map算法在视频游戏中的应用
   • 6.2 Map算法在真实仓储数据上的应用
7. New RIBS 20 Flatline Challenge竞赛
   • 7.1 挑战描述
   • 7.2 算法解决方案
   • 7.3 竞赛成绩
8. 动态约束的执行框架
   • 8.1 动态约束的处理
   • 8.2 运行时框架
9. 路径规划与目标分配
   • 9.1 目标分配与路径规划问题
   • 9.2 基于优先级的规划算法
   • 9.3 基于局部搜索的优化算法
10. 结论
11. 进一步研究方向

引言

大家好，我是Hama，西蒙菲莎大学计算机科学学院的助理教授。在本视频中，我将向您介绍我们最近在大规模貸款系统中使用智能规划的研究进展。首先我们先来看一个已经运行的市场系统，即自动化仓储系统。这些仓储中心由亚马逊和阿里巴巴等物流公司建造。在本次讲座中，我将告诉您我们开发的计划技术如何解决仓储系统中的一些基本问题。在这些系统中，数百甚至数千台机器人需要安全地通过仓库网络和拥挤的交通，以完成在线订单的配送。

自动化仓储系统

2.1 物流公司自动化仓储系统

物流公司如亚马逊和阿里巴巴构建的自动化仓储中心是今天正在运行的一个例子。这些中心通过机器人进行自动化的拣货和分拣，以满足在线订单。

2.2 解决大规模仓储系统问题的技术

大规模仓储系统中多机器人协同问题的核心技术是解决多机器人路径规划问题，又称为Mapath问题。Mapath问题的目标是在给定图上找到多个机器人之间无碰撞的路径，可以最小化时间或最小化混合成本。

2.3 多机器人协同问题的挑战

多机器人协同问题在算法上是复杂的，有些问题甚至是AP-难解的。这意味着找到最优解的复杂度是非常高的，需要寻找近似算法来快速求解。

2.4 解决多机器人协同问题的方法

我们开发了一种基于冲突的搜索算法，称为冲突搜索或CBS。CBS是一个两层算法，它在低层针对单个机器人进行路径规划，而在高层上使用最佳优先搜索来解决路径中的碰撞问题。我们对CBS进行了改进，加速了算法的执行速度，并且能够处理更多的机器人。

使用我们开发的算法，我们已经能够在几分钟内为100个机器人进行路径规划。为了处理更大规模的问题，我们还提出了一种分支定界算法，可以在半分钟内为600个机器人求解路径规划问题，尽管这个算法并非最优或完全的解决方案。

Mapath问题

3.1 Mapath问题的定义

Mapath问题是指在给定图上为多个机器人找到无碰撞的路径的问题。该问题的目标可以是最小化总时间或混合成本，通过路径规划来实现。

3.2 Mapath问题的解决难度

Mapath问题的解决难度较高，存在AP-难解的复杂度结果。这意味着在一般情况下，很难找到最优解，需要寻找近似算法来求解。

3.3 优化算法的贡献

我们为Mapath问题的近似算法提供了新的可行性和近似性结果。这些算法基于冲突搜索(CBS)方法，经过改进后运行速度更快，并且能够处理更多的机器人。

Map变种问题

4.1 解释Map变种问题

我们将多个共享工作空间的机器人之间的路径规划问题解释为新的Map变种问题。我们开发了基于CBS算法的解决方案，保持了完整性和最优性的特性。

4.2 CBS算法在Map变种问题上的应用

我们将CBS算法应用于具有不同形状机器人的导航任务，并证明了该算法在解决Map变种问题上的有效性和可扩展性。

多机器人导航任务

5.1 不同形状机器人的导航任务

我们将CBS算法应用于多机器人导航任务，其中不同形状的机器人需要在保持期望间距的同时移动到目标位置。

5.2 CBS算法在多机器人导航任务上的应用

我们在多机器人导航任务中应用了CBS算法，并展示了该算法在解决机器人导航问题上的优越性能。

Map算法应用实例

6.1 Map算法在视频游戏中的应用

我们将Map算法应用于视频游戏中的机器人和角色的导航任务，使得它们能够同时保持期望的信息和移动到目标位置。

6.2 Map算法在真实仓储数据上的应用

我们通过使用真实仓储数据，在实际的分拣中心模拟器上测试了我们的Map算法。我们的目标是优化分拣站的闲置时间，并提高机器人的吞吐量。

New RIBS 20 Flatline Challenge竞赛

7.1 挑战描述

New RIBS 20 Flatline Challenge竞赛是一个要求解决具有不确定延迟的多链路地图问题的竞赛。我们通过规划和搜索技术开发了一个基于优先级的规划算法，并使用局部搜索来改善解决方案。

7.2 算法解决方案

我们开发了一个基于优先级规划的算法来解决竞赛中的链路问题，并通过局部搜索进一步优化解决方案。

7.3 竞赛成绩

我们开发的软件在New RIBS 20 Flatline Challenge竞赛中获得了第一名，击败了来自51个国家的700多名参赛者。我们的算法基于规划和搜索技术，表现优于所有基于强化学习的解法。

动态约束的执行框架

8.1 动态约束的处理

我们开发了一个执行框架来处理在地图解决方案执行过程中出现的动态约束。这些约束可能包括延迟问题。

8.2 运行时框架

我们开发了一个可执行的计划生成和执行框架，用于处理实际机器人的动态约束。该框架能够在五分钟内计算出3000个机器人的路径规划，并且在竞赛中性能超过了所有基于强化学习的解决方案。

路径规划与目标分配

9.1 目标分配与路径规划问题

我们将目标分配和路径规划问题结合起来，开发了一种针对多个机器人的最优算法。

9.2 基于优先级的规划算法

我们开发了一种基于优先级的路径规划算法，能够在不到一秒的总规划时间内处理30分钟的操作。这包括250个机器人和2000个任务，在模拟仓储系统中机器人需要取货和送货。

9.3 基于局部搜索的优化算法

我们在实际的分拣中心模拟器上测试了我们的路径规划算法，并展示了算法在减少分拣站空闲时间和提高机器人运输效率方面的良好性能。

结论

通过我们的研究，我们已经在多机器人系统中的路径规划与目标分配问题上取得了一系列重要的科学贡献。我们的算法能够处理大规模的问题并在实际应用中取得了优异的性能。

进一步研究方向

我们的研究正在不断发展，包括开发基于学习的Map算法和对长期规划的更好理论理解。我们还计划研究更复杂的联合任务分配和路径规划问题，以应对现实世界中更具挑战性的问题。