CS Paper Radar

TRACS: A Geometry-Aware Framework for Scalable Multi-Agent Path Finding in Warehouses

Siddhant Erande, Anuj Tiwari

eess.SY cs.MA ·submitted 2026-09-19 17:07 UTC · v1

Abstract

Large scale warehouse automation relies on efficient multi agent path finding (MAPF) to coordinate thousands of robots in structured environments. Existing MAPF algorithms primarily improve conflict resolution while representing warehouses as generic navigation graphs, overlooking their inherent geometric structure and traffic patterns. This paper presents TRACS (Traffic aware Routing and Aisle Coordination System), a geometry aware planning framework that exploits warehouse layout to simplify planning rather than introducing another conflict-resolution algorithm. TRACS constructs a directed routing graph with alternating one way aisles that eliminates head on and edge swap conflicts by design, decoupling spatial routing from temporal traffic coordination. Independent hybrid graph grid routing is combined with lightweight edge based scheduling to avoid joint space time search while ensuring collision free execution. Experimental evaluation on warehouse benchmarks against representative priority based, iterative repair, and search based MAPF planners shows that TRACS consistently achieves a 100% empirical success rate while substantially improving planning scalability. On fixed scene benchmarks with up to 1000 robots, TRACS reduces planning time by up to 14.7X while maintaining competitive makespan, lower flowtime, and near optimal path quality. Under a fixed 10 minute planning budget, TRACS routes up to 5120 robots, roughly twice the largest fleet reached by the strongest baselines, while sustaining a 100% success rate, demonstrating the effectiveness of exploiting warehouse geometry for scalable robotic warehouse systems.

Comment
9 pages, 6 figures, under review

Closest papers

Nearest neighbours by meaning across the whole index.

CARVS: A Congestion-Aware Algorithm for Online Multi-Agent Pickup-and-Delivery in Human-Collaborative Warehouses

cs.MA cs.AIcs.RO ·2026-10-17 ·Chaoran Li, Zeyuan Zhao, Shao Zhang
published similarity 0.71
Abstract · 13 pages, 8 figures. Accepted at DAI 2026 (Oral)

Intelligent warehouse systems have transformed logistics by integrating robots with minimal infrastructure changes, boosting efficiency and optimizing workflows compared to traditional human-only operations. However, human-robot collaboration introduces new challenges, particularly due to human uncertainty, which leads to dynamic interactions and unpredictable behavior. To address these complexities, this paper presents the Multi-Agent Pickup-and-Delivery with Human Collaboration (MAPDwHC) problem, an extension of the Multi-Agent Pickup-and-Delivery (MAPD) problem that incorporates human unpredictability. This problem adds key constraints, such as dynamic obstacles caused by robots temporarily blocking paths when interacting with humans, and the need for real-time responsiveness. We formalize the MAPDwHC problem with additional constraints and properties. Based on this problem setting, we propose the CARVS algorithm, which improves task assignment and path planning by integrating task swapping, validation checks, and random initialization. CARVS reduces congestion, enhances adaptability to human-robot interactions, and ensures real-time responsiveness. Simulation results show that CARVS significantly reduces timeouts of path planning in large-scale scenarios where traditional MAPD algorithms fail, improving both efficiency and scalability.

0.35

Solving Multi-Agent Sokoban via LaCAM

cs.MA ·2026-09-30 ·Keisuke Okumura
benchmark similarity 0.69
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

Late Autumn: LLM Agents Specialize a General Multi-Robot Planner for One Warehouse

cs.RO cs.AI ·2026-11-02 ·Yimin Tang, Han Zhang, Shao-Hung Chan, Erdem Bıyık, Sven Koenig +1 more
similarity 0.68
Abstract

No algorithm is best on all problems, but a real warehouse is a narrow problem: its layout and processes rarely change. Operators still run one general multi-robot planner at many sites, because experts cannot tune it for each one. In this work, which we call Late Autumn, we explore whether LLM coding agents running autonomous research can specialize a general planner for one site, trading generality for throughput, much as post-training adapts a pretrained LLM to one task. We study six campaigns on a lifelong planner that combines task assignment with multi-agent path finding, on a floor modeled on an existing automated warehouse. We find that (1) the agents raise throughput by 22--60%, and the gains hold on unseen seeds; (2) they rediscover known MAPF mechanisms, such as corridor-exit priorities, local guidance, and rollouts, and independent campaigns find the same bottleneck; (3) the gains largely carry over to another layout, a larger fleet, and other service times, shrink with a smaller fleet, and mostly vanish under an outbound-heavy demand mix; and (4) each final patch (0.7k--2.4k lines) is a chain of scored commits with a median step of 27 lines, so experts can review it, and review finds problems that the score misses; some patches multiply planner compute by over 100x. LLM agents can therefore turn each site's bias into extra throughput at little engineering cost, with reviewable patches; we expect experts to shift toward designing insightful metrics and fast simulators that mirror the real problem.

0.07

