Multi-Group Pipe Routing under Permanent Geometric Occupancy: Problem, Benchmark, and Classical Baselines

1 Introduction and Motivation

• Different valve groups must remain geometrically separated across design poses, while pipes within a group may share trunks or branch.This motivates automatic routing because manual CAD routing does not scale in the cluttered, bounded 3D domain.Source: §1 · p. 1
• The paper formalizes multi-group pipe routing under permanent geometric occupancy, using dual-witness clearance conflicts and topology-driven multi-terminal groups.This setting is motivated by additive-manufactured valve layouts.Source: §1 · pp. 1–2
• The benchmark combines two corridor generators with two obstacle painters and easy, middle, and hard schedules, with known-feasible witnesses.It is a constructive 3D suite for the routing problem.Source: §1 · p. 2
• CBS, PBS, and priority planning are adapted to the setting and evaluated by fixed-budget success rates across 36 batches of 100 instances.The paper does not claim a new optimal high-level algorithm or industrial CAD parity.Source: §1 · p. 2

2 From Valve Design to a Computational Problem

• Each routed pipe permanently occupies a tubular neighborhood, and cross-group interference is forbidden, unlike MAPF’s pass-and-release occupancy.Within-group sharing or branching is allowed through a topology plan.Source: §2 · pp. 2–3
• The discretized domain models pipes as capsule neighborhoods and static obstacles as spheres, capsules, or boxes; a query point is free only when clearance is at least the pipe radius.Equivalently, the open ball at that point must not intersect forbidden geometry.Source: §2 · p. 3
• Different-group pipes conflict when their tubular neighborhoods violate clearance, represented by two witness points and a penetration deficit; same-group contacts are not conflicts by default.The setting differs from classical MAPF in occupancy, conflict semantics, and agent structure.Source: §2 · p. 3
• A feasible solution routes every task clear of static obstacles and committed geometry from other groups; the primary objective is success within a wall-clock budget.Path cost relative to a constructive witness is secondary, while manufacturing criteria are left for future work.Source: §2 · p. 3

3 Baseline Planner Stack

• A Euclidean pure MST maps each group’s terminals to tree-manifold tasks, while a clearance grid and 26-connected Manhattan A⋆ search route each task.Committed other-group pipes and CBS negative constraints become obstacle chains; PP commits paths as hard occupancy, while CBS/PBS retain paths in the current leaf solution.Source: §3 · p. 4
• After routing all groups in a leaf, the stack detects cross-group geometric hits as dual witnesses with a deficit and ranks conflicts using a near-terminal heuristic.Same-group contacts are ignored.Source: §3 · p. 4

3.1 High-level controllers

• CBS adds opposing negative witness constraints for a selected conflict and replans only the affected group.Its constraint-tree leaves store group paths and negative witness spheres.Source: §3.1 · p. 4
• PBS adds a priority edge for a conflict, then replans the lower-priority group around higher-priority paths.The reported search expands the priority DAG depth-first.Source: §3.1 · p. 4
• Priority planning searches a total order, treating earlier groups’ paths as hard obstacles and repairing the sequence after failure.It uses order search rather than dual-witness constraint branching.Source: §3.1 · p. 4

4 Benchmark Construction

• Each instance pairs an environment and groups with face terminals and uniform radius with a conflict-free witness that certifies generator-level feasibility.Solvers do not receive the witness as a hint; it is used for validation and reference length, not as an optimality bound.Source: §4 · p. 4
• The generation pipeline grows witness corridors, paints obstacles outside their thickened clearance, then emits the grid, obstacles, terminals, and witness.This yields known-feasible clutter without coupling the suite to a solver under test.Source: §4 · p. 4
• Two corridor generators crossed with two obstacle families produce four datasets, each with easy, middle, and hard levels.The shared domain is 323 and the pipe radius is 0.5.Source: §4 · p. 4, Table 2 · p. 5
• AxisRay grows axis-aligned polyline trees using line-of-sight scans, whereas PlaneSlice grows on axis-aligned planes using planar A⋆ without a 3D fallback.Both generators produce multi-terminal trees, with inter-group corridors blocking later growth.Source: §4 · p. 5
• PillarField places large boxes toward a target obstacle density, while CorridorRack meshes the complement around witnesses dilated by two Chebyshev steps.The reported PillarField target density is 0.4.Source: §4 · p. 5

5 Evaluation Protocol

• Runs fix topology to pure MST and low-level search to A⋆ with 26-connected moves and Manhattan distance.Solvers receive the environment and group tasks without the constructive witness.Source: §5 · p. 5
• Success is the primary metric: the fraction of instances solved within the level-specific wall-clock budget.The protocol also reports failure reasons and success-versus-time curves.Source: §5 · p. 5
• On successful instances, cost(sol)/cost(W) is a descriptive quality signal, not an optimality gap.Algorithm cost comparisons use the common success set to limit selection bias.Source: §5 · p. 5

