CS Paper Radar

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

Deng Quan

cs.RO ·submitted 2026-08-27 10:26 UTC · v1
benchmark

Abstract

Additive manufacturing (AM) enables compact hydraulic components whose internal fluid channels can follow free-form 3D paths rather than conventionally drilled holes. A representative case is multi-group channel layout in rotary direct-drive servo valves: once a channel is placed it permanently occupies volume, so later channels must clear earlier geometry--unlike classical multi-agent pathfinding (MAPF), where agents free space after moving. We study this setting as multi-group pipe routing under permanent geometric occupancy. Our contributions are a problem formalization with geometric dual-witness conflicts, a constructive 3D benchmark (two corridor generators x two obstacle painters, controlled difficulty, feasibility witnesses), and baseline results for CBS, PBS, and priority planning adapted to this coupling. We evaluate by success rate under a fixed time budget. PlaneSlice hard instances clearly rank CBS above PBS and PP, while easier cells validate the pipeline. The goal is a reproducible problem definition, suite, and classical baselines--not a new optimal MAPF algorithm.

Closest papers

Nearest neighbours by meaning across the whole index.

Topology-Preserving Multi-Usage Pipe Centerline Refinement under Permanent Tubular Occupancy

cs.RO ·2026-10-14 ·Deng Quan
similarity 0.76
Abstract

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.

0.11

A GPU-Resident Pipeline for Multi-Robot 3D Inspection with Limited Perception

cs.RO cs.MA ·2026-10-19 ·Kryštof Pšenička, Stefan Edelkamp
theorycode/data similarity 0.59
Abstract

We present a complete, GPU-resident pipeline for multi-robot 3D inspection of underwater structures. Given a triangle mesh and a fleet of $K$ robots, each carrying a short-range, limited field-of-view camera, the pipeline computes 6-DOF trajectories that jointly cover a target fraction of the surface while minimizing a linearly interpolated makespan/total-cost objective. The joint problem is NP-hard, so we decompose it into five core stages - candidate viewpoint generation, visibility computation, set cover, min-max vehicle routing solved as a mixed integer program (MIP) with lifted Miller-Tucker-Zemlin subtour elimination, and priority-based multi-agent path finding with continuous-time inter-robot conflict checking - flanked by mesh loading and surface sampling as preprocessing and by trajectory smoothing as postprocessing. Our contributions are: an end-to-end GPU-accelerated integration of the five stages, with its kernel design documented; a GPU batch adaptation of Lien's $\varepsilon$-visibility with four custom CUDA kernels; a $β$-aware per-vehicle tour upper bound derived from the interpolated objective, supplementing the Desrochers-Laporte coefficient lift with forbidden-pair cuts; a 4D space-time extension of Zhou and Zeng's GPU parallel-frontier A*; and an experimental evaluation on 14 meshes (up to $7.2$M faces) that ablates the routing cuts and the parallel-frontier search, audits collision freedom and waypoint attainment \emph{after} trajectory smoothing, and measures the end-to-end gap against analytical and LP-relaxation lower bounds. Code and raw results are publicly available.

0.21

Solving Multi-Agent Sokoban via LaCAM

cs.MA ·2026-09-30 ·Keisuke Okumura
benchmark similarity 0.59
Abstract

Sokoban, a puzzle game in which an agent pushes boxes onto unlabelled target locations in a grid world, is a long-standing benchmark planning problem. While it is easy to see the connection to practical applications such as warehouse logistics with autonomous forklifts, its multi-agent counterpart has remained underdeveloped. This is because Multi-Agent Sokoban is substantially more difficult due to factors specific to multi-agent planning, such as the rapidly growing branching factor as the number of agents grows and the need to handle integrated task assignment and collision-free pathfinding. In this paper, we show that a scalable planner for Multi-Agent Sokoban can be designed by leveraging recent advances in multi-agent pathfinding (MAPF). Specifically, our Sokoban-LaCAM efficiently solves instances involving tens of agents and boxes while preserving both completeness and eventual optimality guarantees. This provides evidence that MAPF can serve as a powerful primitive for solving broader collective automation problems.

0.17

AssemblyGrid v1: A Benchmark for Multi-Robot Production with Temporary Coalitions, Local Information, and Geometric Constraints

cs.RO cs.AI ·2026-09-13 ·Fouad Bahrpeyma, David Heik, Dirk Reichelt
benchmarkcode/data similarity 0.58
Abstract · 11 figures and 23 tables, including appendices with the formal benchmark specification, evaluation protocol, conformance requirements, and e…

Flexible robotic production requires joint decisions on process progression, material routing, resource assignment, temporary cooperation, and simultaneous execution, since each decision can affect the feasibility of the others. The challenge is greater under decentralized control, where each robot acts from bounded local information while system progress depends on collective decisions, shared resources, material state, and workspace compatibility. These properties closely match cooperative multi-agent decision making under partial observability and resource contention. This paper introduces AssemblyGrid v1, a reproducible benchmark for repeated multi-robot production that combines explicit process progression, decentralized observations, material transfer, temporary multi-robot coalitions, productive concurrency, and geometry-dependent feasibility within one task-level formulation. The benchmark includes Flow, Coalition, and Concurrency workload families, each with three scenario levels. Task success and evaluation measures are defined independently of learning reward and solution method, allowing learning-based and non-learning methods to address the same production problem. AssemblyGrid v1 is evaluated through executable conformance checks, mechanism studies, and algorithmic experiments using a privileged centralized reference, structured decentralized controllers, and MARL methods including IPPO, MAPPO, and QMIX. Results demonstrate productive execution under centralized and decentralized control. The MARL experiments further show that decentralized policies can learn effective production behavior from local observations and actions, supporting AssemblyGrid as a controlled benchmark for studying cooperative decision making in flexible robotic production.

