論文の概要: Heuristic Search for Path Finding with Refuelling

• arxiv url: http://arxiv.org/abs/2309.10796v1
• Date: Tue, 19 Sep 2023 17:43:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-20 13:12:05.630018
• Title: Heuristic Search for Path Finding with Refuelling
• Title（参考訳）: 再給油による経路探索のヒューリスティック探索
• Authors: Anushtup Nandy, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset
• Abstract要約: 本稿では,Refuelling Path Finding (RF-PF) 問題と呼ばれる制約付きパスファインディング(PF)問題の一般化について考察する。 RF-PFは、限られた燃料補給停止数を持つロボットの開始から目標まで、最小限のコストパスを求める。 本稿では,関数によって導かれるゴールまで部分解を構成するRefuel A* (RF-A*) という探索アルゴリズムを開発する。
• 参考スコア（独自算出の注目度）: 27.63278352602436
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers a generalization of the Path Finding (PF) with refueling constraints referred to as the Refuelling Path Finding (RF-PF) problem. Just like PF, the RF-PF problem is defined over a graph, where vertices are gas stations with known fuel prices, and edge costs depend on the gas consumption between the corresponding vertices. RF-PF seeks a minimum-cost path from the start to the goal vertex for a robot with a limited gas tank and a limited number of refuelling stops. While RF-PF is polynomial-time solvable, it remains a challenge to quickly compute an optimal solution in practice since the robot needs to simultaneously determine the path, where to make the stops, and the amount to refuel at each stop. This paper develops a heuristic search algorithm called Refuel A* (RF-A* ) that iteratively constructs partial solution paths from the start to the goal guided by a heuristic function while leveraging dominance rules for state pruning during planning. RF-A* is guaranteed to find an optimal solution and runs more than an order of magnitude faster than the existing state of the art (a polynomial time algorithm) when tested in large city maps with hundreds of gas stations.
• Abstract（参考訳）: 本稿では,Refuelling Path Finding (RF-PF) 問題と呼ばれる再給油制約を伴うパスファインディング(PF)の一般化について考察する。 PFと同様に、RF-PF問題は、頂点が既知の燃料価格を持つガソリンスタンドであり、エッジコストは対応する頂点間のガス消費に依存するグラフ上で定義される。 RF-PFは、限られたガスタンクと限られた数の燃料補給停止を持つロボットの目標頂点までの最小コストパスを求める。 rf-pfは多項式時間で解くことができるが、ロボットは経路、停止場所、各停止時に燃料を補給する量を同時に決定する必要があるため、実際に最適な解を迅速に計算することは課題である。 本稿では,計画中の状態プルーニングにおける支配ルールを活用するとともに,ヒューリスティック関数によって導かれる解経路を始点からゴールまで反復的に構築する,Refuel A* (RF-A* ) と呼ばれるヒューリスティック探索アルゴリズムを開発する。 RF-A*は最適な解を見つけることが保証されており、数百のガソリンスタンドを持つ大都市マップでテストした場合、既存の最先端(多項式時間アルゴリズム)よりも桁違いに速く動作する。

関連論文リスト

• Two Completely Parameter-Free Alternating Gradient Projection Algorithms for Nonconvex-(strongly) Concave Minimax Problems [1.141545154221656]
  近年,ミニマックス問題の解法に注目が集まっている。 本稿では,ミニマックス問題を解くための2つの全く異なるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-31T06:54:24Z)
• A Quantum Inspired Bi-level Optimization Algorithm for the First Responder Network Design Problem [0.0]
  トルコの交通・インフラ省からの提案では、ファースト・レスポンダーズのみが使用する道路セグメントのサブセットを割り当てることになっている。 本稿では,この1次応答器ネットワーク設計問題に対する混合整数非線形プログラミングの定式化について述べる。 FRとエスキューパスのフローバランスの制約を用いて、部分的なグラバーベースを得るために、擬似非拘束バイナリ最適化(QUBO)モデルを用いる。
  論文  参考訳（メタデータ） (2024-01-23T03:22:05Z)
• Client Orchestration and Cost-Efficient Joint Optimization for NOMA-Enabled Hierarchical Federated Learning [55.49099125128281]
  半同期クラウドモデルアグリゲーションの下で非直交多重アクセス(NOMA)を実現するHFLシステムを提案する。 提案手法は,HFLの性能改善と総コスト削減に関するベンチマークよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-11-03T13:34:44Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with Data-Efficient Deep Reinforcement Learning [9.877261093287304]
  我々は、当初車両が補給所から離れた場所にあり、燃料の量が異なるミッション再計画問題について検討する。 そこで我々は,各部分ツアーに対する自己注意と,部分ツアーと残りのノード間のエンコーダ・デコーダの注意を組み込んだポリシーネットワークを構築した。 本稿では,複数の非重複サンプルのロールアウトに基づく局所的なミニバッチベースラインに,グリーディロールアウトベースラインを置き換えたREINFORCEアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-02T15:15:56Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Computation Offloading and Resource Allocation in F-RANs: A Federated Deep Reinforcement Learning Approach [67.06539298956854]
  フォグ無線アクセスネットワーク(フォグ無線アクセスネットワーク、F-RAN)は、ユーザのモバイルデバイス(MD)が計算タスクを近くのフォグアクセスポイント(F-AP)にオフロードできる有望な技術である。
  論文  参考訳（メタデータ） (2022-06-13T02:19:20Z)
• Constrained Shortest Path Search with Graph Convolutional Neural Networks [12.457788665461312]
  無人地上車両(AUGV)の計画はまだ課題である。 本稿では,与えられた連結グラフ上の必須ノードを用いた最短経路探索に着目した。 本稿では,制約に基づく解法とグラフ畳み込みニューラルネットワークを組み合わせたハイブリッドモデルを提案する。
  論文  参考訳（メタデータ） (2021-08-02T15:25:16Z)
• Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes [7.766921168069532]
  複数のロボット(MRPP)の経路計画は、ロボットが最初の位置から指定された目標位置までナビゲートできる非衝突経路を見つけるタスクを表します。 本稿では,既存の SAT ベースの MRPP アルゴリズムを,対象の Boolean 符号化を導出する各ロボットの候補経路の集合を分割することで拡張する。
  論文  参考訳（メタデータ） (2021-03-08T00:57:42Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Targeted free energy estimation via learned mappings [66.20146549150475]
  自由エネルギー摂動 (FEP) は60年以上前にズワンツィヒによって自由エネルギー差を推定する方法として提案された。 FEPは、分布間の十分な重複の必要性という厳しい制限に悩まされている。 目標自由エネルギー摂動(Targeted Free Energy Perturbation)と呼ばれるこの問題を緩和するための1つの戦略は、オーバーラップを増やすために構成空間の高次元マッピングを使用する。
  論文  参考訳（メタデータ） (2020-02-12T11:10:00Z)

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

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