6 Experiments

• Experiments compare CBS, PBS, and PP on four datasets, with 100 instances per cell and 30/60/120-second easy/middle/hard budgets.Shared settings use pure MST topology and A⋆ with 26-connected moves and Manhattan distance.Source: §6 · pp. 5–6

6.1 Success rate

• PlaneSlice hard success is 56%/66% for CBS, 7%/11% for PBS, and 0% for PP; AxisRay hard remains near-perfect for CBS.On PlaneSlice, both obstacle painters preserve the ranking CBS ≫ PBS ≫ PP.Source: Table 3 · p. 6, §6.1 · p. 6

6.3 Failures and path cost

• On PlaneSlice hard, CBS failures are mostly timeouts; PP also exhausts order neighbourhoods, while AxisRay-hard PBS/PP failures are mostly no-solution outcomes.The reported failure patterns differ by dataset and solver.Source: §6.3 · p. 6

6.2 Runtime and Success@T

• PlaneSlice-hard CBS median success time is 46–61 seconds; CBS successes accumulate through 100 seconds while PBS plateaus near 7–9% and PP stays at 0%.Many PlaneSlice-hard failures are timeouts, indicating the budget is binding.Source: §6.2 · p. 6, Table 4 · p. 7

6.3 Failures and path cost

• Successful runs typically have median cost ratios below 1, often about 0.53–0.76 on hard non-trivial cells; this is not an optimality gap.The constructive witnesses are feasible but loose.Source: §6.3 · p. 7

7 Related Work

• Grid MAPF uses CBS, PBS, and priority planning for temporary cell occupancy and timestep conflicts; this work reuses those control patterns for permanent geometric occupancy and multi-terminal groups.The target is design-time 3D layout, not concurrent motion on MovingAI-style maps [4].Source: §7 · p. 7
• Belov et al. adapt CBS and PBS to industrial pipe routing, but do not provide a public multi-group benchmark with feasibility witnesses or compare priority planning systematically.This work extends that line to grouped multi-terminal topology and a four-dataset suite.Source: §7 · p. 7
• Automatic pipe-routing literature includes sequential CAD, mixed-integer, and sampling methods; controlled 3D generators and MAPF-style branching are uncommon there.The paper frames its contribution as a benchmark with a fixed protocol and baseline success rates, rather than a single-application optimiser.Source: §7 · p. 7

8 Discussion

• On PlaneSlice hard, CBS reaches 56–66% success, PBS falls to single digits, and PP solves none of 200 instances; both obstacle families preserve this ranking.The authors suggest corridor layout and group count, rather than a particular clutter model, drive this stress test.Source: §8 · p. 8
• The evaluated instances are synthetic 323 grids with uniform radius, not B-rep valve bodies or multi-radius mixtures.The study does not evaluate manufacturing criteria such as bend limits or supportability.Source: §8 · p. 8
• CBS, PBS, and PP are baselines under one fixed protocol, not an exhaustive comparison with commercial CAD routers or continuous shape optimisers.Post-layout smoothing is left as orthogonal follow-on work.Source: §8 · p. 8

• The paper formalizes multi-group 3D pipe routing under permanent geometric occupancy.Source: §9 · p. 8
• A constructive benchmark comprises four datasets with controlled difficulty and N=100 instances per cell.Source: §9 · p. 8
• Fixed-budget success is measured for CBS, PBS, and priority planning.The suite and runs are intended as a reproducible starting point for stronger geometric multi-group planners and manufacturing-aware refinement.Source: §9 · p. 8

A Generator Details

• The appendix documents constructive generators for reproducibility; the main text needs only their high-level behavior.Source: A Generator Details · p. 9

A.1 AxisRay

• AxisRay uses line-of-sight scans with rollback after failed seed or attachment attempts, enforcing path-clearance, axis-change, and branch-spacing rules.Source: §A.1 · p. 9

A.2 PlaneSlice

• PlaneSlice searches only the active axis plane in 2D, with no full-3D A⋆ fallback; same-group off-plane corridors are ignored and other groups on-plane are obstacles.Source: §A.2 · p. 9

A.3 PillarField and CorridorRack

• PlaneSlice takes a domain, radius, subdomain, plane gap, and terminal targets, and returns per-group corridors or failure.Source: §A.3 · p. 10
• PlaneSlice grows groups in round-robin order, sampling valid axis planes and placing face-terminal pairs, with later planes chosen from existing group cells.Source: §A.3 · p. 10
• PillarField blocks thickened witness cells, expands candidate AABBs, rejects boxes that are too thin, and commits the largest-volume candidate as a static obstacle.Source: §A.3 · p. 10
• CorridorRack constructs obstacles from the complement of dilated witnesses, merging obstacle cells into large AABBs.Source: §A.3 · p. 10