論文の概要: Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
- arxiv url: http://arxiv.org/abs/2605.10917v1
- Date: Mon, 11 May 2026 17:52:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-12 23:28:51.053179
- Title: Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
- Title（参考訳）: マルチマルジナル最適輸送とシュレーディンガー橋による最適およびスケーラブルMAPF
- Abstract要約: MAPFはマルコフ構造を基礎としたMMOT(Multi-marginal optimal)問題の特別なクラスとしてキャスト可能であることを示す。
大規模問題へのアプローチに適応するため、我々はシュルディンガー橋を介してMAPF-MMOTを確率的フレームワークにキャストした。
- 参考スコア（独自算出の注目度）: 1.6042394978941512
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider anonymous multi-agent path finding (MAPF) where a set of robots is tasked to travel to a set of targets on a finite, connected graph. We show that MAPF can be cast as a special class of multi-marginal optimal transport (MMOT) problems with an underlying Markovian structure, under which the exponentially large MMOT collapses to a linear program (LP) polynomial in size. Focusing on the anonymous setting, we establish conditions under which the corresponding LP is feasible, totally unimodular, and consequently, yields min-cost, integral $(\{0,1\})$ transports that do not overlap in both space and time. To adapt the approach to large-scale problems, we cast the MAPF-MMOT in a probabilistic framework via Schrödinger bridges. Under standard assumptions, we show that the Schrödinger bridge formulation reduces to an entropic regularization of the corresponding MMOT that admits an iterative Sinkhorn-type solution. The Schrödinger bridge, being a probabilistic framework, provides a shadow (fractional) transport that we use as a template to solve a reduced LP and demonstrate that it results in near-optimal, integral transports at a significant reduction in complexity. Extensive experiments highlight the optimality and scalability of the proposed approaches.
- Abstract（参考訳）: 匿名多エージェント経路探索(MAPF)では、ロボットの集合が有限連結グラフ上の対象の集合に移動する。
MAPF はマルコフ構造を持つマルチマルジナル最適輸送 (MMOT) 問題の特別なクラスとしてキャストされ,指数関数的に大きい MMOT が線形プログラム (LP) 多項式に小さく崩壊することを示す。
匿名の設定に焦点をあてて、対応するLPが実現可能で、完全に一様であり、従って、最小コスト、積分$(\{0,1\})$輸送が空間と時間の両方で重複しない条件を確立する。
大規模問題へのアプローチに適応するため、シュレーディンガー橋を介してMAPF-MMOTを確率的フレームワークにキャストした。
標準的な仮定では、シュレーディンガー橋の定式化は、反復シンクホーン型解を持つ対応するMMOTのエントロピー正則化に還元されることを示す。
シュレーディンガー橋 (Schrödinger bridge) は確率的枠組みであり、還元LPを解くためのテンプレートとして我々が使用するシャドウ(フラクタル)輸送を提供し、それが複雑さを著しく減少させ、ほぼ最適で積分的な輸送をもたらすことを示した。
大規模な実験では、提案されたアプローチの最適性とスケーラビリティを強調している。
関連論文リスト
- Twisted Schrödinger Bridge Matching [34.126987447337534]
拡散に基づくシュルディンガー橋模型は、2つの所定の境界分布間の最適輸送ダイナミクスを近似するために提案されている。
連続時間と離散時間の両方を扱うために設計された拡散法であるTwisted Schrdinger Bridge Matchingを紹介する。
論文 参考訳（メタデータ） (2026-07-18T22:30:43Z) - A Generalized Sinkhorn Algorithm for Mean-Field Schrödinger Bridge [19.922542189921447]
平均フィールド・シュルディンガー橋(英語版)(MFSB)問題は、非局所相互作用を持つ拡散過程を一定期限で所定の分布に到達させる最小効果制御器を設計することに関するものである。
シュルディンガー橋とは異なり、MFSBの動的制約は反発制御を持つ相互作用剤の集団である。
MFSBのためのHopf-Coleアルゴリズムの一般化を提案し、それを構築する上で、関連するシステム積分PDEを解決するシンクホーン型アルゴリズムを設計する。
論文 参考訳（メタデータ） (2026-04-08T00:04:52Z) - Schrödinger bridge for generative AI: Soft-constrained formulation and convergence analysis [6.584866740785309]
いわゆるソフト拘束型シュリンガー橋問題(SCSBP)について検討する。
ペナルティが大きくなるにつれて、制御関数と値関数の両方が線形速度で古典的SBPのものと収束することが証明される。
これらの結果から,ソフト拘束ブリッジの定量的収束保証が得られた。
論文 参考訳（メタデータ） (2025-10-13T18:29:15Z) - Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
マルチロボット運動計画(MPMP)は、共有された連続作業空間で動作する複数のロボットのための軌道を生成する。
離散マルチエージェント探索(MAPF)法は,その拡張性から広く採用されているが,粗い離散化の軌道品質は高い。
本稿では、制約付き生成拡散モデルを用いた離散MAPF解法を導入することにより、2つのアプローチの限界に対処する。
論文 参考訳（メタデータ） (2025-08-27T17:59:36Z) - Schrödinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres [6.197358216842481]
フローベース生成モデリングの最近の進歩は、分布間のSchr"odinger Bridge (SB) を計算するためのスケーラブルな方法を提供している。
従来のIPF(Iterative Proportional Fitting)法よりも多くの特性を持つエレガントで実践的なアプローチを提案する。
得られたアルゴリズムは、ツリーベースの設定でIPFアプローチよりもIMFの多くの利点を継承する。
論文 参考訳（メタデータ） (2025-06-20T17:47:47Z) - Light and Optimal Schrödinger Bridge Matching [67.93806073192938]
我々はSB(Schr"odinger Bridges)を学習するための新しい手法を提案し、それを textbf Schr"odinger Bridge matching と呼ぶ。
EOT/SBを学習するための最適橋梁マッチングは,最近発見されたエネルギーベースモデリング(EBM)の目標と一致することを示す。
我々は、Schr"odinger電位の混合パラメタライゼーションを用いて、実際に最適なマッチングを実現するための光解法(LightSB-Mと呼ぶ)を開発した。
論文 参考訳（メタデータ） (2024-02-05T17:17:57Z) - Generalized Schrödinger Bridge Matching [54.171931505066]
一般化Schr"odinger Bridge (GSB) 問題設定は、機械学習の内外を問わず、多くの科学領域で一般的である。
我々は最近の進歩に触発された新しいマッチングアルゴリズムである一般化シュリンガーブリッジマッチング(GSBM)を提案する。
このような一般化は条件最適制御の解法として、変分近似を用いることができることを示す。
論文 参考訳（メタデータ） (2023-10-03T17:42:11Z) - Light Schrödinger Bridge [72.88707358656869]
我々は,軽量でシミュレーション不要で理論的に正当化されたSchr"odinger Bridgesソルバを開発した。
我々の光解法は密度推定に広く用いられているガウス混合モデルに類似している。
この類似性に着想を得て、光解法がSBの普遍近似であることを示す重要な理論的結果も証明した。
論文 参考訳（メタデータ） (2023-10-02T13:06:45Z) - Implicitly normalized forecaster with clipping for linear and non-linear
heavy-tailed multi-armed bandits [85.27420062094086]
Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。
重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。
INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
論文 参考訳（メタデータ） (2023-05-11T12:00:43Z) - Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
我々は、射影方向にマルコフ構造を課す新しいSW距離の族、Markovian sliced Wasserstein (MSW) 距離を導入する。
フロー,色移動,深部生成モデルなどの様々な応用において,従来のSW変種との距離を比較し,MSWの良好な性能を示す。
論文 参考訳（メタデータ） (2023-01-10T01:58:15Z) - Near-optimal estimation of smooth transport maps with kernel
sums-of-squares [81.02564078640275]
滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。
生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。
そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-03T13:45:36Z) - On Multimarginal Partial Optimal Transport: Equivalent Forms and
Computational Complexity [11.280177531118206]
我々は,少なくとも$n$のサポートを持つ離散的(アンバランスな)測度間のマルチマルジナル部分最適輸送(POT)問題について検討した。
まず、コストテンソルの新たな拡張を通じて、マルチマルジナルな最適輸送問題の観点から、マルチマルジナルPOT問題の2つの等価形式が得られることを証明した。
我々は、ApproxMPOTアルゴリズムが、$tildemathcalO(m3(n+1)m/ varの計算複雑性上界を持つマルチマルジナルPOT問題の最適値を近似できることを実証した。
論文 参考訳（メタデータ） (2021-08-18T06:46:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。