論文の概要: 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
- Authors: Usman A. Khan, Joseph W. Durham,
- 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を解くためのテンプレートとして我々が使用するシャドウ(フラクタル)輸送を提供し、それが複雑さを著しく減少させ、ほぼ最適で積分的な輸送をもたらすことを示した。
大規模な実験では、提案されたアプローチの最適性とスケーラビリティを強調している。
関連論文リスト
- 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) - Generalized Schrödinger Bridge Matching [54.171931505066]
一般化Schr"odinger Bridge (GSB) 問題設定は、機械学習の内外を問わず、多くの科学領域で一般的である。
我々は最近の進歩に触発された新しいマッチングアルゴリズムである一般化シュリンガーブリッジマッチング(GSBM)を提案する。
このような一般化は条件最適制御の解法として、変分近似を用いることができることを示す。
論文 参考訳（メタデータ） (2023-10-03T17:42:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。