PaperlayerView exact revision on arXiv

Source-linked AI summary

Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search

Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Sven Koenig

arXiv:2103.07116v1cs.AIcs.RO

TL;DR

Pairwise symmetry makes MAPF search difficult because many promising paths for two agents collide in every combination. The paper develops symmetry-specific constraints that detect and resolve these cases in a single branching step. In CBS experiments, the techniques reduced node expansions by up to four orders of magnitude and scaled CBSH by up to thirty times.

  • Problem

    Pairwise symmetry forces optimal MAPF algorithms that plan paths independently to enumerate many combinations of colliding paths, making search difficult.

    Source: §1 · p. 2

  • Method

    The paper develops reasoning techniques that detect several pairwise symmetry types and resolve them with specialized constraints in a single branching step.

    Source: §1 · p. 3

  • Results

    The techniques scaled CBSH by up to thirty times and reduced its node expansion by up to four orders of magnitude.

    Source: §12 · p. 55

  • Takeaways & Limitations

    The symmetry reasoning is instantiated for classic MAPF with optimal CBS, and related applications include other optimal and bounded-suboptimal algorithms and MAPF variants.

    Source: §12 · p. 54

    Corridor-conflict cardinality classification is approximate, so the classification may not match the conflict's exact cardinality.

    Source: §8.3 · p. 36

Abstract

from arXiv · show

Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that asks us to plan collision-free paths for a team of cooperative agents. In this work, we show that one of the reasons why MAPF is so hard to solve is due to a phenomenon called pairwise symmetry, which occurs when two agents have many different paths to their target locations, all of which appear promising, but every combination of them results in a collision. We identify several classes of pairwise symmetries and show that each one arises commonly in practice and can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes for current state-of-the-art (bounded-sub)optimal MAPF algorithms. We propose a variety of reasoning techniques that detect the symmetries efficiently as they arise and resolve them by using specialized constraints to eliminate all permutations of pairwise colliding paths in a single branching step. We implement these ideas in the context of the leading optimal MAPF algorithm CBS and show that the addition of the symmetry reasoning techniques can have a dramatic positive effect on its performance - we report a reduction in the number of node expansions by up to four orders of magnitude and an increase in scalability by up to thirty times. These gains allow us to solve to optimality a variety of challenging MAPF instances previously considered out of reach for CBS.

1. Introduction

Pairwise symmetry makes optimal MAPF search difficult because many promising paths for two agents collide in every combination, forcing algorithms to examine many collision resolutions. The paper develops symmetry-specific constraints and reasoning techniques to resolve several common forms of symmetry in a single branching step.

1. Introduction

  • Pairwise symmetry forces optimal MAPF algorithms to enumerate many combinations of colliding paths, creating an exponential search burden.The issue arises in leading algorithms that plan paths independently before resolving collisions.Source: §1 · p. 2
  • In rectangle symmetry, every pair of shortest paths collides inside the rectangle, while waiting can yield an optimal solution.The number of wait-free path combinations to rule out grows exponentially with the rectangle's size.Source: §1 · pp. 2–3
  • Rectangle, target, and corridor symmetry capture repeated collisions along shortest paths, with stopped agents, and in narrow passages.The paper identifies all three as challenging situations commonly found in popular MAPF domains.Source: §1 · p. 3
  • Symmetry-specific reasoning detects each type and resolves it in one branching step using added constraints, while preserving CBS completeness and optimality.The techniques are demonstrated in CBSH, an advanced CBS variant.Source: §1 · p. 3
  • The paper extends earlier AAAI 2019 and ICAPS 2020 versions with generalized rectangle and corridor reasoning and broader empirical comparisons.It compares against CBSH2 and mutex propagation; the techniques are also applicable to generalized MAPF problems and other optimal and bounded-suboptimal algorithms [14, 15, 23].Source: §1 · p. 3

2. Problem Definition

The paper studies classic MAPF with vertex and swapping conflicts, agents that remain at their targets, and the objective of minimizing total path length. Its examples and experiments use four-neighbor grids, although most symmetry reasoning techniques extend to general graphs.

