Cost Splitting for Multi-Objective Conflict-Based Search
The Multi-Objective Multi-Agent Path Finding (MO-MAPF) problem is the problem of finding the Pareto-optimal frontier of collision-free paths for a team of agents while minimizing multiple cost metrics. Examples of such cost metrics include arrival times, travel distances, and energy consumption.In this paper, we focus on the Multi-Objective Conflict-Based Search (MO-CBS) algorithm, a state-of-the-art MO-MAPF algorithm. We show that the standard splitting strategy used by MO-CBS can lead to duplicate search nodes and hence can duplicate the search effort that MO-CBS needs to make. To address this issue, we propose two new splitting strategies for MO-CBS, namely cost splitting and disjoint cost splitting. Our theoretical results show that, when combined with either of these two new splitting strategies, MO-CBS maintains its completeness and optimality guarantees. Our experimental results show that disjoint cost splitting, our best splitting strategy, speeds up MO-CBS by up to two orders of magnitude and substantially improves its success rates in various settings.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Agent Path FindingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search
While the study of unit-cost Multi-Agent Pathfinding (MAPF) problems has been popular, many real-world problems require continuous time and costs due to various movement models. In this context, this paper studies symmet…
Resolving Head-On Conflicts for Multi-Agent Path Finding with Conflict-Based Search
Conflict-Based Search (CBS) is a popular framework for solving the Multi-Agent Path Finding problem. Some of the conflicts incur a foreseeable conflict in one or both of the children nodes when splitting on them. This pa…
Multi-Agent Path FindingLearning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search
Conflict-Based Search (CBS) is a state-of-the-art algorithm for multi-agent path finding. At the high level, CBS repeatedly detects conflicts and resolves one of them by splitting the current problem into two subproblems…
Multi-Agent Path FindingA Bi-Objective Approach to Last-Mile Delivery Routing Considering Driver Preferences
The Multi-Objective Vehicle Routing Problem (MOVRP) is a complex optimization problem in the transportation and logistics industry. This paper proposes a novel approach to the MOVRP that aims to create routes that consid…
Multi-Objective Multi-Agent Path Finding with Lexicographic Cost Preferences
Many real-world scenarios require multiple agents to coordinate in shared environments, while balancing trade-offs between multiple, potentially competing objectives. Current multi-objective multi-agent path finding (MO-…