The problem is to find collision-free plans for multiple agents from designated starts to designated goals. Unlike classical grid MAPF, movement is not restricted to a fixed neighborhood such as the four cardinal directions: an agent can move between any two visible vertices whose connecting segment does not collide with obstacles. Agents are modeled as disks, may wait for arbitrary continuous durations, and move at unit speed, so the duration of a move equals the distance between its endpoints. The main objective is to minimize the sum of the agents' goal-arrival times.
The paper presents AA-CCBS, described as the first optimal any-angle MAPF algorithm. Its high-level search is based on Continuous Conflict-based Search, while its low-level planner is the optimal any-angle Safe Interval Path Planning variant TO-AA-SIPP. The paper adapts two classical MAPF techniques, Disjoint Splitting and Multi-Constraints, to the any-angle setting in order to control the large branching factor. It also introduces three ways of implementing Multi-Constraints and provides a bounded-suboptimal version that allows runtime to be exchanged for solution cost.
CCBS plans each agent separately, detects conflicts over continuous time, and resolves a conflict by adding a constraint and replanning the affected agent. AA-CCBS uses TO-AA-SIPP for low-level search, so the individual planner considers visible straight-line moves, obstacle clearance, and safe time intervals under constraints induced by other agents. Multi-Constraints adds several constraints when resolving one conflict, which can prune more of the high-level search tree than adding only one constraint. Disjoint Splitting separates conflict resolution into disjoint constraint branches and is adapted here to the continuous any-angle setting. For bounded-suboptimal search, the high-level Best-First Search is replaced by Focal Search, limiting solution cost to a specified factor above the optimum.
The evaluation uses a C++ implementation and five MovingAI benchmark maps: empty-16-16, random-32-32-20, maze-32-32-4, den321d, and warehouse-10-20-10-2-2. Each map supplies 25 scenarios; each scenario starts with two agents, and the number of agents is increased while the solver can find a solution within the time limit. The compared versions are vanilla AA-CCBS, three Multi-Constraints variants, Disjoint Splitting alone, and Disjoint Splitting combined with the third Multi-Constraints variant. Reported measures include the number of instances solved within 300 seconds, the number solved under different time limits, and the number of high-level iterations. The bounded-suboptimal evaluation uses the three stronger configurations on the same problem instances and examines solution-cost overhead relative to an optimal solution.
The reported results show that the first and second Multi-Constraints variants do not significantly improve over vanilla AA-CCBS, whereas the third variant, Disjoint Splitting, and their combination provide substantial benefits. The third Multi-Constraints variant is best under very short time limits, while Disjoint Splitting and the combined method become better under longer limits, suggesting that different techniques fit different instance difficulties and available runtimes. The third variant tends to reduce high-level iterations on easier instances, whereas Disjoint Splitting is more useful on harder ones. Allowing a small amount of suboptimality enables many more instances to be solved, but the excerpt does not provide complete cost data for each suboptimality factor.
Classical MAPF usually restricts agents to transitions in a predefined sparse graph and often assigns one unit of time to every move. Conflict-Based Search is a central optimal MAPF framework, and CCBS extends the conflict-based idea to continuous timelines and actions with different durations. Optimal single-agent any-angle planners include Anya and TO-AA-SIPP, while earlier any-angle MAPF approaches mentioned in the paper did not provide optimality guarantees. The paper therefore combines continuous-time multi-agent conflict resolution with an optimal any-angle low-level planner.
The locations are vertices in a metric space, such as the centers of grid cells, with one start and one goal for each agent. An agent may wait at a vertex for an arbitrary duration and may move between two vertices only when a line-of-sight test confirms that the straight segment does not collide with obstacles. A pair of plans conflicts if, at some time, the distance between the two disk-shaped agents is smaller than the sum of their radii. The task is to produce pairwise collision-free plans and minimize the sum of the times at which all agents reach their goals.
The high-level AA-CCBS search reasons about continuous-time conflicts rather than isolated discrete time steps, and the low-level planner is TO-AA-SIPP. Waiting can be represented implicitly by a gap between the end of one move and the start of the next move. Moves use unit speed and assume instantaneous starting and stopping, so their durations are the distances between their endpoints. The paper states that the framework can be adapted to other objectives such as makespan, but the supplied evaluation is centered on sum of costs.
The study evaluates five MovingAI maps, with 25 scenarios per map, and progressively increases the number of agents. A scenario is abandoned for that solver when no solution is found within 300 seconds, after which the next scenario is processed. The comparison includes vanilla AA-CCBS, three Multi-Constraints choices, Disjoint Splitting, and the combination of Disjoint Splitting with the third Multi-Constraints choice. The bounded-suboptimal study evaluates Disjoint Splitting, the third Multi-Constraints choice, and their combination on the same instances.
The abstract reports that the proposed techniques solve over 30 percent more problems than the vanilla combination of CCBS and TO-AA-SIPP. In the time-limit analysis, the third Multi-Constraints variant performs best between 0.01 and 0.1 seconds, while Disjoint Splitting-based variants perform better at higher limits. Among instances solved by all compared methods, the third Multi-Constraints variant requires fewer high-level iterations in nearly half of the cases, especially among easier cases. The paper also reports that permitting a small bounded-suboptimality factor allows many more problems to be solved.
AA-CCBS provides a CCBS-based framework with optimality guarantees for any-angle MAPF. Disjoint Splitting and Multi-Constraints are shown to be useful ways to reduce the search burden created by the large number of any-angle moves. The bounded-suboptimal variant provides a controlled trade-off between solution cost and runtime. The evidence supports selecting different enhancements according to instance difficulty and the available time.
Any-angle movement creates a very large branching factor, and the straightforward AA-CCBS combination can struggle even on simple instances. The paper explicitly leaves construction of a bounded-suboptimal low-level search outside its scope. The experiments cover the specified five maps, scenarios, agent-growth procedure, and time limits, so the excerpt does not establish performance in other environments or with richer robot dynamics. Future work includes more sophisticated ways to form Multi-Constraints, deciding which action sets to consider at each step, and adapting incremental search to the any-angle low-level planner.
Any-angle motion can represent shorter paths than fixed-neighborhood grid motion, but it also makes multi-agent search substantially harder. This work is important because it connects continuous-time collision reasoning and optimal single-agent any-angle planning in an optimal multi-agent framework. Its bounded-suboptimal extension is relevant when an exact optimum is too expensive but a controlled cost guarantee is still desirable. The paper therefore addresses both an optimal formulation and the practical scaling of its search.
This survey is suited to researchers working on any-angle MAPF, CCBS, SIPP, CBS extensions, continuous-time collision handling, and bounded-suboptimal search. It is especially relevant for readers comparing conflict-splitting and multi-constraint strategies for reducing high-level search effort. Readers interested in heterogeneous agents, different speeds, or kinodynamic constraints can use the related-work discussion as context, but the supplied excerpt does not establish the performance of those extensions.