Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing
Yimin Tang, Sven Koenig, Erdem Bıyık · 2026
Read Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing by Yimin Tang, Sven Koenig, Erdem Bıyık (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19388.txt.
Introduction
Yimin Tang, Sven Koenig, and Erdem Bıyık tidy the paths of robot fleets after a planner has done its job. Multi agent path finding is a hard problem with uses in warehouses and robot coordination. Learning based solvers are fast and scale well, but their feasible plans often include wasteful or wobbly moves.
Their layer, Judgelight, post optimizes each trajectory by collapsing closed subwalks, loops that return to their start. Cutting dead loops keeps the plan valid while making it shorter and cleaner. A cheap cleanup step can lift any solver's output, which makes it a handy add on.
Catalog record
| CREATOR | Yimin Tang, Sven Koenig, Erdem Bıyık |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19388
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing Yimin Tang, Sven Koenig, Erdem Bıyık Abstract Multi-Agent Path Finding (MAPF) is an NP-hard problem with applications in warehouse automation and multi-robot coordination. Learning-based MAPF solvers offer fast and scalable planning but often produce feasible trajectories that contain unnecessary or oscillatory movements. We propose Judgelight , a post-optimization layer that improves trajectory quality after a MAPF solver generates a feasible schedule. Judgelight collapses closed subwalks in agents’ trajectories to remove redundant movements while preserving all feasibility constraints. We formalize this process as MAPF-Collapse , prove that it is NP-hard, and present an exact optimization approach by formulating it as integer linear programming (ILP) problem. Experimental results show Judgelight consistently reduces solution cost by around 20%, particularly for learning-based solvers, producing trajectories that are better suited for real-world deployment. 1 Introduction Multi-Agent Path Finding (MAPF) is an NP-hard problem [ 39 , 51 ] that plans collision-free trajectories for multiple agents moving from given start locations to distinct goal locations on a known graph while optimizing a cost criterion. MAPF is a fundamental abstraction for coordination in domains such as warehouse automation, transportation, and aerial swarms. Lots of search-based methods are designed to solve this problem, including Conflict-Based Search (CBS) [ 30 ] , M^{*} [ 46 ] , LaCAM [ 27 ] , and MAPF-LNS2 [ 14 ] . These methods provide strong correctness guarantees and high-quality solutions, but their runtime increase substantially as the number of agents and the level of congestion grow, motivating complementary approaches that deliver fast decisions at scale. Driven by the success of deep neural networks in perception, control, and decision making [ 13 , 31 , 1 ] , learning-based MAPF solvers have attracted increasing attention [ 3 ] . Some learning-based methods, such as RAILGUN [ 44 ] , adopt a centralized formulation that uses global information as neural network input features and outputs the actions for all agents simultaneously. Others follow a decentralized formulation: each agent maps a local observation (often a limited field-of-view, FOV) to a single-step action, and all agents act either synchronously or in a fixed order. Representative methods include PRIMAL [ 29 ] , MAPPER [ 19 ] , MAGAT [ 18 ] , SCRIMP [ 50 ] , MAPF-GPT [ 4 ] , and SILLM [ 12 ] . These approaches typically rely on imitation learning (IL) and/or reinforcement learning (RL). Learned policies face two persistent challenges that limit their direct use as drop-in MAPF solvers. First, MAPF is safety-critical: even a single invalid action might cause a collision or a deadlock. In practice, learned policies are commonly wrapped by lightweight validity checks, and invalid moves are often patched by forcing one or more agents to wait. Recent work such as CS-PIBT [ 45 ] helps learning-based methods avoid producing collision-inducing next actions by using neural network output probabilities to guide the search order in the search-based algorithm PIBT [ 25 ] , thereby effectively increasing success rates under congestion. While these corrections are useful as they may prevent collisions, they only focus on feasibility at the next-action level. When the trajectories are already feasible, their post-processing do not improve the solution quality. Second, even when a learned solver outputs feasible trajectories, the resulting motion may exhibit unnecessary movements (e.g., back-and-forth movements) [ 45 ] that are undesirable in real deployments. In warehouse settings, such redundant motion increases energy consumption and mechanical wear, and may elevate operational risk by introducing avoidable interactions with other robots and environmental uncertainties. Importantly, this inefficiency might persist even when no nearby agents constrain the motion [ 45 ] , indicating that trajectory quality issues are not solely attributable to collision resolution. In this work, we propose Judgelight , a post-optimization layer that improves trajectory quality after a MAPF solver (learning-based or search-based) produces a feasible schedule. Judgelight targets redundant motion by allowing the solver to collapse closed subwalks in individual agents’ trajectories while maintaining all MAPF feasibility constraints. We formalize this post-processing task as a new optimization problem, MAPF-Collapse , whose objective is to minimize the total number of move actions (treating waits as low-cost) subject to feasibility. This formulation captures the deployment-motivated preference that an agent should stay in place unless movement is necessary. Our main contributions are: 1. We introduce MAPF-Collapse , a trajectory-level post-optimization problem that takes a feasible MAPF schedule as input and reduces redundant movements through collapse operations. 2. We analyze the computational complexity of MAPF-Collapse and prove that it is NP-hard . 3. We develop an exact optimization approach, Judgelight , for MAPF-Collapse and demonstrate that it consistently improves solution quality, particularly for learning-based MAPF solvers, producing trajectories that are more suitable for real-world warehouse-style operations. 2 Background: MAPF Problem Definition The MAPF problem is defined as follows: Let I=\{1,2,\cdots,N\} denote a set of N agents. G=(V,E) represents an undirected graph, where each vertex v\in V represents a possible location of an agent in the workspace, and each edge e\in E is a unit-cost edge between two vertices that moves an agent from one vertex to the other. Self-loop edges are also allowed, which represent “wait-in-place” actions. Each agent i\in I has a start location s_{i}\in V and a goal location g_{i}\in V . It also holds that s_{i}\neq s_{j} and g_{i}\neq g_{j} when i\neq j \forall i,j\in I . The task is to plan a collision-free path for each agent i from s_{i} to g_{i} . Each action of agents, either waiting in place or moving to an adjacent vertex, takes one time unit. Let v^{i}_{t}\in V be the location of agent i at timestep t . Let \pi_{i}=[v_{0}^{i},v_{1}^{i},...,v_{T^{i}}^{i}] denote a path of agent i from its start location v_{0}^{i} to its target v_{T^{i}}^{i} . We assume that agents rest at their targets after completing their paths, i.e., v_{t}^{i}=v_{T^{i}}^{i},\forall t>T^{i} . We refer to the path with the minimum cost as the shortest path. We consider two types of agent-agent collisions. The first type is vertex collision , where two agents i and j occupy the same vertex at the same timestep. The second type is edge collision , where two agents move in opposite directions along the same edge simultaneously. We use (i,j,t) to denote a vertex collision between agents i and j at timestep t or an edge collision between agents i and j at timestep t to t+1 . MAPF algorithms usually use SoC (flowtime) \sum_{i=1}^{N}T^{i} as the cost function. Overall, we need to find a set of paths \{\pi_{i}\mid i\in I\} for all agents such that, for each agent i : 1. Agent i starts from its start location (i.e., v_{0}^{i}=s_{i} ) and stops at its target location g_{j} (i.e., v_{t}^{i}=g_{j},\forall t\geq T^{i} ). 2. Every pair of adjacent vertices on path \pi_{i} is connected by an edge, i.e., (v_{t}^{i},v_{t+1}^{i})\in E,\forall t\in\{0,1,\dots,T^{i}\} . 3. \{\pi_{i}\mid i\in I\} is collision-free. 3 Related Work 3.1 Multi-Agent Path Finding (MAPF) MAPF has been proved an NP-hard problem when optimality is required [ 51 ] . It has inspired a wide range of solutions for its related challenges. Decoupled strategies, as outlined in [ 32 , 49 , 20 ] , approach the problem