論文の概要: Multi-Agent Route Planning as a QUBO Problem

• arxiv url: http://arxiv.org/abs/2602.07913v1
• Date: Sun, 08 Feb 2026 11:18:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.868815
• Title: Multi-Agent Route Planning as a QUBO Problem
• Title（参考訳）: QUBO問題としてのマルチエージェント経路計画
• Authors: Renáta Rusnáková, Martin Chovanec, Juraj Gazda,
• Abstract要約: 本稿では、形式的な問題定義を与え、重み付き集合パッケージ問題から減算してNP硬度を証明し、二次的非制約二項最適化の定式化を導出する。 単一のペナルティパラメータがカバレッジオーバーラップトレードオフを制御する。 バルセロナでの最大10万台の車両による実験では、カバーオーバーラップの明確な膝が明らかになった。
• 参考スコア（独自算出の注目度）: 0.39325957466009204
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-Agent Route Planning considers selecting vehicles, each associated with a single predefined route, such that the spatial coverage of a road network is increased while redundant overlaps are limited. This paper gives a formal problem definition, proves NP-hardness by reduction from the Weighted Set Packing problem, and derives a Quadratic Unconstrained Binary Optimization formulation whose coefficients directly encode unique coverage rewards and pairwise overlap penalties. A single penalty parameter controls the coverage-overlap trade-off. We distinguish between a soft regime, which supports multi-objective exploration, and a hard regime, in which the penalty is strong enough to effectively enforce near-disjoint routes. We describe a practical pipeline for generating city instances, constructing candidate routes, building the QUBO matrix, and solving it with an exact mixed-integer solver (Gurobi), simulated annealing, and D-Wave hybrid quantum annealing. Experiments on Barcelona instances with up to 10 000 vehicles reveal a clear coverage-overlap knee and show that Pareto-optimal solutions are mainly obtained under the hard-penalty regime, while D-Wave hybrid solvers and Gurobi achieve essentially identical objective values with only minor differences in runtime as problem size grows.
• Abstract（参考訳）: マルチエージェント経路計画では、道路網の空間被覆が増加し、重複の重複が制限されるような、1つの事前定義された経路に関連付けられた選択車両について検討する。 本稿では,重み付き集合パッケージ問題から減算してNP硬度を証明し,一意のカバレッジ報酬を直接符号化し,ペアの重なり合うペナルティの係数を導出する二次的非制約二項最適化の定式化を導出する。 単一のペナルティパラメータがカバレッジオーバーラップトレードオフを制御する。 我々は,多目的探索を支援するソフトレジームと,そのペナルティが十分強く,近接する経路を効果的に実施できるハードレジームとを区別する。 本稿では,都市インスタンスの生成,候補経路の構築,QUBO行列の構築,正確な混合整数解法(Gurobi),シミュレートアニール,D-Waveハイブリッド量子アニールによる解法について述べる。 最大10万台の車両を持つバルセロナのインスタンスの実験では、カバーオーバーラップの明確な膝が明らかに示され、パレート最適化ソリューションが主にハード・ペナルティ・レシエーションの下で得られることを示し、一方、D-Waveハイブリッド・ソルバとグロビは、問題のサイズが大きくなるにつれて、本質的に同一の客観的な値を得る。

関連論文リスト

• Assignment-Routing Optimization: Solvers for Problems Under Constraints [0.0]
  我々は、アイテムを1対1でプレースホルダーに割り当てなければならないJRA(Joint Routing-Assignment)問題について検討する。 よりリッチな制約付きパッケージング計画シナリオに適した解法を開発した。 以上の結果から, ロボット包装, 運動計画, 複合物流におけるMIPに基づくJRA最適化の実用性を強調した。
  論文  参考訳（メタデータ） (2025-12-21T06:32:31Z)
• Rich Vehicle Routing Problem in Disaster Management enabling Temporally-causal Transhipments across Multi-Modal Transportation Network [1.1470070927586018]
  地理的に分散した車両基地に複数台の異種車両を配置し、異なる交通手段を利用できるような、豊富な車両経路問題も検討されている。 この問題は、車両経路の等間隔を最小化することで災害応答時間を最適化する現実的な要件から生じる。 提案手法の優位性は,Mixed-Integer Linear Programmingの定式化によって実証された。
  論文  参考訳（メタデータ） (2025-09-16T16:37:18Z)
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  マルチロボット運動計画(MPMP)は、共有された連続作業空間で動作する複数のロボットのための軌道を生成する。 離散マルチエージェント探索(MAPF)法は,その拡張性から広く採用されているが,粗い離散化の軌道品質は高い。 本稿では、制約付き生成拡散モデルを用いた離散MAPF解法を導入することにより、2つのアプローチの限界に対処する。
  論文  参考訳（メタデータ） (2025-08-27T17:59:36Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。 我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
  論文  参考訳（メタデータ） (2025-03-01T21:25:21Z)
• Joint Transmit and Pinching Beamforming for Pinching Antenna Systems (PASS): Optimization-Based or Learning-Based? [89.05848771674773]
  MISO (Multiple-input Single-output) フレームワークを提案する。 それは複数の導波路で構成されており、多数の低コストアンテナ(PA)を備えている。 PAの位置は、大規模パスと空間の両方にまたがるように再構成することができる。
  論文  参考訳（メタデータ） (2025-02-12T18:54:10Z)
• Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models [57.45019514036948]
  MAPF(Multi-Agent Path Finding)は、ロボット工学における基本的な問題である。 連続空間におけるMAPFの拡散モデルと制約付き最適化を統合する新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-12-23T21:27:19Z)
• Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection [8.202492922523591]
  問題は、旅行予算が限られている検査車両に定式化されている。 この問題の最適解は、線形計画法(ILP)によって解決される。 これらのアルゴリズムは、電力線セグメントを電気変電所で検査する実世界のシナリオで実証される。
  論文  参考訳（メタデータ） (2023-02-02T15:59:46Z)
• Multi-Agent Chance-Constrained Stochastic Shortest Path with Application to Risk-Aware Intelligent Intersection [15.149982804527182]
  既存の自動交差点の深刻な課題は、運転環境や人間駆動車からの不確実性の検出と推論にある。 自動運転車(AV)と人間駆動車(HV)のためのリスク対応知的交差点システムを提案する。
  論文  参考訳（メタデータ） (2022-10-03T06:49:23Z)
• Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
  絡み合いルーティングは、2つの任意のノード間のリモート絡み合い接続を確立する。 量子ネットワークにおける複数のソース・デスティネーション(SD)ペアの忠実性を保証するために、精製可能な絡み合わせルーティング設計を提案する。
  論文  参考訳（メタデータ） (2021-11-15T14:07:22Z)

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

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