0.32

Optimization-Based Path Planning for Industrial Manipulators: Experimental Validation in Additive Manufacturing

cs.RO math.OC ·2026-11-10 ·Shiva Ganesh Murali, Valentin Bhend, Deepak Ingole, Gabriele Fadini, Alisa Rupenyan
similarity 0.58
Abstract · Submitted for the review in ECC 2027

Robotic additive manufacturing requires joint paths that reconcile robot feasibility with process-specific geometry. We develop an offline optimization-based path planner that combines joint-path regularity and self-collision penalties with process costs and constraints, so that a new process enters through its own reference, residuals, and tolerances. Full-path and boundary-coupled chunked optimization handle references of different lengths. Iterative Weight Tuning (IWT) determines the cost weights from the gaps between Key Performance Indicators (KPIs) and their targets. In carbon-fiber winding and robotic 3D printing, the planned paths meet the geometric tolerances and all KPI targets, and both paths are executed on a UR10e, without extrusion for printing, with joint-level tracking recorded during execution.

0.22

Asymmetric Decomposition for Multi-Agent Path Finding with Unassigned Agents

cs.RO cs.MA ·2026-11-18 ·Xi Jin, Chen Qian, Renjun Zhang, Guowei Wu, Xiaobo Li +2 more
benchmarktheorycode/data similarity 0.56
Abstract

Robots without assigned tasks may obstruct active robots, while routing them to designated parking locations can cause unnecessary travel. This article proposes flow-oracle conflict-based search (FOCBS) for Multi-Agent Path Finding with unassigned agents (MAPF-UA). FOCBS searches over assigned-agent paths using conflict-based search (CBS) and routes targetless unassigned agents through a min-cost flow oracle. When the selected assigned-agent paths leave unassigned agents no collision-free paths, flow-conflict branching converts min-cut blockers into assigned-agent constraints, which guide the search without excluding optimal solutions. A batched zero-cost warm start accelerates the oracle, and start-avoiding tie-breaking reduces unassigned-agent movement. For feasible instances on finite graphs, we prove termination and global minimization of assigned-agent sum of service time, measured by last-arrival times. Unassigned-agent movement is minimized conditional on the selected assigned-agent paths, without a global lexicographic optimality guarantee. Benchmark experiments show that FOCBS scales well with the number of unassigned agents, and ablation studies show that, compared with discarding non-completable assigned-agent paths, flow-conflict branching solves substantially more instances while retaining optimality. Simulation and physical-robot experiments demonstrate plan executability, with laboratory tests reducing fleet travel by 40.8% relative to the parking-based coordination baseline. The source code and related resources are available at https://github.com/Chin-hsi/focbs

0.50

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

cs.AI ·2026-08-25 ·Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini
benchmarktheory similarity 0.56
Abstract

Automated high-density storage systems (warehouses, robotic parking, plant logistics, etc.) require fleets of agents to move through scarce task-critical resources and then park without obstructing future operations. We introduce Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a MAPF variant in which a subset of tasked agents must each visit one of a set of interchangeable pivots (e.g., workstations) before the entire fleet terminates at anonymous stations, one agent per station. We characterize solvability completely: every instance on a 2-edge-connected graph is solvable, and, on arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices gives a necessary and sufficient condition. We prove that minimizing station-makespan or station-flowtime is NP-hard already with a single pivot. We present three algorithms, a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline.

0.16

Multi-Agent Path Planning via Compatible Encounter-Space Allocation in Crowded Spaces Dynamically Occupied by Work Activities

cs.CE ·2026-10-13 ·Boda Liu, Xuezhi Yang, Bin Yang, Shu Li
published similarity 0.55
Abstract · 81 pages; full English and Chinese versions are included, with the English version first. Planning to submit to IEEE Transactions on Robotic…

Lifelong multiagent path planning on construction floors must accommodate continually changing goals and work occupancy. Existing planners can update paths and timing online, but work motion space coupling changes the spatial basis of unfinished encounters, while rerouting affects later encounters. Planning must therefore construct and maintain local encounter possibility. We propose Width based Planning with Compatible Encounter Space Allocation (WP), which constructs shared passage relationships from actual encounter demands and real time widths. Shared channels, ordered anchors, and urgency based updates coordinate successive encounters while retaining individual greedy motion between them. A necessary and sufficient width condition for fixed-point position exchange and a necessary directional condition for composite exchange provide geometric grounds for channel construction and encounter relocation. In crowded floor computational experiments, WP maintained route continuation after occupancy changes and enabled multi agent clearing, with infrequent, brief near stops. Complete run comparisons with four methods showed 25.2% to 52.2% more mean goal arrivals than the best baseline at each configuration of 5 to 10 agents, with lower mean computation time than the rolling horizon K_CBS adaptation. The contribution is a planning principle that constructs and continuously maintains local passage relationships from real time space, unifying shared spatial allocation and conditional local clearing to extend lifelong planning to work motion space coupling.

0.37