論文の概要: Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
- arxiv url: http://arxiv.org/abs/2606.18730v1
- Date: Wed, 17 Jun 2026 06:17:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-18 17:16:51.031996
- Title: Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
- Title（参考訳）: 移動障害物を有する移動目標トラベリングセールスマン問題の2相二値探索
- Authors: Allen George Philip, Anoop Bhat, Sivakumar Rathinam, Howie Choset,
- Abstract要約: 移動障害物を用いた移動目標トラベリングセールスマン問題(MT-TSP-MO)について検討する。
本稿では,市販の解法を用いて解けるMICP(Mixed-Integer Conic Programming)の定式化と,高速でスケーラブルな2相二値探索(TPBS)アルゴリズムを提案する。
我々は,最大40の目標と40の障害を持つ幅広い問題インスタンスに対して,既存のベースラインアルゴリズムに対するアプローチを評価した。
- 参考スコア（独自算出の注目度）: 20.81107528768337
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum cost trajectory for an agent that departs from a static depot, visits a set of moving targets, each within one of their assigned time windows, and returns to the depot. In this article, we study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), a generalization of the MT-TSP where the agent trajectory must avoid moving obstacles. We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers, as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm that computes high-quality feasible solutions for the problem. We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles. The results demonstrate that both the proposed methods significantly outperform the baseline with respect to success rates, solution costs, and computation time.
- Abstract（参考訳）: 移動目標トラベリングセールスマン問題(MT-TSP)は、静的補給所から出発し、割り当てられた時間窓の1つ内で移動目標のセットを訪れ、補給所に戻るエージェントの最小コストの軌跡を求める。
本稿では,MT-TSPを一般化した移動目標トラベリングセールスマン問題(MT-TSP-MO)について検討する。
本稿では,市販の解法を用いて解けるMICP(Mixed-Integer Conic Programming)の定式化と,高速でスケーラブルな2相二値探索(TPBS)アルゴリズムを提案する。
我々は,最大40の目標と40の障害を持つ幅広い問題インスタンスに対して,既存のベースラインアルゴリズムに対するアプローチを評価した。
その結果, 提案手法は, 成功率, ソリューションコスト, 計算時間に関して, ベースラインを著しく上回ることがわかった。
関連論文リスト
- NaviFormer: A Deep Reinforcement Learning Transformer-like Model to Holistically Solve the Navigation Problem [53.70554593151033]
NaviFormerは、高レベル経路と低レベル軌道の両方を予測することによって、グローバルナビゲーション問題を解決する深層強化学習モデルである。
結果は,各サブプロブレムの制約や難易度を理解することができるため,NaviFormerの競合精度を示す。
計算速度が優れていることは、リアルタイムのミッションに適していることを証明している。
論文 参考訳（メタデータ） (2026-04-18T11:32:34Z) - Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity [24.447439182269974]
移動目標車両ルーティング問題(MT-VRP)は、一連の移動目標を迎撃する複数のエージェントの軌跡を求める。
MT-VRP に対して,Relaxed Continuity (BPRC) を用いたブランチ・アンド・プライスアルゴリズムを導入する。
提案アルゴリズムは, これまでの研究結果から, ベースラインよりも桁違いに高速な最適解を求める。
論文 参考訳（メタデータ） (2026-02-28T14:09:54Z) - LDC-MTL: Balancing Multi-Task Learning through Scalable Loss Discrepancy Control [48.98651927356094]
マルチタスク学習(MTL)は、複数のタスクを同時に学習する能力に広く採用されている。
両レベル最適化の観点から定式化されたMDLの簡易かつスケーラブルな損失分散制御手法であるLCC-MTLを提案する。
提案手法は2つの重要な要素を包含する: (i) 細粒度損失分散制御のための2レベル定式化, (ii) 時間とメモリを$mathcalO(1)$でしか必要としないスケーラブルな1次2レベルアルゴリズム。
論文 参考訳（メタデータ） (2025-02-12T17:18:14Z) - A Meta-Engine Framework for Interleaved Task and Motion Planning using Topological Refinements [51.54559117314768]
タスク・アンド・モーション・プランニング(タスク・アンド・モーション・プランニング、TAMP)は、自動化された計画問題の解決策を見つけるための問題である。
本稿では,TAMP問題のモデル化とベンチマークを行うための,汎用的でオープンソースのフレームワークを提案する。
移動エージェントと複数のタスク状態依存障害を含むTAMP問題を解決する革新的なメタ技術を導入する。
論文 参考訳（メタデータ） (2024-08-11T14:57:57Z) - iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning [8.747306544853961]
MTSP(Min-Max Multiple Traveling Salesman)問題の検討
目標は、最長ツアーの長さを最小化しながら、各エージェントが一括してすべての都市を訪れるツアーを見つけることである。
我々は、命令型MTSP(iMTSP)と呼ばれる、新しい自己教師型双方向エンドツーエンド学習フレームワークを導入する。
論文 参考訳（メタデータ） (2024-05-01T02:26:13Z) - A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets [27.63278352602436]
本稿では,移動目標トラベリングセールスマン問題(MT-TSP)の最適解を求める新しい定式化を提案する。
問題は、補給所から始まるエージェントの最も短い経路を見つけ、割り当てられた時間ウィンドウ内で1度だけ移動対象のセットを訪れ、補給所に戻ることである。
MT-TSPのためのMICP(Mixed Conic Program)の定式化について検討した。
論文 参考訳（メタデータ） (2024-03-07T22:03:36Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in
Complex Environments [55.204450019073036]
本稿では,倉庫環境における移動ロボットのためのタスク割り当てと分散ナビゲーションアルゴリズムを提案する。
本稿では,共同分散タスク割り当てとナビゲーションの問題について考察し,それを解決するための2段階のアプローチを提案する。
ロボットの衝突のない軌道の計算では,タスク完了時間において最大14%の改善と最大40%の改善が観察される。
論文 参考訳（メタデータ） (2022-09-07T00:35:27Z) - Pruning Self-attentions into Convolutional Layers in Single Path [89.55361659622305]
ビジョントランスフォーマー(ViT)は、様々なコンピュータビジョンタスクに対して印象的なパフォーマンスを実現している。
トレーニング済みのViTを効率よく自動圧縮するSPViT(Single-Path Vision Transformer pruning)を提案する。
われわれのSPViTはDeiT-Bで52.0%のFLOPをトリミングできる。
論文 参考訳（メタデータ） (2021-11-23T11:35:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。