2. Problem Definition

  • Classic MAPF considers vertex and swapping conflicts, assumes agents stay at their targets, and minimizes the sum of path costs.Agents move or wait at discrete timesteps, and a solution consists of conflict-free paths.Source: §2 · p. 4
  • A vertex conflict occurs when two agents occupy the same vertex at the same timestep; an edge conflict occurs when they traverse an edge in opposite directions.The edge conflict is defined over the transition from timestep t − 1 to t.Source: §2 · p. 4
  • The examples and experiments use four-neighbor grids, while most symmetry reasoning techniques can be applied directly to general graphs.The paper motivates the grid setting by its common use in MAPF and applications such as video games and warehouse robots.Source: §2 · p. 4

3. Background: CBS and Its Variants

CBS combines low-level single-agent pathfinding with high-level conflict resolution in a constraint tree. The paper explains its correctness basis and the CBSH and CBSH2 variants used or compared in the study.

3.1. Vanilla CBS

  • CBS replans individual shortest paths under constraints and uses best-first search over a binary constraint tree to resolve conflicts.Each child adds a constraint for one agent; the affected path is replanned, and a node whose plan is conflict-free is an optimal solution.Source: §3.1 · p. 5

3.1.1. Theoretical Analysis

  • CBS preserves completeness and optimality when branching constraints are mutually disjunctive, so no conflict-free solution is excluded from both children.The theorem applies the principle to two constraint sets used to split a constraint-tree node.Source: §3.1.1 · p. 6

3.2. Advanced Variants of CBS

  • CBSH is the experimental baseline, and CBSH2 is an additional CBS variant included in the comparisons.Source: §3.2 · p. 6

3.2.1. CBSH

  • CBSH prioritizes cardinal conflicts and uses a minimum-vertex-cover heuristic on the cardinal conflict graph to guide high-level search.It uses MDDs to identify cardinal, semi-cardinal, and non-cardinal conflicts.Source: §3.2.1 · pp. 6–7

3.2.2. CBSH2

  • CBSH2 builds a weighted pairwise dependency graph and uses an edge-weighted minimum vertex cover to obtain an admissible high-level heuristic.The resulting h-value is no smaller than the CBSH heuristic; with runtime-reduction techniques, CBSH2 speeds up CBSH on the tested maps.Source: §3.2.2 · pp. 7–8

4. Related Work

The related work covers optimal MAPF algorithms and approaches to eliminating symmetries. The paper situates its techniques among CBS-like search, compilation-based solvers, and methods that modify graphs or propagate pairwise mutex information.

4.1. Optimal MAPF Algorithms

  • Leading optimal algorithms that plan paths independently and resolve conflicts afterward—including CBS variants—also face pairwise symmetries.Joint-state search is an alternative, but the cited leading variants use the independent-planning strategy.Source: §4.1 · p. 8

4.1.1. Search-Based Algorithms that Search in the Joint-State Space

  • Joint-state A* and ICTS search agent combinations, but their state spaces grow exponentially with agent count and their speedups are limited as congestion rises.The reviewed A* and ICTS variants were competitive with vanilla CBS but worse than CBSH with rectangle reasoning in the cited comparison.Source: §4.1.1 · pp. 8–9

4.1.2. Compilation-Based Algorithms

  • Compilation-based methods encode MAPF as ILP, SAT, or CP; BCP, SMT-CBS, and lazy-CBS use more efficient approaches that retain conflict-resolution strategies.BCP uses branch and price, SMT-CBS adds constraints when needed, and lazy-CBS traverses a CBS constraint tree using lazy clause generation.Source: §4.1.2 · pp. 9–10

4.2. Existing Approaches to Eliminating Symmetries

  • Graph decomposition reduces search through preprocessing but preserves completeness rather than optimality; highways can help bounded-suboptimal ECBS but do not guarantee resolution of all corridor conflicts in optimal CBS.Graph decomposition replaces special subgraphs with meta-vertices, while highways make movement against assigned directions more expensive.Source: §4.2 · pp. 10–11
  • Mutex propagation resolves cardinal symmetric conflicts, whereas the paper reports that its handcrafted reasoning outperforms it by covering more conflict types, lowering overhead, and using more effective constraints in some cases.Source: §4.2 · p. 11

5. Rectangle Symmetry

Rectangle symmetries can make CBS expand exponentially many constraint-tree nodes, even for two agents. The section develops whole-path and path-segment reasoning that resolves these conflicts with barrier constraints while preserving completeness and optimality.

