日本フィジカルAI新聞

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

学習支援オンラインアルゴリズムarXiv:2601.13494

直線上のオンライン巡回修理人問題に対する学習支援アルゴリズム

Learning-Augmented Online TRP on a Line

シェア:XThreadsFacebookLINEはてブBluesky

直線上のオンライン巡回修理人問題において、機械学習によるリクエスト位置の予測を活用する学習支援フレームワークを初めて適用し、予測が正確な場合に競合比2+√3を達成する決定論的アルゴリズムを提案した。

詳しい要約

1. どんなもの?

- オンラインtraveling repairperson problem (TRP) on a lineをlearning-augmented frameworkで研究。 - リクエストの位置予測が事前に与えられるが、到着時刻はオンラインで未知。 - 目的はリクエストの完了時刻の和(または平均)を最小化。 - 予測が完全な場合と誤差がある場合の競合比を解析。

2. 先行研究と比べてどこがすごい?

- 従来のオンラインTRP on a lineでは、決定論的アルゴリズムの競合比下界は1+√2≈2.414、上界は4。 - 本研究はlearning-augmented frameworkにおける初の結果。 - 予測が完全な場合に(2+√3)≈3.732-competitiveな決定論的アルゴリズムを設計。 - 予測誤差δがある場合でもmin{3.732+4δ,4}-competitiveを達成。 - また、3-competitive下界を確立し、これは元のモデルにも拡張。

3. 技術・手法の肝は?

- 予測モデル:各リクエストの位置予測が事前に与えられるが、到着時刻は未知。 - 決定論的アルゴリズムを設計し、予測が完全な場合の競合比を保証。 - 予測誤差δを考慮し、競合比がmin{3.732+4δ,4}となることを証明。 - 下界の証明には3-competitive下界を導出。

4. どうやって有効だと検証した?

- 理論的な競合比の解析により、アルゴリズムの性能を保証。 - 予測が完全な場合と不完全な場合の競合比を数学的に証明。 - 下界と上界の一致を示す。

5. 議論はある?

- 予測誤差δが競合比に与える影響を明示。 - 予測が完全な場合でも競合比は3.732であり、従来の下界2.414より大きい。 - 予測の有用性と限界について議論の余地がある。 - 他のオンライン問題への拡張可能性。

6. 次に読むべき論文は?

- 元のオンラインTRP on a lineの研究(競合比下界1+√2、上界4)。 - learning-augmented frameworkの他の問題への応用(例:online TSP、online scheduling)。 - 予測誤差を考慮したオンラインアルゴリズムの設計手法。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Swapnil Guragain, Gokarna Sharma

分類: cs.DS, cs.RO

原文アブストラクト

We study the online traveling repairperson problem on a line within the recently proposed learning-augmented framework, which provides predictions on the requests to be served via machine learning. In the original model (with no predictions), there is a stream of requests released over time along the line. The goal is to minimize the sum (or average) of the completion times of the requests. In the original model, the state-of-the-art competitive ratio lower bound is $1+\sqrt{2} > 2.414$ for any deterministic algorithm and the state-of-the-art competitive ratio upper bound is 4 for a deterministic algorithm. Our prediction model involves predicted positions, possibly error-prone, of each request in the stream known a priori but the arrival times of requests are not known until their arrival. We first establish a 3-competitive lower bound which extends to the original model. We then design a deterministic algorithm that is $(2+\sqrt{3})\approx 3.732$-competitive when predictions are perfect. With imperfect predictions (maximum error $\delta > 0$), we show that our deterministic algorithm becomes $\min\{3.732+4\delta,4\}$-competitive, knowing $\delta$. To the best of our knowledge, these are the first results for online traveling repairperson problem in the learning-augmented framework.

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

PR・アフィリエイト広告

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

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