論文の概要: CAHC:A General Conflict-Aware Heuristic Caching Framework for Multi-Agent Path Finding

• arxiv url: http://arxiv.org/abs/2512.12243v2
• Date: Sat, 17 Jan 2026 09:48:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 08:17:40.327247
• Title: CAHC:A General Conflict-Aware Heuristic Caching Framework for Multi-Agent Path Finding
• Title（参考訳）: CAHC:マルチエージェントパス探索のための一般衝突対応ヒューリスティックキャッシングフレームワーク
• Authors: HT To, S Nguyen, NH Pham,
• Abstract要約: 我々は、状態と関連する制約コンテキストの両方に基づいて値をキャッシュする一般的なフレームワークであるtextbfCAHC(Conflict-Aware Heuristic Caching)を提案する。 カーライクロボットにおけるCL-CBSのケーススタディを通じてCAHCを実演し、コンフリクト対応キャッシングと適応ハイブリッドを併用したtextbfCARCHASE(Car-like Robot Conflict-Aware Heuristic Adaptive Search Enhancement)を提案する。 キーとなるイノベーションは、(1)制約が状態のコンテキストに影響を及ぼすことを効率的にエンコードするコンパクトなEmphconflict指紋、(2)ドメイン適応型指紋である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-Agent Path Finding (MAPF) algorithms, including those for car-like robots and grid-based scenarios, face significant computational challenges due to expensive heuristic calculations. Traditional heuristic caching assumes that the heuristic function depends only on the state, which is incorrect in constraint-based search algorithms (e.g., CBS, MAPF-LNS, MAP2) where constraints from conflict resolution make the search space context-dependent. We propose \textbf{CAHC} (Conflict-Aware Heuristic Caching), a general framework that caches heuristic values based on both state and relevant constraint context, addressing this fundamental limitation. We demonstrate CAHC through a case study on CL-CBS for car-like robots, where we combine conflict-aware caching with an adaptive hybrid heuristic in \textbf{CAR-CHASE} (Car-Like Robot Conflict-Aware Heuristic Adaptive Search Enhancement). Our key innovations are (1) a compact \emph{conflict fingerprint} that efficiently encodes which constraints affect a state's heuristic, (2) a domain-adaptable relevance filter using spatial, temporal, and geometric criteria, and (3) a modular architecture that enables systematic application to diverse MAPF algorithms. Experimental evaluation on 480 CL-CBS benchmark instances demonstrates a geometric mean speedup of 2.46$\times$ while maintaining solution optimality. The optimizations improve success rate from 77.9\% to 84.8\% (+6.9 percentage points), reduce total runtime by 70.1\%, and enable solving 33 additional instances. The framework's general architecture makes it applicable as a reliable optimization technique for MAP2, MAPF-LNS, and other constraint-based MAPF algorithms.
• Abstract（参考訳）: カーライクなロボットやグリッドベースのシナリオを含むMAPF(Multi-Agent Path Finding)アルゴリズムは、高価なヒューリスティックな計算のために重大な計算課題に直面している。 従来のヒューリスティックキャッシングでは、このヒューリスティック関数は、制約ベースの検索アルゴリズム(例えばCBS、MAPF-LNS、MAP2)で正しくない状態に依存していると仮定している。 我々は、状態と関連する制約コンテキストの両方に基づいてヒューリスティックな値をキャッシュする一般的なフレームワークである「textbf{CAHC} (Conflict-Aware Heuristic Caching)」を提案する。 カーライクロボットにおけるCL-CBSのケーススタディを通じてCAHCを実証し,コンフリクト対応キャッシングと適応型ハイブリッドヒューリスティック(Car-like Robot Conflict-Aware Heuristic Search Enhancement)を組み合わせた。 本研究では,(1)状態のヒューリスティックに影響を及ぼす制約を効率的に符号化するコンパクトな‘emph{conflict fingerprint’,(2)空間的,時間的,幾何学的基準を用いたドメイン適応型関連フィルタ,(3)多様なMAPFアルゴリズムに体系的な適用を可能にするモジュラーアーキテクチャを提案する。 480 CL-CBSベンチマークインスタンスに対する実験的評価は、解の最適性を維持しながら、幾何平均速度が2.46$\times$であることを示している。 最適化により、成功率は77.9\%から84.8\%(+6.9パーセント)に向上し、全体の実行時間を70.1\%削減し、33の追加インスタンスを解決できる。 このフレームワークの一般的なアーキテクチャは、MAP2、MAPF-LNS、その他の制約ベースのMAPFアルゴリズムの信頼性の高い最適化手法として適用することができる。

関連論文リスト

• DyACE: Dynamic Algorithm Co-evolution for Online Automated Heuristic Design with Large Language Model [12.490525543266807]
  非定常バイレベル制御問題としてDyACE(Dynamic Co-evolution)を導入する。 DyACEの中核となる要素はLook-Ahead Rollout Searchである。 結果は、DyACEが最先端の静的ベースラインを大幅に上回っていることを示している。
  論文  参考訳（メタデータ） (2026-03-07T06:46:53Z)
• Hyperparameter Optimization of Constraint Programming Solvers [2.4915743991417547]
  本稿では,CPMpyライブラリに組み込まれたハイパーパラメータの自動最適化フレームワークであるプローブ・アンド・ソルバアルゴリズムを紹介する。 このアルゴリズムを114の問題インスタンスに対して,ACEとChocoの2つの異なる制約解決器上で評価する。 その結果,ベイズ最適化を用いることで,解法のデフォルト設定よりも優れた性能が得られることがわかった。
  論文  参考訳（メタデータ） (2026-01-16T16:02:36Z)
• Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings [73.44599934855067]
  LookaHESは、動的で履歴に依存したコスト環境のために設計された非心筋BOフレームワークである。 LookaHESは、$H$-Entropy Searchのマルチステップ版と、パスワイズサンプリングとニューラルポリシー最適化を組み合わせたものだ。 私たちの革新は、構造化されたドメイン固有のアクションスペースを効果的にナビゲートするために、大きな言語モデルを含むニューラルポリシーの統合です。
  論文  参考訳（メタデータ） (2026-01-10T09:49:45Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  本稿では,高信頼領域を適応的にフィルタするBALLETというフレームワークを提案する。 理論的には、BALLETは探索空間を効率的に縮小することができ、標準BOよりも厳密な後悔を示すことができる。
  論文  参考訳（メタデータ） (2023-07-25T09:45:47Z)
• AutoSpace: Neural Architecture Search with Less Human Interference [84.42680793945007]
  現在のニューラルネットワークアーキテクチャ検索(NAS)アルゴリズムは、ネットワーク構築のための検索空間を設計するための専門知識と努力を必要とします。 探索空間を最適なものに進化させる新しい微分可能な進化フレームワークであるAutoSpaceを提案する。 学習した検索空間では、最近のNASアルゴリズムの性能は、以前手作業で設計した空間に比べて大幅に改善できる。
  論文  参考訳（メタデータ） (2021-03-22T13:28:56Z)
• ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding [86.40042104698792]
  スパース符号問題としてニューラルアーキテクチャ探索を定式化する。 実験では、CIFAR-10の2段階法では、検索にわずか0.05GPUしか必要としない。 本手法は,CIFAR-10とImageNetの両方において,評価時間のみのコストで最先端のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2020-10-13T04:34:24Z)
• Artificial Intelligence Assisted Collaborative Edge Caching in Small Cell Networks [19.605382256630538]
  本稿では、エッジノードにおける異種キャッシュモデルを持つユーザの異種コンテンツ嗜好について考察する。 複雑な制約問題を妥当な時間で効率的に解決する修正粒子群最適化(M-PSO)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-16T10:39:46Z)

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

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