論文の概要: Heuristic Search for Path Finding with Refuelling
- arxiv url: http://arxiv.org/abs/2309.10796v2
- Date: Mon, 24 Feb 2025 06:31:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-25 15:46:57.552040
- Title: Heuristic Search for Path Finding with Refuelling
- Title（参考訳）: 燃料補給による経路探索のためのヒューリスティック検索
- Authors: Shizhe Zhao, Anushtup Nandy, Howie Choset, Sivakumar Rathinam, Zhongqiang Ren,
- Abstract要約: ガスステーション問題(GSP)は,限られたガスタンクと限られた燃料補給装置を備えたロボットの開始から目標まで,最小限のコストの経路を求める。
本稿では,Refuel A$*$ (RF-A$*$) という検索アルゴリズムを開発し,まず最初に部分解を反復的に構築する。
RF-A$*$は最適解経路を見つけることが保証され、しばしば既存のアプローチの2倍から8倍の速度で走る。
- 参考スコア（独自算出の注目度）: 24.307418195475833
- License:
- Abstract: This paper considers a generalization of the Path Finding (PF) problem with refuelling constraints referred to as the Gas Station Problem (GSP). Similar to PF, given a graph where vertices are gas stations with known fuel prices, and edge costs are the gas consumption between the two vertices, GSP 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 GSP is polynomial-time solvable, it remains a challenge to quickly compute an optimal solution in practice since it requires 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 while leveraging dominance rules for pruning during planning. RF-A$^*$ is guaranteed to find an optimal solution and often runs 2 to 8 times faster than the existing approaches in large city maps with several hundreds of gas stations.
- Abstract（参考訳）: 本稿では,ガスステーション問題(GSP)と呼ばれる制約を補充した経路探索問題(PF)の一般化について考察する。
PFと同様に、頂点が既知の燃料価格を持つガソリンスタンドであるグラフとエッジコストが2つの頂点の間のガス消費であるグラフと異なり、GSPは、限られたガスタンクと限られた燃料補給停止を持つロボットの目標頂点までの最小コストの経路を求める。
GSPは多項式時間で解けるが、経路を同時に決定し、どこで停止するか、各停止で燃料を補給する必要があるため、実際は最適解を迅速に計算することは困難である。
本稿では,Refuel A$^*$ (RF-A$^*$) と呼ばれるヒューリスティックな探索アルゴリズムを開発した。
RF-A$^*$は最適な解を見つけることが保証されており、数百のガソリンスタンドを持つ大都市地図の既存手法の2倍から8倍の速度で走ることが多い。
関連論文リスト
- Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
パスワイズ法は、ペナライズされた推定器の完全な経路を効率的に計算することができる。
これらのアルゴリズムを離散時間で観測されたプロセスのペナル化推定に適用する。
論文 参考訳（メタデータ） (2024-12-05T10:38:29Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。