5. Rectangle Symmetry

  • Undetected cardinal rectangle conflicts can make CBSH’s constraint tree grow exponentially with rectangle size, even in two-agent instances.Figure 2 shows the conflict and corresponding tree; the text says CBSH can time out if the conflict goes undetected.Source: §5 · p. 11, Figure 2 · p. 12

5.1. Rectangle Reasoning Technique I: for Entire Paths

  • A rectangle conflict groups agents’ shortest paths through a shared area, with cardinal, semi-cardinal, and non-cardinal types distinguished by whether either agent has an optimal bypass.The conflict definition requires Manhattan-optimal paths, movement in the same direction on both axes, and equal distances from cells in the conflicting area to both starts.Source: §5 · p. 12, §5.1 · pp. 13–14

5.1.1. Identifying Rectangle Conflicts

  • The entire-path technique identifies rectangle conflicts from a semi- or non-cardinal vertex conflict, using the conflict and path conditions to establish the rectangle criteria.Cardinal vertex conflicts are excluded because ordinary vertex constraints resolve them in one branching step.Source: §5.1.1 · p. 14

5.1.2. Resolving Rectangle Conflicts

  • Two exit-border barrier constraints give one agent priority in the conflicting area, blocking its shortest paths through the rectangle in a single branching step.The two child constraint-tree nodes add a barrier for one agent or the other, forcing the constrained agent to detour or use a longer path.Source: §5.1.2 · pp. 14–15

5.1.3. Classifying Rectangle Conflicts

  • The technique classifies conflicts by whether adding each agent’s barrier constraint increases that agent’s path length: both, one, or neither yields cardinal, semi-cardinal, or non-cardinal.The classification is determined by comparing the rectangle dimensions with those of each agent’s start-target rectangle.Source: §5.1.3 · p. 15

5.1.4. Theoretical Analysis

  • The two barrier constraints are mutually disjunctive, so using them to split a constraint-tree node preserves CBS completeness and optimality.Theorem 3 states that the entire-path rectangle reasoning technique preserves both guarantees.Source: §5.1.4 · p. 16

5.2. Rectangle Reasoning Technique II: for Path Segments

  • For conflicts between path segments, the technique treats singleton MDD nodes as segment endpoints and reuses the entire-path method, including its conflict classification.It adds start-node conditions to avoid unsafe barriers; the segment starts must be on different rectangle sides and distinct.Source: §5.2 · p. 17, §5.2.1 · p. 18, §5.2.3 · p. 19

5.2.2. Resolving Rectangle Conflicts

  • Segment barriers are restricted to nodes in each agent’s MDD, and the resulting constraints preserve CBS completeness and optimality.The MDD restriction addresses cases where a barrier node is absent from an agent’s shortest-path MDD; Theorem 4 states the guarantee for the segment technique.Source: §5.2.2 · p. 19, §5.2.4 · p. 20

6. Generalized Rectangle Symmetry

Generalized rectangle reasoning addresses conflicts that earlier rectangle techniques miss by identifying same-timestep shared areas where agents must cross, then resolving them with barrier constraints. The technique preserves CBS completeness and optimality, while its empirical benefit depends on map structure.

6. Generalized Rectangle Symmetry

  • A generalized rectangle conflict is a same-timestep shared area that agents must topologically cross, and the technique applies to planar graphs beyond 4-neighbor grids.The examples include conflicts without appropriate singletons and with a nonrectangular conflicting area.Source: §6 · p. 22

6.1. High-Level Idea

  • The high-level test uses the ordering of agents’ solid entrance lines around the shared area; paired barrier constraints give one agent priority and force the other to leave later or detour.Dashed exit-line placement affects conflict type, while holes are acceptable only when each contains entrance lines of at most one agent.Source: §6.1 · pp. 22–24

6.2.1. Step 1: Finding the Generalized Rectangle

  • The algorithm builds a connected directed acyclic graph from shared MDD nodes where each agent reaches each vertex at a unique timestep.It starts at the conflict and reports “Not-Rectangle” if the resulting graph is empty or has only one node.Source: §6.2.1 · p. 25

6.2.2. Step 2: Scanning the Border

  • Border scanning checks whether each agent’s entrance edges lie on opposite sides of the border segment from Rs to Rg, then marks the last-seen entrance nodes as R1 and R2.Remaining entrance edges are retained for the hole check.Source: §6.2.2 · p. 26

