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

Discrete multi-group pipe routers place channels on a grid or coarse graph. The resulting centerlines are topologically feasible but typically contain many axis-aligned corners. For permanently occupied fluid tubes---as in additively manufactured hydraulic manifolds---those corners are undesirable: they degrade geometric fairness and, in practice, flow quality. This technical report studies the downstream geometric stage that starts from a fixed routing topology and a feasible coarse layout, and refines tubular centerlines under permanent clearance. Unlike classical robotic path smoothing, which usually fair one temporary open trajectory, our setting is a branched manifold with declared terminal usages, finite tube radii, and static cross-group occupancy. We formalize the refinement problem, highlight the multi-usage junction conflict that a single shared branch point cannot resolve, and outline a hybrid trunk-share / junction-split parameterization with soft geometric costs and hard clearance acceptance. On a multi-group suite ($8$ groups $\times$ $8$ terminals, $r{=}2$) with capsule clearance, the refine reaches full hard-accept success, $κr\lesssim 1$, and about a $95\%$ relative drop in the soft objective. Physics-based pressure-drop optimization is intentionally deferred to a later PDE stage; here the objective remains geometric.

Anonymous Multi-Agent Path Finding (AMAPF) admits polynomial-time network-flow algorithms for several objectives, including makespan, total distance, and sum-of-costs (SoC) when agents disappear upon reaching goals. We show that standard goal-staying AMAPF is fundamentally different. We first formulate SoC minimization by augmenting the standard time-expanded flow model with goal-settlement constraints and show that the resulting linear programming relaxation is non-integral. We then prove that minimizing SoC in goal-staying AMAPF is NP-hard via a reduction from 3-SAT. Together with the polynomial-time result for the disappearing variant, this establishes a sharp complexity boundary determined by whether completed agents remain at their goals.

Many research fields share a common structure: a set of agents, each pursuing its own goal, whose actions must be coordinated so that no two of them conflict. Multi-Agent Path Finding (MAPF) is a concrete instance of this structure, with applications from warehouses to road traffic and airports. Much of MAPF research assumes discrete time, circular agents sharing one spatial graph, a single goal per agent, and that an agent must remain at its goal once reached, precluding heterogeneous fleets, non-geometric conflicts, task sequences, and agents that move on after completing them. We generalise the MAPF formulation to lift these assumptions, and present Anytime-Optimal Continuous-time Conflict-Based Search (AOC-CBS), an exact and solution-complete solver for it. AOC-CBS guarantees the eventual return of an optimal solution, while reporting an incumbent with a known optimality gap upper bound throughout its runtime; it is configurable with a portfolio of repair functions, one of which we introduce (Tier-Prioritized Safe Interval Path Planning), and can exploit multiple processor cores. We demonstrate AOC-CBS on a mixed fleet of non-convex agents moving along smooth, kinodynamically feasible trajectories. Preliminary experiments against the exact solver OC-CBS, on well-known benchmarks and roadmaps we sample from them, show AOC-CBS is comparable at finding optimal solutions while extending scalability from the tens to the hundreds of agents when a bounded optimality gap is accepted.