多主体

基于冲突的搜索,以实现最佳的多智能体寻路

Submitted by neurta on Tue, 01/12/2021 - 16:31
在多主体寻路问题(MAPF)中,我们得到了一组主体,每个主体都有各自的起始位置和目标位置。任务是查找所有代理的路径,同时避免冲突。解决此问题的大多数先前工作已将单个代理视为单个“联合代理”,然后应用了A *算法的单代理搜索变体。 在本文中,我们提出了一种基于冲突的搜索(CBS)新的最优多主体寻路算法。CBS是一种两级算法,不会将问题转换为单个“联合代理”模型。在较高级别上,对冲突树(CT)执行搜索,该树是基于各个代理之间的冲突的树。CT中的每个节点代表了一组对代理人运动的约束。在低级别,执行快速单代理搜索以满足高层CT节点施加的约束。在许多情况下,这种两级公式使CBS可以检查少于A *的状态,同时仍保持最佳状态。我们分析CBS并显示其优缺点。 此外,我们介绍了Meta-Agent CBS(MA-CBS)算法。MA-CBS是CBS的概括。与基本CBS不同,MA-CBS不仅限于低级别的单代理搜索。取而代之的是,MA-CBS允许将代理合并为一小组联合代理。这减轻了基本CBS的某些缺点,并进一步提高了性能。实际上,MA-CBS是可以建立在任何最佳而完整的MAPF求解器之上的框架,以增强其性能。在各种问题上的实验结果表明,与以前的方法相比,速度提高了一个数量级。