6.2.3. Step 3: Checking the Holes

  • The hole check rejects a candidate if any hole has entrance edges from both agents; otherwise, the algorithm proceeds to generate constraints.It checks the hole borders against the remaining entrance edges.Source: §6.2.3 · p. 26

6.2.4. Step 4: Generating the Constraints

  • The method generates a barrier constraint for each agent and rejects the candidate if the constraints do not block both current paths; it classifies conflicts by whether the constraints cut zero, one, or both MDDs.Both blocked means cardinal, one means semi-cardinal, and neither means non-cardinal.Source: §6.2.4 · p. 26, §6.2.5 · pp. 26–27

6.3. Theoretical Analysis

  • The barrier constraints are mutually disjunctive, so using them to split a CT node preserves CBS completeness and optimality.The paper states this result as Theorem 5 for generalized rectangle reasoning.Source: §6.3 · p. 27

6.4. Empirical Evaluation on Rectangle Reasoning

  • On open maps, GR is best; on Random, Room, Maze, and Game2, rectangle reasoning neither improves nor degrades CBSH.On Game1 and City, GR significantly outperforms RM, which significantly outperforms R. The evaluation covers 8 maps, 6 agent counts per map, and 25 instances per setting.Source: §6.4 · pp. 27–29, Figure 8 · p. 28, Table 1 · p. 28

7. Target Symmetry

Target symmetry arises when a moving agent visits another agent’s target after that agent has arrived and remains there. The section introduces length-constraint branching to resolve these conflicts and analyzes its classification, guarantees, and empirical performance.

7. Target Symmetry

  • Target symmetry can cause exponential CT growth: with two copies of the example, expansions grow quadratically, and for m-agent instances they grow exponentially in m.Only one leaf CT node resolves the example conflict; other leaves may be fruitlessly expanded when later conflicts occur.Source: §7 · p. 30

7.1. Identifying Target Conflicts

  • Target conflicts are detected by comparing the conflicting timestep with the agents’ path lengths.Source: §7.1 · p. 30

7.2. Resolving Target Conflicts

  • Branching on a target conflict splits the target agent’s path length into l2 > t and l2 ≤ t, with the latter barring other agents from the target at or after t.The first constraint forces the target agent to finish later; the second can prune a node if the other agent has no alternate path and can require replanning for other agents.Source: §7.2 · pp. 30–31

7.3. Classifying Target Conflicts

  • Target conflicts are classified by the corresponding vertex conflict, but this is approximate because both children of a semi-cardinal conflict can increase in cost.Source: §7.3 · pp. 31–32

7.5. Empirical Evaluation on Target Reasoning

  • Target reasoning speeds up CBSH on all tested maps except Maze, with larger improvements usually on denser maps; Maze is hindered by costly low-level searches for long or nonexistent paths.The authors suggest Safe Interval Path Planning as a possible way to address both issues, leaving it for future work.Source: Figure 10 · p. 32, §7.5 · pp. 32–33

7.4. Theoretical Analysis

  • Resolving target conflicts with length constraints preserves CBS completeness and optimality.Source: §7.4 · p. 32

8. Corridor Symmetry

Corridor symmetry occurs when agents moving in opposite directions conflict inside a narrow passage. The section replaces repeated conflict splitting with range-constraint branching and establishes the method’s guarantees and an approximate conflict classification.

8. Corridor Symmetry

  • As corridor length k increases, CBS expands 2k+1 CT nodes; many wait-location variants remain mutually conflicting, prompting corridor reasoning to resolve conflicts in one branching step.In the illustrated length-3 case, only two of sixteen leaf CT nodes contain optimal solutions.Source: §8 · p. 34

8.1. Identifying Corridor Conflicts

  • Corridor conflicts are detected by checking vertex and edge conflicts and tracing degree-2 vertices to find the corridor endpoints.Source: §8.1 · p. 34

8.2. Resolving Corridor Conflicts

  • For corridors without bypasses, one agent must wait for the other to traverse; with bypasses, the earliest arrival bounds incorporate each agent’s bypass time.The resulting mutually disjunctive range constraints split the CT node; the example resolves the symmetry in one branch.Source: §8.2 · pp. 34–35

