論文の概要: WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained
Tours with Dubins vehicle
- arxiv url: http://arxiv.org/abs/2002.00811v1
- Date: Mon, 3 Feb 2020 15:06:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-04 08:11:38.382504
- Title: WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained
Tours with Dubins vehicle
- Title（参考訳）: WiSM: Windowsing Surrogate Model for Evaluation of Curvature-Constrained Tours with Dubins Vehicle
- Authors: Jan Drchal and Jan Faigl and Petr V\'a\v{n}a
- Abstract要約: Dubins Tours は Dubins Traveling Salesman Problem (DTSP) の解である。
DTSPは、曲率に制約のある最短経路を決定する最適化ルーティング問題の変種である。
我々のアルゴリズムは、他の最先端のDTSPソルバよりも大幅にスケール可能であることを示す。
- 参考スコア（独自算出の注目度）: 3.248584983235657
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Dubins tours represent a solution of the Dubins Traveling Salesman Problem
(DTSP) that is a variant of the optimization routing problem to determine a
curvature-constrained shortest path to visit a set of locations such that the
path is feasible for Dubins vehicle, which moves only forward and has a limited
turning radius. The DTSP combines the NP-hard combinatorial optimization to
determine the optimal sequence of visits to the locations, as in the regular
TSP, with the continuous optimization of the heading angles at the locations,
where the optimal heading values depend on the sequence of visits and vice
versa. We address the computationally challenging DTSP by fast evaluation of
the sequence of visits by the proposed Windowing Surrogate Model (WiSM) which
estimates the length of the optimal Dubins path connecting a sequence of
locations in a Dubins tour. The estimation is sped up by a regression model
trained using close to optimum solutions of small Dubins tours that are
generalized for large-scale instances of the addressed DTSP utilizing the
sliding window technique and a cache for already computed results. The reported
results support that the proposed WiSM enables a fast convergence of a
relatively simple evolutionary algorithm to high-quality solutions of the DTSP.
We show that with an increasing number of locations, our algorithm scales
significantly better than other state-of-the-art DTSP solvers.
- Abstract（参考訳）: Dubins Tours は、最適化ルーティング問題の変種である Dubins Traveling Salesman Problem (DTSP) の解であり、経路が前方にしか移動せず、旋回半径が制限された Dubins vehicle に対して可能となるような、曲率に制約のある最短経路を決定する。
dtspはnp-hard combinatorial optimization(np-hard combinatorial optimization)を組み合わせることで、通常のtspのように、位置への訪問の最適なシーケンスを決定する。
提案手法であるWindowing Surrogate Model (WiSM) を用いて,Dubinsツアーの行程を接続する最適なDubinsパスの長さを推定する。
この推定は,スライディングウインドウ手法とキャッシュを用いたDTSPの大規模インスタンスに対して一般化された,小型のDubinsツアーの最適に近い解を用いて訓練された回帰モデルによって高速化される。
報告された結果から,提案したWiSMは比較的単純な進化的アルゴリズムをDTSPの高品質な解に高速に収束させることができることがわかった。
位置が増加するにつれて、我々のアルゴリズムは他の最先端のDTSP解法よりも大幅にスケールすることを示す。
関連論文リスト
- TSPDiffuser: Diffusion Models as Learned Samplers for Traveling Salesperson Path Planning Problems [7.566713416204861]
旅行セールスパーソンパス計画問題(TSPPP)のための新しいデータ駆動パスプランナを提案する。
障害物マップ内の目的地の集合を考慮に入れれば、最も短い衝突のない経路を効率的に見つけることが目的である。
我々は,TSPPP インスタンスの集合とその各ソリューション上で拡散モデルを訓練し,未知の問題インスタンスに対する可塑性経路を生成する。
論文 参考訳（メタデータ） (2024-06-05T02:15:55Z) - Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
本稿では,旅行セールスマン問題(TSP)の学習方法を提案する。
1対1のピックアップ・アンド・デリバリノードのシーケンスで一番短いツアーを見つける。
PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
論文 参考訳（メタデータ） (2024-04-17T15:05:51Z) - Keypoint-Guided Optimal Transport [85.396726225935]
最適マッチングを探索するリレーション保存(KPG-RL)によるキーポイント誘導モデルを提案する。
提案した KPG-RL モデルはシンクホーンのアルゴリズムで解くことができ、異なる空間で分布がサポートされている場合でも適用可能である。
二重KPG-RLからの学習された輸送計画に基づき、ターゲット領域にソースデータを転送する新しい多様体バリ中心射影を提案する。
論文 参考訳（メタデータ） (2023-03-23T08:35:56Z) - Deep Declarative Dynamic Time Warping for End-to-End Learning of
Alignment Paths [54.53208538517505]
本稿では、動的時間ワープ(DTW)による時間的アライメントステップを含む時系列データのエンドツーエンド学習モデルについて述べる。
そこで我々は,2レベル最適化とDecDTWと呼ばれる深層宣言ネットワークに基づくDTW層を提案する。
この特性は、下流損失関数が最適アライメントパス自身で定義されるアプリケーションに特に有用であることを示す。
論文 参考訳（メタデータ） (2023-03-19T21:58:37Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - DAG Learning on the Permutahedron [33.523216907730216]
本稿では,観測データから潜在有向非巡回グラフ(DAG)を発見するための連続最適化フレームワークを提案する。
提案手法は、置換ベクトル(いわゆるペルムタヘドロン)のポリトープを最適化し、位相的順序付けを学習する。
論文 参考訳（メタデータ） (2023-01-27T18:22:25Z) - Event-Based Feature Tracking in Continuous Time with Sliding Window
Optimization [55.11913183006984]
イベントカメラにおける連続時間特徴追跡のための新しい手法を提案する。
時空における推定軌道に沿って事象を整列させることによって特徴を追跡する。
提案するスライディングウインドウB-スプライン最適化が,より長く,より正確な特徴トラックにつながることを実験的に確認した。
論文 参考訳（メタデータ） (2021-07-09T16:41:20Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳（メタデータ） (2021-05-05T03:36:00Z) - Lifted Disjoint Paths with Application in Multiple Object Tracking [39.205794818196395]
この問題は整数多成分流と3-SATの低減によってNPハードであることが示される。
高品質なLP-レラクセーションを生成する線形不等式をいくつか提案する。
昇降経路トラッカーは入力検出に関してほぼ最適に割り振られる。
論文 参考訳（メタデータ） (2020-06-25T16:49:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。