論文の概要: Resource Constrained Pathfinding with A* and Negative Weights

• arxiv url: http://arxiv.org/abs/2503.11037v1
• Date: Fri, 14 Mar 2025 03:06:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-17 13:07:50.867659
• Title: Resource Constrained Pathfinding with A* and Negative Weights
• Title（参考訳）: A*および負の重みを持つ資源制約パスフィンディング
• Authors: Saman Ahmadi, Andrea Raith, Mahdi Jalili,
• Abstract要約: 制約付きパスフィニングはよく研究されているが、ネットワーク最適化の問題である。 本稿では,大規模ネットワークにおけるRCSPに取り組むために,A*に基づく新たなリソース制約付き検索フレームワークを提案する。 文献の最先端RCSPアルゴリズムと比較して最大2桁高速な性能を示す。
• 参考スコア（独自算出の注目度）: 8.899546103635938
• License:
• Abstract: Constrained pathfinding is a well-studied, yet challenging network optimisation problem that can be seen in a broad range of real-world applications. Pathfinding with multiple resource limits, which is known as the Resource Constrained Shortest Path Problem (RCSP), aims to plan a cost-optimum path subject to limited usage of resources. Given the recent advances in constrained and multi-criteria search with A*, this paper introduces a new resource constrained search framework on the basis of A* to tackle RCSP in large networks, even in the presence of negative cost and negative resources. We empirically evaluate our new algorithm on a set of large instances and show up to two orders of magnitude faster performance compared to state-of-the-art RCSP algorithms in the literature.
• Abstract（参考訳）: 制約付きパスフィンディングはよく研究されているが、様々な現実世界のアプリケーションで見られるネットワーク最適化の問題である。 資源制約最短経路問題 (Resource Constrained Shortest Path Problem, RCSP) として知られる複数の資源制限によるパスフィニングは、資源の使用制限によるコスト最適経路を計画することを目的としている。 本稿では,A*を用いた制約付き・複数基準検索の最近の進歩を踏まえ,負のコストと負のリソースが存在する場合でも,大規模ネットワークにおけるRCSPに取り組むために,A*に基づく新たなリソース制約付き検索フレームワークを提案する。 我々は,本アルゴリズムを大規模インスタンスの集合上で実証的に評価し,文献における最先端RCSPアルゴリズムと比較して最大2桁高速な性能を示す。

関連論文リスト

• Resource Constrained Pathfinding with Enhanced Bidirectional A* Search [10.100786663811666]
  本研究では,大規模ネットワークにおける高速かつ効率的なRCSP探索を実現するために,効率的なプルーニング戦略を用いた制約付き検索フレームワークを提案する。 その結果, 拡張されたフレームワークは, 最先端技術と比較して, 探索時間を大幅に短縮し, 最大2桁の高速化を達成できることが示唆された。
  論文  参考訳（メタデータ） (2024-12-18T14:29:40Z)
• Joint Admission Control and Resource Allocation of Virtual Network Embedding via Hierarchical Deep Reinforcement Learning [69.00997996453842]
  本稿では,仮想ネットワークの埋め込みにおいて,入出力制御と資源配分を併用して学習する深層強化学習手法を提案する。 HRL-ACRAは,受入率と長期平均収益の両面で,最先端のベースラインを上回っていることを示す。
  論文  参考訳（メタデータ） (2024-06-25T07:42:30Z)
• Enhanced Methods for the Weight Constrained Shortest Path Problem [18.567812400186092]
  WCSPP(Weight Constrained Shortest Path Problem)は、AIにおいてよく研究されているが、難しいトピックである。 本稿では, A* 探索に基づく WCSPP に対する2つの新しい解法を提案する。 我々は,大規模で現実的な問題事例の集合に対して,アルゴリズムの性能を実証的に評価した。
  論文  参考訳（メタデータ） (2022-07-29T15:32:45Z)
• Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality [57.91411772725183]
  本稿では,状態空間と動作空間が有限である場合のオフライン最短経路問題について考察する。 オフラインポリシ評価(OPE)とオフラインポリシ学習タスクの両方を扱うための,シンプルな値ベースアルゴリズムを設計する。 これらの単純なアルゴリズムの解析は、極小値に近い最悪のケース境界を示唆する強いインスタンス依存境界をもたらす。
  論文  参考訳（メタデータ） (2022-06-10T07:44:56Z)
• Evolutionary Optimization for Proactive and Dynamic Computing Resource Allocation in Open Radio Access Network [4.9711284100869815]
  Open Radio Access Network (O-RAN) におけるコンピュータリソースの自動割り当てを実現するためのインテリジェントな技術が求められている このリソース割り当て問題を解決するための既存の問題定式化は、リソースのキャパシティユーティリティを不適切な方法で定義しているため不適切である。 問題をよりよく記述した新しい定式化が提案されている。
  論文  参考訳（メタデータ） (2022-01-12T08:52:04Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  本研究では, 資源制約を満たすため, エージェントを安定な集団状態へ誘導する新しい手法を提案する。 提案手法は,ゲームラグランジアンの拡張によるリソース負荷に基づく分散リソース価格設定手法である。
  論文  参考訳（メタデータ） (2020-10-21T10:11:17Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。 本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-27T17:38:51Z)
• Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation [49.69139684065241]
  コンテキスト多重武装バンディット(MAB)は、様々な問題において最先端のパフォーマンスを達成する。 本稿では,階層型適応型文脈帯域幅法(HATCH)を提案する。
  論文  参考訳（メタデータ） (2020-04-02T17:04:52Z)
• RC-DARTS: Resource Constrained Differentiable Architecture Search [162.7199952019152]
  資源制約付き微分可能なアーキテクチャ探索法(RC-DARTS)を提案する。 RC-DARTS法は,モデルサイズが小さく,計算量も少ない,軽量なニューラルアーキテクチャを学習する。
  論文  参考訳（メタデータ） (2019-12-30T05:02:38Z)

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

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