8.3. Classifying Corridor Conflicts

  • The classification inherits the corresponding conflict’s cardinality, but is approximate: a non-cardinal corridor conflict can yield two children whose costs both exceed the parent’s.Source: §8.3 · p. 36

8.4. Theoretical Analysis

  • Range constraints are mutually disjunctive, so resolving corridor conflicts with them preserves CBS completeness and optimality.The guarantee depends on the chosen exit-endpoint constraints; entry-endpoint constraints might not be mutually disjunctive and could lose completeness guarantees.Source: §8.4 · p. 36

9. Generalized Corridor Symmetries

The section generalizes corridor reasoning to pseudo-corridor conflicts and cases where starts or targets lie inside corridors. The resulting constraint sets preserve CBS completeness and optimality, and generalized corridor reasoning performs best among the tested corridor techniques.

9.1. Pseudo-Corridor Conflicts

  • Pseudo-corridor conflicts behave like length-1 corridor conflicts in non-corridor regions; the method reuses corridor range constraints and preserves CBS completeness and optimality.MDD checks filter candidate conflicts before the more costly endpoint-time calculations; the method focuses on cardinal cases.Source: §9.1 · p. 38

9.2. Corridor Conflicts with Start Vertices inside the Corridor

  • Allowing start vertices inside the corridor lets the modified method detect and resolve conflicts that the earlier method could not resolve in one branch.The modified technique preserves CBS completeness and optimality.Source: §9.2 · pp. 39–40

9.3. Corridor-Target Conflicts

  • Corridor-target conflicts include cases with one or both targets inside the corridor, and detection uses MustCross to determine whether agents have to cross.Unlike the earlier condition, agents need not move in opposite directions when starts or targets are inside the corridor.Source: §9.3 · p. 41, §9.3.1 · pp. 41–42

9.3.2. Resolving Corridor-Target Conflicts

  • Resolving corridor-target conflicts combines corridor and target reasoning, with separate constraint sets for cases where one or both targets lie inside the corridor.Source: §9.3.2 · pp. 42–43

9.3.3. Classifying Corridor-Target Conflicts

  • Corridor-target conflict classification reuses the earlier method, while its constraint sets are mutually disjunctive and preserve CBS completeness and optimality.The generalized method’s constraint sets preserve those guarantees across all covered corridor-conflict types.Source: §9.3.3 · p. 43, §9.3.4 · p. 43, §9.4 · p. 44

9. Generalized Corridor Symmetries

  • Generalized corridor reasoning covers standard corridors, including internal start vertices, corridor-target conflicts, and pseudo-corridors.The prior method has limitations in these special cases, which the section addresses before presenting a unified framework.Source: §9 · p. 37, §9.4 · p. 44

9.5. Empirical Evaluation on Generalized Corridor Reasoning

  • On maps without corridors, corridor reasoning neither speeds up nor slows down CBSH; on maps with many corridors, all techniques help, and generalized corridor reasoning is always best.Pseudo-corridor reasoning helps on some maps with varied obstacles where basic and start/target corridor techniques do not improve performance.Source: §9.5 · pp. 44–45, Figure 16 · p. 45

10. Symmetry Reasoning Framework

The framework combines pairwise symmetry reasoning techniques and selects conflicts to resolve within CBSH. In evaluation, the combined RTC configuration improves performance and scalability over CBSH without these techniques.

10.1. Framework

  • For each CT-node vertex or edge conflict, the framework checks generalized corridor reasoning first, then target reasoning, then rectangle reasoning, and otherwise uses standard CBS splitting.Conflict selection prioritizes target, corridor, rectangle, then vertex/edge conflicts by expected child-node cost increases; conflicts are also prioritized by cardinality.Source: §10 · pp. 45–46, §10.1 · pp. 46–47

