日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

経路計画arXiv:2410.08627

散らかして逃げ切れ:円配置を伴う巡回セールスマン問題

Making a Complete Mess and Getting Away with it: Traveling Salesperson Problems with Circle Placement Variants

シェア:XThreadsFacebookLINEはてブBluesky

訪問した各地点の隣に円形障害物を置く制約下で、有効な閉路が存在する最大半径と最小巡回コストを求める問題(TSP-CP)を定式化し、Dubins車両版や自己消去グラフ上のTSPを含む新解法を提案した。

著者: David Woller, Masoumeh Mansouri, Miroslav Kulich

分類: cs.RO

原文アブストラクト

This paper explores a variation of the Traveling Salesperson Problem, where the agent places a circular obstacle next to each node once it visits it. Referred to as the Traveling Salesperson Problem with Circle Placement (TSP-CP), the aim is to maximize the obstacle radius for which a valid closed tour exists and then minimize the tour cost. The TSP-CP finds relevance in various real-world applications, such as harvesting, quarrying, and open-pit mining. We propose several novel solvers to address the TSP-CP, its variant tailored for Dubins vehicles, and a crucial subproblem known as the Traveling Salesperson Problem on self-deleting graphs (TSP-SD). Our extensive experimental results show that the proposed solvers outperform the current state-of-the-art on related problems in solution quality.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  4. 4GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

OZ GAMING(GPU搭載BTOゲーミングPC)

OZ GAMING(GPU搭載BTOゲーミングPC)の公式広告バナーOZ GAMINGで完成品PCを見る ↗
PR本紙発行元 EmplifAI