論文の概要: Discrete Model-Based Diffusion for Combinatorial Optimization in Multi-Robot Task Allocation
- arxiv url: http://arxiv.org/abs/2611.13382v2
- Date: Wed, 11 Nov 2026 20:52:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:32.901587
- Title: Discrete Model-Based Diffusion for Combinatorial Optimization in Multi-Robot Task Allocation
- Title(参考訳): 離散モデルに基づく複数ロボットタスク割当における組合せ最適化のための拡散
- Abstract要約: マルチロボットシステムにおける決定は、ほぼリアルタイムな実装のために数秒以内に解決しなければならない離散的な決定変数を含むことが多い。
モデルベース拡散(MBD: Model-Based Diffusion)は、サンプルベース最適化(SBO: sample-based optimization)において、トレーニングなしで、連続空間上でのみ拡散を組み込む。
モンテカルロサンプリングによるカテゴリー逆遷移分布を近似することにより、離散変数を直接最適化する訓練自由なSBO法である離散モデルベース拡散(Discrete MBD)を提案する。
- 参考スコア(独自算出の注目度): 9.466312202833421
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decision making in multi-robot systems often involves discrete decision variables, leading to NP-hard combinatorial optimization problems that must be solved within seconds for near real-time implementation. Denoising diffusion has emerged as a powerful tool for such problems, but existing approaches face a trade-off: Model-Based Diffusion (MBD) incorporates diffusion in sampling-based optimization (SBO) without training but only over continuous spaces, while existing diffusion-based combinatorial solvers operate over discrete spaces but require offline training. To this end, we propose Discrete Model-Based Diffusion (Discrete MBD), a training-free SBO method that directly optimizes discrete variables by approximating categorical reverse transition distributions through Monte Carlo sampling. We establish a finite-step lower bound on the probability of finding a global minimizer and show that this bound converges to one as the number of denoising steps increases. Extensive experiments on generic integer programs and heterogeneous multi-robot coalition formation and scheduling demonstrate that Discrete MBD outperforms SBO baselines in nearly all settings while achieving solution quality competitive with that of mixed-integer programming and reinforcement learning methods at a fraction of their computational cost.
- Abstract(参考訳): マルチロボットシステムにおける決定は、しばしば離散的な決定変数を伴い、NPハードな組合せ最適化問題を引き起こす。
モデルベース拡散(MBD)は、トレーニングなしでサンプリングベース最適化(SBO)に拡散を組み込むが、連続空間上でのみ拡散し、既存の拡散ベース組合せ解法は離散空間上で動作し、オフライントレーニングを必要とする。
そこで本研究では,モンテカルロサンプリングによるカテゴリー逆遷移分布の近似により,離散変数を直接最適化する学習自由なSBO法であるDiscrete Model-Based Diffusion (Discrete MBD)を提案する。
我々は、大域最小化子を見つける確率に基づいて有限段階の下界を確立し、この境界が1に収束することを示す。
汎用整数プログラムとヘテロジニアスなマルチロボット連成とスケジューリングに関する広範な実験により、離散MBDはSBOのベースラインをほぼ全ての設定で上回り、混合整数プログラミングや強化学習法と競合する解品質を計算コストのごく一部で達成することを示した。
関連論文リスト
- Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion [40.25954048196068]
本稿では,混合整数最適化問題の事例を大まかに解くための,学習に基づく新しい手法を提案する。
提案手法は,混合整数最適化問題の離散成分を学習するグラフベース生成拡散モデルに依存する。
Constrained Graph Diffusion (CGD) という名前のフレームワークは問題に依存しず、様々な混合整数最適化問題に対応できる。
論文 参考訳(メタデータ) (2026-08-13T10:46:18Z) - DiffusionOPD: A Unified Perspective of On-Policy Distillation in Diffusion Models [55.01951088768769]
DiffusionOPDはオンライン政策蒸留(OPD)に基づく拡散モデルのための新しいマルチタスクトレーニングパラダイムである
本研究では,DiffusionOPDがトレーニング効率と最終性能において,マルチリワードRLとカスケードRLのベースラインを一貫して上回っていることを示す。
論文 参考訳(メタデータ) (2026-05-14T16:49:09Z) - FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming [52.52020895303244]
Mixed-Integer Linear Programming (MILP)は、複雑な意思決定問題の基本的なツールである。
混合整数線形計画法(FMIP)のための連立連続整数フローを提案する。これはMILPソリューションにおける整数変数と連続変数の共分散をモデル化する最初の生成フレームワークである。
FMIPは任意のバックボーンネットワークや様々なダウンストリームソルバと完全に互換性があり、現実世界のMILPアプリケーションにも適している。
論文 参考訳(メタデータ) (2025-07-31T10:03:30Z) - Inference-Time Scaling of Diffusion Language Models with Particle Gibbs Sampling [70.8832906871441]
我々は、モデルを再訓練することなく、所望の報酬に向けて世代を操る方法を研究する。
従来の手法では、通常は1つの認知軌道内でサンプリングやフィルタを行い、軌道レベルの改善なしに報酬をステップバイステップで最適化する。
本稿では,拡散言語モデル(PG-DLM)の粒子ギブスサンプリングについて紹介する。
論文 参考訳(メタデータ) (2025-07-11T08:00:47Z) - Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
本稿では,両者の時間的分離を必要とせずに,意思決定とIS分布を共同で更新する反復型アルゴリズムを提案する。
本手法は,IS分布系に対する目的的,軽度な仮定の凸性の下で,最小の変数分散を達成し,大域収束を保証する。
論文 参考訳(メタデータ) (2025-04-04T16:10:18Z) - Go With the Flow: Fast Diffusion for Gaussian Mixture Models [13.836464287004505]
シュロディンガーブリッジ (Schrodinger Bridges, SBs) は、有限時間で操る拡散過程であり、与えられた初期分布を、適切なコスト関数を最小化する。
そこで本研究では,低次元の問題を解決するための一組の実行可能なポリシーの解析的パラメトリゼーションを提案する。
本稿では,オートエンコーダの空間における画像から潜時変換,マルチマージ運動量SBを用いた細胞動態の学習など,低次元問題におけるこのアプローチの可能性を示す。
論文 参考訳(メタデータ) (2024-12-12T08:40:22Z) - DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
生成拡散モデルは、様々なクロスドメインアプリケーションで人気がある。
これらのモデルは複雑なネットワーク最適化問題に対処する上で有望である。
本稿では拡散モデルに基づく解生成という,拡散モデル生成のための新しいフレームワークを提案する。
論文 参考訳(メタデータ) (2024-08-13T07:56:21Z) - Distributionally Robust Model-based Reinforcement Learning with Large
State Spaces [55.14361269378122]
強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。
広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。
本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
論文 参考訳(メタデータ) (2023-09-05T13:42:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。