10.2. Empirical Evaluation

  • RTC is always the best of the tested configurations for runtime and success rates, with combined success-rate gains exceeding those of individual techniques on several maps.The authors attribute the larger gains to instances containing multiple symmetry classes, where standard splitting for only one class can leave unacceptable runtimes.Source: §10.2 · p. 47, Figure 17 · p. 48, Figure 18 · p. 48
  • 13 times on Game1 and 30 times on City: RTC improves CBSH scalability on all tested maps except Maze.Scalability is measured as the largest agent count solved with 100% success; Table 3 reports this comparison.Source: Table 3 · p. 47, §10.2 · p. 48
  • Up to four orders of magnitude fewer CT nodes: RTC beats None on 782 of 890 instances solved by at least one algorithm, while performing worse on 24.Figure 19 compares expanded CT nodes; its distribution also reports that RTC solves 418 instances that None does not, while None solves only 3 that RTC does not.Source: §10.2 · pp. 48–49, Figure 19 · p. 49
  • Rectangle reasoning's runtime overhead is always below 7%, while corridor reasoning exceeds 10% on Random and Game2; overall, the authors report that the overhead pays off.Table 4 reports the runtime shares for rectangle and corridor reasoning; target-reasoning overhead is negligible and omitted.Source: §10.2 · p. 49, Table 4 · p. 49
  • Rectangle, target, and corridor conflicts together account for approximately 70% of expansion conflicts on many maps, with their frequency varying by map structure.Rectangle conflicts are more frequent on maps with open space, while corridor conflicts are detected on all maps and are frequent on maps with obstacles.Source: §10.2 · p. 50, Table 5 · p. 50
  • On two-agent instances, RTC solves up to 99% by expanding one CT node and solves at least 81% in the worst case.Except on Maze, fewer than 0.5% of instances require more than 10 CT nodes; on Maze, the share is below 1.5%.Source: §10.2 · p. 51, Table 6 · p. 51

11. Empirical Comparison with Existing Algorithms

Across the tested instances, RTC outperforms mutex propagation, and combining them adds negligible improvement over RTC alone. Adding RTC to CBSH2 improves its runtime and CT-node performance, with CBSH2 with RTC performing best among the compared variants.

11.1. Comparison with Mutex Propagation

  • The comparison tested mutex propagation, RTC, and both combinations, applying the first technique before the second when both were used.M+RTC tries mutex propagation first; RTC+M tries RTC first.Source: §11.1 · p. 52
  • RTC alone always outperformed mutex propagation alone; combining them did not outperform RTC alone on the tested instances.Mutex propagation handles cardinal symmetric conflicts but not semi- or non-cardinal ones, and has greater runtime overhead; RTC+M’s improvement over RTC was negligible.Source: §11.1 · pp. 52–53, Figure 20 · p. 52

11.2. Comparison with CBSH2

  • CBSH2 with RTC performed best in runtime comparisons, while RTC alone also outperformed CBSH2 in most cases.The authors attribute RTC’s advantage over CBSH2 to directly resolving symmetries with symmetry-breaking constraints rather than relying on heuristics; CBSH2 with RTC uses both approaches.Source: Figure 21 · p. 53, §11.2 · p. 54
  • RTC reduced CBSH2’s CT-tree size by up to three orders of magnitude; among instances solved by at least one algorithm, it beat CBSH2 on 676 of 961 and performed worse on 44.Figure 22 reports that 239 of 1,200 instances were solved by neither algorithm, 241 by CBSH2 with RTC only, and 6 by CBSH2 only.Source: Figure 22 · p. 53, §11.2 · p. 54

12. Summary and Future Work

The paper identifies pairwise symmetries as a source of difficulty for optimal MAPF and develops reasoning techniques instantiated for CBS. The techniques improve CBSH’s performance, while extensions to other algorithms and MAPF variants have also been explored.

12. Summary and Future Work

  • The paper provides CBS instantiations for classic MAPF, while related work applies these ideas to BCP, EECBS, and k-robust MAPF.The paper states that the symmetry issues must eventually be resolved by every optimal MAPF algorithm, although encodings are algorithm-specific.Source: §12 · p. 54
  • Rectangle conflicts arise when two agents must cross paths and have many equivalent ways to do so; generalized rectangle reasoning applies to planar graphs.The paper describes planar graphs as representing almost all real-world circumstances for MAPF in 2D scenarios.Source: §12 · p. 54
  • The reasoning techniques scaled up CBSH by up to thirty times and reduced node expansions by up to four orders of magnitude.They significantly outperformed mutex propagation and significantly improved CBSH2.Source: §12 · p. 55
  • Generalized corridor and target reasoning use spatial and temporal reasoning to avoid symmetries caused by multiple waiting actions, and apply to any graphs.The paper identifies these techniques as relevant to warehouse-robot routing.Source: §12 · p. 55
  • Some pairwise symmetries remain undetected, and congested settings can involve complex interactions among more than two agents.The paper also points to additional symmetric conflicts in k-robust MAPF, large-agent MAPF, and settings with agents of different speeds.Source: §12 · p. 55

