論文の概要: Can LLMs Prove Robotic Path Planning Optimality? A Benchmark for Research-Level Algorithm Verification

• arxiv url: http://arxiv.org/abs/2603.19464v1
• Date: Thu, 19 Mar 2026 20:55:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 19:48:38.882874
• Title: Can LLMs Prove Robotic Path Planning Optimality? A Benchmark for Research-Level Algorithm Verification
• Title（参考訳）: LLMはロボット経路計画最適性を証明できるか?-研究レベルアルゴリズム検証のためのベンチマーク
• Authors: Zhengbang Yang, Md. Tasin Tazwar, Minghan Wei, Zhuangdi Zhu,
• Abstract要約: 本稿では,ロボット経路計画アルゴリズムの近似比証明について,LLM(Large Language Models)を評価するための最初のベンチマークを紹介する。 我々の評価では、最強のモデルでさえ、外部のドメイン知識なしで完全に有効な証明を作成するのに苦労していることが明らかになっている。
• 参考スコア（独自算出の注目度）: 5.637461397736495
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Robotic path planning problems are often NP-hard, and practical solutions typically rely on approximation algorithms with provable performance guarantees for general cases. While designing such algorithms is challenging, formally proving their approximation optimality is even more demanding, which requires domain-specific geometric insights and multi-step mathematical reasoning over complex operational constraints. Recent Large Language Models (LLMs) have demonstrated strong performance on mathematical reasoning benchmarks, yet their ability to assist with research-level optimality proofs in robotic path planning remains under-explored. In this work, we introduce the first benchmark for evaluating LLMs on approximation-ratio proofs of robotic path planning algorithms. The benchmark consists of 34 research-grade proof tasks spanning diverse planning problem types and complexity levels, each requiring structured reasoning over algorithm descriptions, problem constraints, and theoretical guarantees. Our evaluation of state-of-the-art proprietary and open-source LLMs reveals that even the strongest models struggle to produce fully valid proofs without external domain knowledge. However, providing LLMs with task-specific in-context lemmas substantially improves reasoning quality, a factor that is more effective than generic chain-of-thought prompting or supplying the ground-truth approximation ratio as posterior knowledge. We further provide fine-grained error analysis to characterize common logical failures and hallucinations, and demonstrate how each error type can be mitigated through targeted context augmentation.
• Abstract（参考訳）: ロボット経路計画問題はしばしばNPハードであり、実用的な解法は一般に証明可能な性能保証を持つ近似アルゴリズムに依存する。 このようなアルゴリズムを設計することは難しいが、その近似最適性を正式に証明することがさらに要求され、複雑な演算制約に対して、ドメイン固有の幾何学的洞察と多段階の数学的推論を必要とする。 近年のLarge Language Models (LLMs) は、数学的推論ベンチマークにおいて強力な性能を示してきたが、ロボット経路計画における研究レベルの最適性証明を支援する能力は、まだ解明されていない。 本研究では,ロボット経路計画アルゴリズムの近似比証明におけるLLMの評価のための最初のベンチマークを紹介する。 このベンチマークは、様々な計画上の問題タイプと複雑性レベルにまたがる34の研究グレードの証明タスクで構成され、それぞれがアルゴリズムの記述、問題制約、理論的保証に対して構造化された推論を必要とする。 最先端のプロプライエタリかつオープンソース LLM を評価した結果,最強のモデルでさえ,外部のドメイン知識を使わずに完全に有効な証明を作成するのに苦労していることが明らかとなった。 しかし、タスク固有の文脈内補題をLLMに提供することにより、推論品質が大幅に向上する。 さらに、一般的な論理的失敗や幻覚を特徴付けるためのきめ細かいエラー解析を提供し、各エラータイプをターゲットのコンテキスト拡張によって緩和する方法を実証する。

関連論文リスト

• AlgBench: To What Extent Do Large Reasoning Models Understand Algorithms? [21.836954662380094]
  本稿では,アルゴリズム中心のパラダイムの下でLarge Reasoning Models(LRMs)を評価する専門家によるベンチマークであるAlgBenchを提案する。 AlgBenchは、ACMアルゴリズムの専門家によって構築された27のアルゴリズムにまたがる3000以上の元の問題で構成されている。 先進的なLRM(Gemini-3-Pro、DeepSeek-v3.2- Speciale、GPT-o3)に関する実証的な評価は、かなりの性能を示している。
  論文  参考訳（メタデータ） (2026-01-08T14:54:44Z)
• Position: We Need An Algorithmic Understanding of Generative AI [7.425924654036041]
  本稿では,LLMが学習・使用するアルゴリズムを体系的に研究するためのフレームワークであるAlgEvalを提案する。 AlgEvalは、潜在表現、注意、推論時間計算に反映されるアルゴリズムプリミティブと、タスク固有の問題を解決するアルゴリズム構成を明らかにすることを目的としている。
  論文  参考訳（メタデータ） (2025-07-10T08:38:47Z)
• Bridging Pattern-Aware Complexity with NP-Hard Optimization: A Unifying Framework and Empirical Study [0.0]
  本稿では,ドメイン間の効率的な計算複雑性を低減するための新しいパターン認識フレームワークを提案する。 厳密な定義、定理、メタ学習駆動型ソルバパイプラインによって、パターン利用効率(PUE)のようなメトリクスを導入し、最大で79%のソリューション品質向上を実現します。
  論文  参考訳（メタデータ） (2025-03-12T11:05:06Z)
• EVOLvE: Evaluating and Optimizing LLMs For In-Context Exploration [76.66831821738927]
  大規模言語モデル(LLM)は、不確実性の下で最適な意思決定を必要とするシナリオにおいて、未調査のままである。 多くのアプリケーションに関係のあるステートレス強化学習環境である,帯域幅を最適に決定できる LLM の (in) 能力の測定を行う。 最適な探索アルゴリズムの存在を動機として,このアルゴリズム知識をLLMに統合する効率的な方法を提案する。
  論文  参考訳（メタデータ） (2024-10-08T17:54:03Z)
• Designing Algorithms Empowered by Language Models: An Analytical Framework, Case Studies, and Insights [86.06371692309972]
  本研究では,大規模言語モデル(LLM)に基づくアルゴリズムの設計と解析のための分析フレームワークを提案する。 提案する枠組みは頭痛を緩和する試みとして機能する。
  論文  参考訳（メタデータ） (2024-07-20T07:39:07Z)
• Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach [0.0]
  本稿では,パラメータ化複雑性解析を用いて,アルゴリズムの選択肢を体系的に探索する方法を示す。 環境、実演、ポリシーに対する多くの(しばしば同時に)制限に対して、我々の問題は、一般的にも、あるいは相対的に、効率的に解決できないことを示す。
  論文  参考訳（メタデータ） (2022-05-10T15:54:06Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。