論文の概要: Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing

• arxiv url: http://arxiv.org/abs/2601.19388v2
• Date: Wed, 28 Jan 2026 03:15:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 08:17:40.959259
• Title: Judgelight: Trajectory-Level Post-Optimization for Multi-Agent Path Finding via Closed-Subwalk Collapsing
• Title（参考訳）: ジャッジライト:クローズド・サブウォーク・コラプシングによるマルチエージェントパス探索のための軌道レベル後最適化
• Authors: Yimin Tang, Sven Koenig, Erdem Bıyık,
• Abstract要約: MAPF(Multi-Agent Path Finding)は、倉庫の自動化と複数ロボットの協調におけるNPハード問題である。 本稿では、MAPFソルバが実行可能なスケジュールを生成した後、軌道品質を向上させるポスト最適化層であるジャッジライトを提案する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: MAPF(Multi-Agent Path Finding)は、倉庫の自動化と複数ロボットの協調におけるNPハード問題である。 学習ベースのMAPFソルバは、高速でスケーラブルな計画を提供するが、しばしば不必要または振動運動を含む実行可能な軌道を生成する。 本稿では、MAPFソルバが実行可能なスケジュールを生成した後、軌道品質を向上させるポスト最適化層であるジャッジライトを提案する。 判事の光はエージェントの軌道に閉じた潜航路を崩壊させ、余分な動きを排除し、すべての実現可能性の制約を守った。 この過程をMAPF-Collapseとして定式化し、NPハードであることを証明し、整数線形プログラミング(ILP)問題として定式化して正確な最適化手法を提案する。 実験結果からは,特に学習ベースの問題解決において,現実のデプロイメントに適したトラジェクトリを生成することにより,ソリューションコストを一貫して約20%削減できることがわかった。

関連論文リスト

• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  マルチロボット運動計画(MPMP)は、共有された連続作業空間で動作する複数のロボットのための軌道を生成する。 離散マルチエージェント探索(MAPF)法は,その拡張性から広く採用されているが,粗い離散化の軌道品質は高い。 本稿では、制約付き生成拡散モデルを用いた離散MAPF解法を導入することにより、2つのアプローチの限界に対処する。
  論文  参考訳（メタデータ） (2025-08-27T17:59:36Z)
• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  MAPF(Multi-agent pathfinding)は、一般に、共有環境において複数のエージェントに対して衝突のない経路を見つけることを必要とする問題である。 近年、MAPFへの学習に基づくアプローチが注目されており、特に深層強化学習を活用している。 MAPF-GPTは,多種多様な問題インスタンスにおいて,現在最も優れた学習可能なMAPFソルバよりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-08-29T12:55:10Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search [30.364955687049292]
  MAPFはLarge Neborhood Search(LNS)に基づいている 探索を併用したBandit-based Adaptive LArge Neighborhood Search(BALANCE)を提案する。 大規模シナリオでは、最先端のMAPFと比較して、少なくとも50%のコスト改善が実証的に実証されている。
  論文  参考訳（メタデータ） (2023-12-28T01:24:42Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。