Appendix A. Proof for Rectangle Reasoning Techniques

The appendix establishes geometric properties used by rectangle reasoning: paths reaching designated exit borders must also pass through corresponding entrance borders. It extends this property to paths subject to barrier constraints.

Appendix A. Proof for Rectangle Reasoning Techniques

  • For rectangle conflicts found by technique I, paths reaching each agent’s designated exit border must also visit the corresponding entrance border.The proof uses the geometry of the rectangle and the Manhattan-optimality of the relevant path segments.Source: Appendix A · pp. 60–61
  • For technique II, paths visiting nodes prohibited by the barrier constraints must also pass through the corresponding entrance border.The proof reduces the claim to the argument for Property 1 after replacing the earlier coordinate equations with Equation (7).Source: Appendix A · pp. 61–62

Appendix B. Proof for the Generalized Rectangle Reasoning Technique

The appendix proves that paths entering the generalized rectangle pass through specified entrance edges. It uses those edges and the geometry of the conflicting area to establish that violating paired barrier constraints yields a conflict.

Appendix B. Proof for the Generalized Rectangle Reasoning Technique

  • Any path visiting a node in the generalized rectangle must visit an entrance edge, and any such path must visit an entrance edge in the subset Ep_i.The proof of the subset claim uses the decomposition of entrance edges into Ep_i and Eh_i and shows paths through Eh_i also pass through Ep_i.Source: Appendix B · p. 62
  • When one path violates B(a1, R1, Rg) and the other violates B(a2, R2, Rg), the paths must conflict within the conflicting area G.The proof uses the entrance-edge locations on opposite border segments to show the paths cross at a vertex in V′.Source: Appendix B · pp. 62–63

Appendix C. Proof for the Corridor Reasoning Technique

The corridor property states that when each agent violates its specified constraint, their paths must conflict inside the corridor. The proof establishes that both paths traverse the corridor and reach its endpoints in an order that forces a conflict.

Appendix C. Proof for the Corridor Reasoning Technique

  • Violating the paired constraints guarantees one or more vertex or edge conflicts inside the corridor.The property applies to all combinations of paths satisfying those violations.Source: Appendix C · p. 63
  • Each violating path must traverse the corridor because it reaches an endpoint earlier than it could without using the corridor.The proof applies this reasoning to both agents’ paths.Source: Appendix C · p. 63
  • The paths reach the opposite endpoints in crossing order, forcing a conflict between them inside the corridor.One path visits the other’s endpoint no later than the second agent’s earliest arrival there; the proof applies the corresponding ordering in reverse as well.Source: Appendix C · pp. 63–64

Appendix D. Proof for the Corridor-Target Reasoning Technique

The corridor-target property states that violating the paired constraint sets guarantees a conflict inside the corridor. Its proof treats cases according to where the agents’ targets lie and shows that their required routes or entry timing force that conflict.

Appendix D. Proof for the Corridor-Target Reasoning Technique

  • Violating constraint sets C1 and C2 guarantees one or more vertex or edge conflicts inside the corridor.The property applies to all combinations of paths for the corridor-target conflict.Source: Appendix D · p. 64
  • The proof excludes the case where a1’s path simultaneously violates the incompatible length constraints l1 > l and l1 ≤ l.It therefore considers the relevant case where a1 violates l1 > l and a2 violates its stated constraint.Source: Appendix D · p. 64
  • When agent a2’s target is outside the corridor, its constrained path must traverse the corridor, while agent a1’s path must enter and remain there to reach its target.The proof compares the entry time of a1’s path with a2’s path to establish a conflict inside the corridor.Source: Appendix D · p. 64
  • When both targets are inside the corridor, a2’s constrained path reaches its target via the other agent’s target or endpoint, or a1 enters early enough to force a conflict.The proof considers both possible corridor-entry endpoints for a1.Source: Appendix D · p. 65

Related papers

Loading 2103.07116v1…