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

Siddhant Erande; Anuj Tiwari

eess.SYSep 19, 2026

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

Authors: Siddhant Erande, Anuj Tiwari

Organizations: Department of Engineering Design, Indian Institute of Technology Madras, Chennai 600036, India · Department of Mechanical Engineering at Indian Institute of Technology Madras, Chennai 600036, India

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.

Figures & tables

Fig. 1: Overview of the TRACS pipeline. (I) Graph construction : the warehouse layout is converted into a directed routing graph by assigning alternating one-way travel directions to parallel aisles. (II) Route planning : each robot independently computes its lowest-cost route on this graph, combining local grid search with directed-graph search over its $k$ nearest entry/exit edges. (III) Traffic coordination : at execution time, a lightweight edge-based scheduler grants edge, cell, and junction reservations under capacity and headway constraints. Because stages II and III are decoupled, TRACS avoids joint space–time search while still guaranteeing collision-free execution.

Fig. 2: Construction of the directed routing graph. Alternating aisle directions preserve global connectivity while eliminating head-on and edge-swap conflicts by construction. As a result, the remaining interactions are localized to junction nodes, which constitute only $1$ – $2\%$ of the navigable cells in a typical warehouse.

Planner	SR	Time (s)	Makespan	Flowtime
PIBT2 [ 18 ]	67%	93.5	240	240,000
Prioritized [ 8 ]	100%	629.8	177	98,270
MAPF-LNS2 [ 6 ]	100%	439.3	177	98,270
LaCAM [ 7 ]	100%	77.5	178	178,000
TRACS (ours)	100%	42.7	182	73,635

TABLE I: Planner comparison at

N=1000

on the

81\times 125

warehouse. Among planners achieving a

100\%

success rate (SR), TRACS provides the fastest planning time and the lowest flowtime. Times are reported in seconds.

Fig. 3: Scalability under a fixed 10-minute planning budget on two large warehouses ( $207\times 457$ , top; $307\times 927$ , bottom). Left : largest fleet each planner completes within budget. Centre : planning time versus fleet size (log–log scale), with the 10-minute ceiling marked. Right : success rate versus maximum fleet size (bubble size $\propto$ success rate). TRACS reaches the largest fleet size on both maps while remaining on the $100\%$ success-rate line throughout.

Planner	$207\times 457$	$307\times 927$
Prioritized [ 8 ]	320	160
MAPF-LNS2 [ 6 ]	320	160
LaCAM [ 7 ]	1280	1280
PIBT2 [ 18 ]	2560	1280
TRACS (ours)	5120	2560

TABLE II: Largest fleet successfully routed within a 10-minute planning budget. Fleet size is doubled from 10 robots until the first unsuccessful run.

Fig. 4: Occupancy density (top row) and collision-event density (bottom row) for $N=500$ robots, compared across all five planners. TRACS spreads traffic along the directed aisle backbone and visits the fewest total cells (top row), while its higher count of local following/goal-contention events (bottom row) reflects the edge-based scheduler actively managing junction access rather than unresolved conflicts.

Fig. 5: Path length of TRACS versus the single-agent-optimal CBS baseline, grouped by Manhattan trip distance: (a) mean path length; (b) full distribution (box: interquartile range; whiskers: 5th–95th percentile). The one-way detour overhead is largest, in relative terms, for the shortest trips ( $0$ – $20$ cells) and shrinks to within a few percent of optimal beyond $\sim\!20$ cells, where warehouse shelf-to-workstation trips predominate.

Fig. 6: Success rate, flowtime, makespan, planning time, and local contention events for TRACS and all baselines at $N=100$ , $500$ , and $1000$ robots on the $81\times 125$ warehouse. TRACS is the only planner with a $100\%$ success rate at every fleet size, and its advantage in planning time and flowtime widens as $N$ grows.

Multi-Agent Path Finding

Multi-agent path finding (MAPF) plans collision-free routes for multiple agents sharing an environment.

See all 92 papers

From Gridworlds to Warehouses: Adapting Lightweight One-shot Multi-Agent Pathfinding for AGVs
May 15, 2026Hiroki Nagai, Keisuke OkumuraMulti-Robot Motion Planning Constrained Motion Planning
National Institute of Advanced Industrial Science and Technology (AIST), Japan
Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding
Mar 11, 2026Fernando Salanova, Eduardo Montijano, Cristian MahuleaMulti-Agent Planning Multi-Agent Path Finding
Dept. of Systems Engineering and Computer Science, University of Zaragoza, Zaragoza, Spain
Learning-guided Prioritized Planning for Lifelong Multi-Agent Path Finding in Warehouse Automation
Mar 25, 2026Han Zheng, Yining Ma, Brandon Araki +2Warehouse Automation Multi-Agent Path Finding
Massachusetts Institute of Technology, Cambridge, MA, USA · Symbotic, Wilmington, MA, USA

May 15, 2026J/K move · Enter open · S save

From Gridworlds to Warehouses: Adapting Lightweight One-shot Multi-Agent Pathfinding for AGVs

Hiroki Nagai, Keisuke Okumura

National Institute of Advanced Industrial Science and Technology (AIST), Japan

Multi-Robot Motion Planning Constrained Motion Planning Robot Navigation Multi-Agent Path Finding

Open paper AskPDF arXiv

Multi-agent pathfinding (MAPF) under one-shot planning is a core component of warehouse automation, yet classical formulations typically assume four-connected 2D grids with unit-time moves in four directions. To fill reality gaps while still being trackable with discrete combinatorial search, this work proposes a more practical counterpart tailored to differential-drive AGVs. We term this multi-agent warehouse pathfinding (MAWPF), featured with four constraints: (i) agent actions are restricted to straight motion and in-place rotation; (ii) rotations require multi-step costs; (iii) acceleration and deceleration are considered, and; (iv) follower collisions are prohibited to prevent rear-end crashes. To solve MAWPF efficiently, we adapt representative suboptimal MAPF algorithms-PP, LNS2, PIBT, and LaCAM-and conduct comprehensive benchmarking. Our experiments reveal that PP and LNS2 struggle to solve instances with many agents, while PIBT-based approaches achieve preferable scalability with increased solution cost. We believe that these constitute an important step toward adapting classical gridworld MAPF to operational warehouse setups.

Abstract

Multi-Agent Path Finding

Explore similar work

From Gridworlds to Warehouses: Adapting Lightweight One-shot Multi-Agent Pathfinding for AGVs

Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding

Learning-guided Prioritized Planning for Lifelong Multi-Agent Path Finding in Warehouse Automation