论文标题
通过脱钩和集成的目标顶点订购多进球的多目标路径查找
Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering
论文作者
论文摘要
我们介绍了多目标多代理路径查找（MAPF $^{mg} $），该查找概括了标准离散多代理路径查找（MAPF）问题。 MAPF中的任务是在无向图中从其起始顶点到每个代理一个单独的目标顶点，而MAPF $^{mg} $分配每个代理多个目标顶点，而任务是至少访问每个代理。求解mapf $^{mg} $不仅需要为单个代理找到无冲突的碰撞路径，而且还需要确定访问代理的目标顶点的顺序，以便优化诸如成本之和成本之类的共同目标。我们建议使用不同范式来解决MAPF $^{mg} $：一种基于启发式搜索的搜索算法，称为Hamiltonian-CBS（HCBS），以及使用SMT范式构建的基于汇编的算法，称为SMT-Hamiltonian-CBS（SMT-HCB）。实验比较表明基于汇编的方法的局限性。
We introduce multi-goal multi agent path finding (MAPF$^{MG}$) which generalizes the standard discrete multi-agent path finding (MAPF) problem. While the task in MAPF is to navigate agents in an undirected graph from their starting vertices to one individual goal vertex per agent, MAPF$^{MG}$ assigns each agent multiple goal vertices and the task is to visit each of them at least once. Solving MAPF$^{MG}$ not only requires finding collision free paths for individual agents but also determining the order of visiting agent's goal vertices so that common objectives like the sum-of-costs are optimized. We suggest two novel algorithms using different paradigms to address MAPF$^{MG}$: a heuristic search-based search algorithm called Hamiltonian-CBS (HCBS) and a compilation-based algorithm built using the SMT paradigm, called SMT-Hamiltonian-CBS (SMT-HCBS). Experimental comparison suggests limitations of compilation-based approach.