Local Solution Repair for Multi-Agent Pickup and Delivery

cs.RO cs.MA ·2026-11-01 ·Ethan Schneider, Jingkai Chen, Seth Hutchinson, Sonia Chernova
similarity 0.68
Abstract

Multi-robot systems in automated warehouses must efficiently attend to a constant stream of pickup-and-delivery tasks while avoiding collisions. Existing Multi-Agent Pickup-and-Delivery (MAPD) solutions generate plans that are globally feasible but often locally inefficient. In large-scale, long-horizon deployments, these inefficiencies, such as robots backtracking from target goal locations and idling in congested areas, accumulate over time and degrade performance. This paper contributes Local Solution Repair (LSR), a goal replanning approach that detects suboptimal behaviors at run-time and locally improves plans to reduce conflict between agents. We demonstrate the utility of our approach by repairing solutions generated by state-of-the-art MAPD baselines, M2M and LNS-PBS. Our results in long-horizon warehouse simulations over three environments show upwards of 5.9% improvement in task throughput over current state-of-the-art methods by reducing the number of suboptimal instances by ~36k or by 14.6% with minor additional computation time.

0.12

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.66
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

LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions

cs.RO cs.AIcs.MA ·2026-11-07 ·Dachuan Liu, Shuai Zhou, Shizhe Zhao, Zhongqiang Ren
publishedhighly cited similarity 0.64
Abstract · 15 pages, 14 figures

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit the use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-based Planning (LSRP) was proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSRP* and test it against several baselines with up to 1000 agents on various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP.

0.61

The Cost of Classical Multi-Agent Path Finding

cs.MA ·2026-10-07 ·Alvin Combrink, Sabino Francesco Roselli, Martin Fabian
theory similarity 0.64
Abstract · 9 pages, 5 figures

Multi-Agent Path Finding (MAPF) is the problem of planning conflict-free paths for multiple agents in a shared space, each from its start to its goal. Classical MAPF has been the dominant formulation for many years, with its assumptions of discrete time and graph-based conflicts presumably easing the search for solutions. These assumptions limit the physical environments and agents for which a solution is truly collision-free, and also place an upper bound on solution quality that no algorithmic improvements can lift. This work investigates how much solution quality, and in what contexts, the classical MAPF formulation forfeits. Continuous-time MAPF (MAPF$_R$) relaxes these assumptions, making it a natural counter-formulation to compare against across various agent counts and sizes, and graph connectedness, topologies, and resolutions. We find that continuous time and agent shape consideration are worth relatively little on their own; their value comes from enabling an expanded range of move actions, on average improving solution quality by at least $5\%$ on narrow and constrained maps and $17\%$ on maps with open spaces. In some cases, the improvements exceed $20\%$. Doubling the map resolution with classical MAPF recovers less than $3\%$, meaning that little of what is forfeited can be bought back through more compute. This work therefore provides insight on when classical MAPF is a reasonable simplification, and when MAPF$_R$ unlocks significantly higher-quality solutions.

0.08

Fixed-Haven Reservation for Online Multi-Agent Pickup and Delivery in Dense Warehouses

cs.MA cs.RO ·2026-08-27 ·Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji, Itsuki Noda
publishedtheory similarity 0.63
Abstract · 11 pages, 9 figures. Accepted at the 14th Workshop on Planning and Robotics (PlanRob), co-located with ICAPS 2026

Dense warehouses often contain single-lane aisles, dead ends, and tree-like guidepaths that leave little room for idle agents to wait without blocking others. Existing Multi-Agent Pickup and Delivery (MAPD) guarantees for completing all finitely released tasks typically rely on extra waiting endpoints that planned paths can avoid, or on biconnected topology; these assumptions may fail in such layouts. We study fixed-Haven reservation for online MAPD, where pickup-delivery tasks are released over time. Each agent owns a fixed Safe Haven (Haven for short), usually its start cell, that only the owner may occupy and that other agents treat as blocked. For finite task releases, we prove that this fixed-Haven contract completes all released tasks under Haven-Reachability and explicit planning/progress assumptions. We implement the contract in SHARP, a Safe-Haven Retreat Planner that keeps every busy or retreating agent on a collision-free reserved route ending at its Haven. We compare SHARP with representative TP and PIBT-family MAPD baselines: Token Passing (TP), Priority Inheritance with Backtracking (PIBT), and PIBT with Temporary Priority and Temporary Avoidance (PIBTTP-TA) for biconnected main areas with attached trees. In the robustness sweep, SHARP is the only method with 100% success on all tested configurations, at substantially higher centralized planning cost on tree-like layouts. A TP-style fixed-home-return counterfactual with full-route validation also recovers robustness on tested tree-like layouts, suggesting that fixed return is a central robustness mechanism there. A no-overwrite variant shows that disabling mid-retreat reassignment worsens service time (release-to-delivery latency) by 1.89 times and makespan by 1.53 times in the tested high-load tree condition.

0.37