論文の概要: TSPDiffuser: Diffusion Models as Learned Samplers for Traveling Salesperson Path Planning Problems
- arxiv url: http://arxiv.org/abs/2406.02858v1
- Date: Wed, 5 Jun 2024 02:15:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 22:26:58.667367
- Title: TSPDiffuser: Diffusion Models as Learned Samplers for Traveling Salesperson Path Planning Problems
- Title(参考訳): TSPDiffuser:トラベリングセールスパーソンパス計画問題のための学習サンプリングとしての拡散モデル
- Authors: Ryo Yonetani,
- Abstract要約: 旅行セールスパーソンパス計画問題(TSPPP)のための新しいデータ駆動パスプランナを提案する。
障害物マップ内の目的地の集合を考慮に入れれば、最も短い衝突のない経路を効率的に見つけることが目的である。
我々は,TSPPP インスタンスの集合とその各ソリューション上で拡散モデルを訓練し,未知の問題インスタンスに対する可塑性経路を生成する。
- 参考スコア(独自算出の注目度): 7.566713416204861
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents TSPDiffuser, a novel data-driven path planner for traveling salesperson path planning problems (TSPPPs) in environments rich with obstacles. Given a set of destinations within obstacle maps, our objective is to efficiently find the shortest possible collision-free path that visits all the destinations. In TSPDiffuser, we train a diffusion model on a large collection of TSPPP instances and their respective solutions to generate plausible paths for unseen problem instances. The model can then be employed as a learned sampler to construct a roadmap that contains potential solutions with a small number of nodes and edges. This approach enables efficient and accurate estimation of traveling costs between destinations, effectively addressing the primary computational challenge in solving TSPPPs. Experimental evaluations with diverse synthetic and real-world indoor/outdoor environments demonstrate the effectiveness of TSPDiffuser over existing methods in terms of the trade-off between solution quality and computational time requirements.
- Abstract(参考訳): 本稿では,トラベリングセールスパーソンパス計画問題(TSPPP)を,障害に富んだ環境下で行う新しいデータ駆動型パスプランナーTSPDiffuserを提案する。
障害物マップ内の目的地の集合を考慮に入れれば、最も短い衝突のない経路を効率的に見つけることが目的である。
TSPDiffuser では,大量の TSPPP インスタンスとその各ソリューション上で拡散モデルを訓練し,未知の問題インスタンスに対する可塑性経路を生成する。
このモデルは学習したサンプルとして利用でき、少数のノードとエッジを持つ潜在的なソリューションを含むロードマップを構築することができる。
このアプローチにより、目的地間の移動コストを効率よく正確に推定することができ、TSPPPの解法における主要な計算課題に効果的に対処できる。
各種合成・実世界の屋内・屋外環境を用いた実験評価は,ソリューションの品質と計算時間とのトレードオフの観点から,既存の手法よりもTSPDiffuserの有効性を示す。
関連論文リスト
- Dynamical Measure Transport and Neural PDE Solvers for Sampling [77.38204731939273]
本研究では, 対象物へのトラクタブル密度関数の移動として, 確率密度からサンプリングする作業に取り組む。
物理インフォームドニューラルネットワーク(PINN)を用いて各偏微分方程式(PDE)の解を近似する。
PINNはシミュレーションと離散化のない最適化を可能にし、非常に効率的に訓練することができる。
論文 参考訳(メタデータ) (2024-07-10T17:39:50Z) - LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
経路計画はロボット工学と自律航法における基本的な科学的問題である。
A*やその変種のような伝統的なアルゴリズムは、パスの妥当性を保証することができるが、状態空間が大きくなるにつれて、計算とメモリの非効率が著しく低下する。
本稿では, A* の正確なパスフィニング能力と LLM のグローバルな推論能力とを相乗的に組み合わせた LLM ベースの経路計画法を提案する。
このハイブリッドアプローチは、特に大規模シナリオにおいて、パス妥当性の完全性を維持しながら、時間と空間の複雑さの観点からパスフィニング効率を向上させることを目的としている。
論文 参考訳(メタデータ) (2024-06-20T01:24:30Z) - MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation [80.47072100963017]
Amortized Pareto Front (MAP) を用いた新しい低演算アルゴリズム Model Merging を導入する。
MAPは、複数のモデルをマージするためのスケーリング係数のセットを効率的に識別し、関連するトレードオフを反映する。
また,タスク数が比較的少ないシナリオではベイジアンMAP,タスク数の多い状況ではNested MAPを導入し,計算コストを削減した。
論文 参考訳(メタデータ) (2024-06-11T17:55:25Z) - A Bi-Objective Approach to Last-Mile Delivery Routing Considering Driver Preferences [42.16665455951525]
MOVRP(Multi-Objective Vehicle Routing Problem)は、輸送・物流業界における複雑な最適化問題である。
本稿では,運転者の判断や操作者の嗜好を考慮した経路作成を目的としたMOVRPに対する新しいアプローチを提案する。
この目的に対処するための2つのアプローチとして,視覚的に魅力的な経路計画と,同様の経路を計画するための過去の運転行動のデータマイニングを評価した。
論文 参考訳(メタデータ) (2024-05-25T04:25:00Z) - 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) - Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
旅行購入問題(TPP)は幅広いアプリケーションにおいて重要な最適化問題である。
本稿では,ルート構築と購入計画を個別に扱う,深層強化学習(DRL)に基づく新しいアプローチを提案する。
メタラーニング戦略を導入することで、大規模なTPPインスタンス上で安定してポリシーネットワークをトレーニングすることができる。
論文 参考訳(メタデータ) (2024-04-03T05:32:10Z) - NNPP: A Learning-Based Heuristic Model for Accelerating Optimal Path Planning on Uneven Terrain [5.337162499594818]
本稿では,この縮小された検索空間内でのみ最適な経路をAstarのような基礎アルゴリズムで見つけることができるNNPPモデルを提案する。
NNPPモデルは、多くの事前注釈付き最適経路のデモから、スタート地点とゴール地点に関する情報とマップ表現を学習する。
新規地図上での経路計画のテキストカラー化が可能である。
論文 参考訳(メタデータ) (2023-08-09T08:31:05Z) - Vertex-based Networks to Accelerate Path Planning Algorithms [3.684936338492373]
本稿では,RT* のサンプリングプロセスを強化するため,頂点に基づくネットワークの利用を提案し,より効率的な経路計画手法を提案する。
我々は、関連するデータ不均衡問題に対処するために焦点損失を採用し、異なるマスキング構成を探索し、システム性能の実用的なトレードオフを決定する。
論文 参考訳(メタデータ) (2023-07-13T20:56:46Z) - Contextualizing MLP-Mixers Spatiotemporally for Urban Data Forecast at Scale [54.15522908057831]
本稿では,STTD予測を大規模に行うためのコンピュータ・ミクサーの適応版を提案する。
我々の結果は、この単純な効率の良いソリューションが、いくつかのトラフィックベンチマークでテストした場合、SOTAベースラインに匹敵する可能性があることを驚くほど示している。
本研究は, 実世界のSTTD予測において, 簡便な有効モデルの探索に寄与する。
論文 参考訳(メタデータ) (2023-07-04T05:19:19Z) - Multi-UAV Path Planning for Wireless Data Harvesting with Deep
Reinforcement Learning [18.266087952180733]
本稿では,データ収集ミッションを定義するシナリオパラメータの深い変化に適応できるマルチエージェント強化学習(MARL)手法を提案する。
提案するネットワークアーキテクチャにより,データ収集タスクを慎重に分割することで,エージェントが効果的に協調できることを示す。
論文 参考訳(メタデータ) (2020-10-23T14:59:30Z) - Congestion-aware Evacuation Routing using Augmented Reality Devices [96.68280427555808]
複数の目的地間でリアルタイムに個別の避難経路を生成する屋内避難のための渋滞対応ルーティングソリューションを提案する。
建物内の混雑分布をモデル化するために、ユーザエンド拡張現実(AR)デバイスから避難者の位置を集約して、オンザフライで取得した人口密度マップを用いる。
論文 参考訳(メタデータ) (2020-04-25T22:54:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。