論文の概要: 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*は最適な解を見つけることが保証されており、数百のガソリンスタンドを持つ大都市マップでテストした場合、既存の最先端(多項式時間アルゴリズム)よりも桁違いに速く動作する。

関連論文リスト

• Memetic Search for Green Vehicle Routing Problem with Private Capacitated Refueling Stations [25.615777593601262]
  本稿では,GVRP-PCAFSを解くために,制約付きツアーセグメンテーション(SCTS)と効率的なローカルサーチ(ELS)を分離した新しいメメティックアルゴリズムMETSを提案する。 グローバルサーチでは,SCTS戦略は巨大ツアーを分割して多様なソリューションを生成し,総合的なフィットネス評価機能によって探索プロセスが導かれる。 局所探索のために、ESSは一定時間移動評価機構を備えた調整された移動演算子を導入し、大規模溶液近傍の効率的な探索を可能にする。
  論文  参考訳（メタデータ） (2025-04-06T15:52:49Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• 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)
• Joint Gaze-Location and Gaze-Object Detection [62.69261709635086]
  現在、フレームガウン位置検出(GL-D)とガウンオブジェクト検出(GO-D)は2つの異なるタスクである。 本稿では,検出後の視線を合理化するために,検出後の下線Gazeを短縮したGTRを提案する。 GTRはGazeFollowingで12.1mAP、GL-DでVideoAttentionTargetで18.2mAP、GO-Dで19mAP向上を達成した。
  論文  参考訳（メタデータ） (2023-08-26T12:12:24Z)
• 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)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• Machine-learning-based arc selection for constrained shortest path problems in column generation [5.08128537391027]
  本研究では,機械学習に基づく新しい価格アルゴリズムを提案する。 目的は、ネットワークのサイズを小さくし、PPを加速することであり、線形緩和溶液の一部となる確率の高い弧のみを保持することである。 この方法は、公共交通機関における車両と乗員のスケジューリング問題と、時間窓による車両のルーティング問題という2つの特定の問題に適用されている。
  論文  参考訳（メタデータ） (2022-01-07T16:49:12Z)
• 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)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)
• Targeted free energy estimation via learned mappings [66.20146549150475]
  自由エネルギー摂動 (FEP) は60年以上前にズワンツィヒによって自由エネルギー差を推定する方法として提案された。 FEPは、分布間の十分な重複の必要性という厳しい制限に悩まされている。 目標自由エネルギー摂動(Targeted Free Energy Perturbation)と呼ばれるこの問題を緩和するための1つの戦略は、オーバーラップを増やすために構成空間の高次元マッピングを使用する。
  論文  参考訳（メタデータ） (2020-02-12T11:10:00Z)
• Modeling and solving the multimodal car- and ride-sharing problem [0.0]
  マルチモーダルカー・ライドシェアリング問題(MMCRP)を紹介する。 車両のプールは一連の乗車要求をカバーするために使用され、発見されていない要求は他の交通手段に割り当てられる。 カラム生成に基づく2層分解アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-15T09:43:55Z)

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

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