Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing

• URL: http://arxiv.org/abs/2601.19388v2
• Date: Wed, 28 Jan 2026 03:15:23 GMT
• Title: Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing
• Abstract summary: Multi-Agent Path Finding (MAPF) is an NP-hard problem with applications in warehouse automation and multi-robot coordination.<n>We propose Judgelight, a post-optimization layer that improves trajectory quality after a MAPF solver generates a feasible schedule.
• Score: 10.510038680299223
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Execution-Verified Reinforcement Learning for Optimization Modeling [49.171122807323634]
  Execution-verified learning framework treats a mathematical programming solver as a deterministic, interactive verifier.<n>Experiments on NL4OPT, MAMO, IndustryOR, and OptiBench across Gurobi, OR-Tools, and COPT show that EVOM matches or outperforms process-supervised SFT.
  arXiv  Detail & Related papers  (2026-04-01T03:39:11Z)
• Parallel Diffusion Solver via Residual Dirichlet Policy Optimization [88.7827307535107]
  Diffusion models (DMs) have achieved state-of-the-art generative performance but suffer from high sampling latency due to their sequential denoising nature.<n>Existing solver-based acceleration methods often face significant image quality degradation under a low-dimensional budget.<n>We propose the Ensemble Parallel Direction solver (dubbed as EPD-EPr), a novel ODE solver that mitigates these errors by incorporating multiple gradient parallel evaluations in each step.
  arXiv  Detail & Related papers  (2025-12-28T05:48:55Z)
• Bridging Planning and Execution: Multi-Agent Path Finding Under Real-World Deadlines [9.228609005424348]
  We propose REMAP, an execution-informed MAPF planning framework for time-sensitive applications.<n>Our framework integrates the proposed ExecTimeNet to accurately estimate execution time based on planned paths.<n>Experiments show that REMAP achieves up to 20% improvement in solution quality over baseline methods.
  arXiv  Detail & Related papers  (2025-11-26T20:08:52Z)
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
  arXiv  Detail & Related papers  (2025-08-27T17:59:36Z)
• Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning [46.35418789518417]
  Multi-agent pathfinding (MAPF) is a common abstraction of multi-robot trajectory planning problems.<n>We introduce MAPF-GPT-DDG, a decentralized suboptimal MAPF solvers that leverage machine learning.<n>Our experiments demonstrate that MAPF-GPT-DDG surpasses all existing learning-based MAPF solvers.
  arXiv  Detail & Related papers  (2025-06-30T12:34:31Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  Multi-agent pathfinding (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in a shared environment.<n>Recently, learning-based approaches to MAPF have gained attention, particularly those leveraging deep reinforcement learning.<n>We show that MAPF-GPT notably outperforms the current best-performing learnable MAPF solvers on a diverse range of problem instances.
  arXiv  Detail & Related papers  (2024-08-29T12:55:10Z)
• Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic [16.4408116214332]
  We propose Adaptive Delay-based Destroy-and-Repair with Enhanced Success-based Self-Learning (ADDRESS) as a single-destroy-heuristic variant of MAPF-LNS.<n>We demonstrate cost improvements by at least 50% in large-scale scenarios with up to a thousand agents, compared with the original MAPF-LNS.
  arXiv  Detail & Related papers  (2024-08-06T05:15:35Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search [30.364955687049292]
  State-of-the-art anytime MAPF is based on Large Neighborhood Search (LNS) We propose Bandit-based Adaptive LArge Neighborhood search Combined with Exploration (BALANCE) We empirically demonstrate cost improvements of at least 50% compared to state-of-the-art anytime MAPF in large-scale scenarios.
  arXiv  Detail & Related papers  (2023-12-28T01:24:42Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.