論文の概要: Hybrid Quantum-Classical Multi-Agent Pathfinding
- arxiv url: http://arxiv.org/abs/2501.14568v1
- Date: Fri, 24 Jan 2025 15:20:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-27 14:58:06.384953
- Title: Hybrid Quantum-Classical Multi-Agent Pathfinding
- Title(参考訳): ハイブリッド量子古典多エージェントパスフィニング
- Authors: Thore Gerlach, Loong Kuan Lee, Frédéric Barbaresco, Nico Piatkowski,
- Abstract要約: MAPF(Multi-Agent Path Finding)は、特定の目標地点に到達するために共有空間をナビゲートする複数のエージェントに対して、競合のない経路を決定することに焦点を当てている。
分岐・カット・アンド・プライズに基づく最初の最適量子古典型MAPFアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 2.5424058500941453
- License:
- Abstract: Multi-Agent Path Finding (MAPF) focuses on determining conflict-free paths for multiple agents navigating through a shared space to reach specified goal locations. This problem becomes computationally challenging, particularly when handling large numbers of agents, as frequently encountered in practical applications like coordinating autonomous vehicles. Quantum computing (QC) is a promising candidate in overcoming such limits. However, current quantum hardware is still in its infancy and thus limited in terms of computing power and error robustness. In this work, we present the first optimal hybrid quantum-classical MAPF algorithm which is based on branch-and-cut-and-prize. QC is integrated by iteratively solving QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our approach dominates previous QUBO formulations and baseline MAPF solvers.
- Abstract(参考訳): MAPF(Multi-Agent Path Finding)は、特定の目標地点に到達するために共有空間をナビゲートする複数のエージェントに対して、競合のない経路を決定することに焦点を当てている。
この問題は、特に多数のエージェントを扱う場合、特に自動運転車の調整のような実践的な応用で頻繁に発生するように、計算的に困難になる。
量子コンピューティング(QC)はそのような限界を克服する上で有望な候補である。
しかし、現在の量子ハードウェアはまだ初期段階であり、計算能力とエラーの堅牢性には限界がある。
本研究では,分岐・カット・アンド・プライズに基づく最初の最適量子古典型MAPFアルゴリズムを提案する。
QCは競合グラフに基づいてQUBO問題を反復的に解くことで統合される。
実際の量子ハードウェアの実験とベンチマークデータによる結果から,本手法が従来のQUBOの定式化とベースラインMAPFの解法に支配的であることが示唆された。
関連論文リスト
- Benchmarking Quantum Annealers with Near-Optimal Minor-Embedded Instances [0.0]
本稿では,D-Wave Quantum Annealersに関連付けられた準最適部分埋め込みマッピングを用いてグラフインスタンスを生成するための新しいプロトコルを確立する。
この手法を用いて、制約のない最適化問題の大規模インスタンス上でQAをベンチマークし、QPUの性能を効率的な古典的解法と比較する。
論文 参考訳(メタデータ) (2024-05-02T15:19:39Z) - Quantum Multi-Agent Reinforcement Learning for Aerial Ad-hoc Networks [0.19791587637442667]
本稿では,航空通信のユースケースを提示し,それを解くためのハイブリッド量子古典型MLアルゴリズムを提案する。
その結果,古典的アルゴリズムに匹敵する量子化解の性能はわずかに向上した。
これらの有望な結果は、産業関連複雑なユースケースに対するQMARLの可能性を示している。
論文 参考訳(メタデータ) (2024-04-26T15:57:06Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳(メタデータ) (2024-02-26T09:32:07Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - Multiple Target Tracking and Filtering using Bayesian Diabatic Quantum
Annealing [3.6944296923226316]
本稿では、多目的データアソシエーション(MTDA)と追跡問題と呼ばれるNPハード問題を解くためのハイブリッド量子/古典的アルゴリズムを提案する。
これはベイズハイブリッド量子古典的多重目標追跡フィルタの最初の実演かもしれない。
論文 参考訳(メタデータ) (2022-09-01T17:28:48Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳(メタデータ) (2022-05-24T03:49:10Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Towards Multi-Agent Reinforcement Learning using Quantum Boltzmann
Machines [2.015864965523243]
我々は、より困難な問題を解決するために、オリジナルの概念の拡張を提案する。
我々は、経験的なリプレイバッファを追加し、ターゲットとポリシーの値を近似するために異なるネットワークを使用します。
量子サンプリングは、強化学習タスクには有望な方法であることが証明されているが、現在はQPUサイズによって制限されている。
論文 参考訳(メタデータ) (2021-09-22T17:59:24Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳(メタデータ) (2021-05-06T17:59:38Z) - Electronic structure with direct diagonalization on a D-Wave quantum
annealer [62.997667081978825]
本研究は、D-Wave 2000Q量子アニール上の分子電子ハミルトニアン固有値-固有ベクトル問題を解くために、一般量子アニール固有解法(QAE)アルゴリズムを実装した。
そこで本研究では,D-Waveハードウェアを用いた各種分子系における基底および電子励起状態の取得について述べる。
論文 参考訳(メタデータ) (2020-09-02T22:46:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。