論文の概要: Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming

• arxiv url: http://arxiv.org/abs/2603.16593v1
• Date: Tue, 17 Mar 2026 14:40:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-21 18:33:56.913788
• Title: Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming
• Title（参考訳）: フローベース混合整数線形計画によるスケーラブルな検査計画
• Authors: Adir Morgan, Kiril Solovey, Oren Salzman,
• Abstract要約: 検査計画とは、最短のロボット経路を計算して、与えられた一連の関心点を検査することである。 我々は、GIPのための高度にスケーラブルな混合線形プログラミング(MILP)ソリューションを提案し、ランタイムとソリューションの品質の両方において最先端の技術を著しく向上させます。
• 参考スコア（独自算出の注目度）: 8.568142982906755
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Inspection planning is concerned with computing the shortest robot path to inspect a given set of points of interest (POIs) using the robot's sensors. This problem arises in a wide range of applications from manufacturing to medical robotics. To alleviate the problem's complexity, recent methods rely on sampling-based methods to obtain a more manageable (discrete) graph inspection planning (GIP) problem. Unfortunately, GIP still remains highly difficult to solve at scale as it requires simultaneously satisfying POI-coverage and path-connectivity constraints, giving rise to a challenging optimization problem, particularly at scales encountered in real-world scenarios. In this work, we present highly scalable Mixed Integer Linear Programming (MILP) solutions for GIP that significantly advance the state-of-the-art in both runtime and solution quality. Our key insight is a reformulation of the problem's core constraints as a network flow, which enables effective MILP models and a specialized Branch-and-Cut solver that exploits the combinatorial structure of flows. We evaluate our approach on medical and infrastructure benchmarks alongside large-scale synthetic instances. Across all scenarios, our method produces substantially tighter lower bounds than existing formulations, reducing optimality gaps by 30-50% on large instances. Furthermore, our solver demonstrates unprecedented scalability: it provides non-trivial solutions for problems with up to 15,000 vertices and thousands of POIs, where prior state-of-the-art methods typically exhaust memory or fail to provide any meaningful optimality guarantees.
• Abstract（参考訳）: 検査計画とは、ロボットのセンサーを用いて、与えられた関心点(POI)を検査するために最も短いロボット経路を計算することである。 この問題は、製造から医療ロボティクスまで幅広い用途で発生する。 問題の複雑さを軽減するため、最近の手法はより管理しやすい(離散的な)グラフ検査計画(GIP)問題を得るためにサンプリングベースの手法に依存している。 残念なことに、GIPはPOIカバレッジとパス接続性の制約を同時に満たす必要があり、特に現実世界のシナリオで発生するスケールにおいて、困難な最適化問題を引き起こすため、大規模に解決するのは依然として非常に困難である。 本稿では,GIPのためのMILP(Mixed Integer Linear Programming)ソリューションを提案する。 我々の重要な洞察は、効率的なMILPモデルと、フローの組合せ構造を利用する専門的なブランチ・アンド・カット・ソルバを可能にする、ネットワークフローとしての問題のコア制約の再構築である。 医療およびインフラベンチマークに対する我々のアプローチを,大規模合成インスタンスとともに評価した。 全てのシナリオにおいて,提案手法は既存の定式化よりもはるかに低い境界を生じさせ,大規模インスタンス上での最適性ギャップを30～50%削減する。 最大15,000の頂点と数千のPOIを持つ問題に対して、非自明なソリューションを提供する。

関連論文リスト

• Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach [5.84228364962637]
  本稿では,最適化問題を近似する効率的なアルゴリズムを学習するメタ最適化手法を提案する。 我々は,学習方法の指数収束,近似保証,一般化境界を証明した。 この手法は計算効率に優れ、高品質な近似を高速に生成し、既存の手法と比較して問題の大きさでスケールする。
  論文  参考訳（メタデータ） (2025-05-16T15:27:50Z)
• Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
  教師なし学習方式でバイナリ変数の自動エンコーダを訓練する。 オフライン学習AEのデコーダパラメータから平面制約を切断するクラスを構築する戦略を提案する。 原始的なMIP問題への統合は、実現可能な領域を縮小したMIPの強化につながる。
  論文  参考訳（メタデータ） (2024-12-23T14:48:32Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Optimization of Robot Trajectory Planning with Nature-Inspired and Hybrid Quantum Algorithms [0.0]
  産業規模でロボット軌道計画問題を解く。 我々のエンドツーエンドソリューションは、高度に多目的なランダムキーアルゴリズムとモデル積み重ねとアンサンブル技術を統合している。 我々は、後者が我々のより大きなパイプラインにどのように統合され、問題に対する量子対応ハイブリッドソリューションを提供するかを示す。
  論文  参考訳（メタデータ） (2022-06-08T02:38:32Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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