Conflict-Based Steiner Search for Multi-Agent Combinatorial Path Finding
Conflict-Based Steiner Search for Multi-Agent Combinatorial Path Finding
复制标题
基于冲突的斯坦纳搜索多智能体组合路径查找
DOI：
10.15607/rss.2022.xviii.058
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
H. Choset
中科院分区：
文献类型：
--
作者：
Z. Ren;S. Rathinam;H. Choset
传统的多智能体路径查找（MAPF）问题旨在计算多个智能体从其各自的起始位置到预先分配的目的地的无冲突路径的集合。这项工作认为，广义版本的MAPF称为多代理组合路径查找（MCPF）的代理必须集体访问大量的中间目标位置沿着他们的路径到达目的地之前。这个问题不仅涉及规划多个代理的无冲突路径，但也分配目标，并指定每个代理的访问顺序（即多目标排序）。为了解决这个问题，我们利用著名的基于统计的搜索（CBS）的MAPF，并提出了一个新的框架，称为基于统计的施泰纳搜索（CBSS）。CBSS交织（1）CBS中的冲突解决策略以绕过MAPF中的维数灾难，以及（2）多个旅行商算法来处理多目标排序中的组合学，以计算代理在访问所有目标时的最优或有界次优路径。我们广泛的测试验证了CBSS在计算较短路径和提高成功率方面优于基线方法，最多可用于20个代理和50个目标。我们还评估CBSS与几个MCPF的变种，这表明了我们的问题制定和CBSS框架的一般性。
—Conventional Multi-Agent Path Finding (MAPF) problems aim to compute an ensemble of collision-free paths for multiple agents from their respective starting locations to pre-allocated destinations. This work considers a generalized version of MAPF called Multi-Agent Combinatorial Path Finding (MCPF) where agents must collectively visit a large number of intermediate target locations along their paths before arriving at destinations. This problem involves not only planning collision-free paths for multiple agents but also assigning targets and specifying the visiting order for each agent (i.e. multi-target sequencing). To solve the problem, we leverage the well-known Conflict-Based Search (CBS) for MAPF and propose a novel framework called Conflict-Based Steiner Search (CBSS). CBSS interleaves (1) the conflict resolving strategy in CBS to bypass the curse of dimensionality in MAPF and (2) multiple traveling salesman algorithms to handle the combinatorics in multi-target sequencing, to compute optimal or bounded sub-optimal paths for agents while visiting all the targets. Our extensive tests verify the advantage of CBSS over baseline approaches in terms of computing shorter paths and improving success rates within a runtime limit for up to 20 agents and 50 targets. We also evaluate CBSS with several MCPF variants, which demonstrates the generality of our problem formulation and the CBSS framework.