論文の概要: Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics

• arxiv url: http://arxiv.org/abs/2306.17609v1
• Date: Fri, 30 Jun 2023 12:31:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-03 12:24:44.728900
• Title: Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics
• Title（参考訳）: 効率的なヒューリスティックスを用いた時間最適マルチロボットカバレッジパス計画のための混合整数計画法
• Authors: Jingtao Tang and Hang Ma
• Abstract要約: 非重み付きおよび地形の時間最適マルチロボット被覆経路計画(MCPP)について検討する。 RMMTCを最適に解くためのMixed Programming(MIP)モデルを提案する。
• 参考スコア（独自算出の注目度）: 5.710487978627656
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate time-optimal Multi-Robot Coverage Path Planning (MCPP) for both unweighted and weighted terrains, which aims to minimize the coverage time, defined as the maximum travel time of all robots. Specifically, we focus on a reduction from MCPP to Rooted Min-Max Tree Cover (RMMTC). For the first time, we propose a Mixed Integer Programming (MIP) model to optimally solve RMMTC, resulting in an MCPP solution with a coverage time that is provably at most four times the optimal. Moreover, we propose two suboptimal yet effective heuristics that reduce the number of variables in the MIP model, thus improving its efficiency for large-scale MCPP instances. We show that both heuristics result in reduced-size MIP models that remain complete (i.e., guarantee to find a solution if one exists) for all RMMTC instances. Additionally, we explore the use of model optimization warm-startup to further improve the efficiency of both the original MIP model and the reduced-size MIP models. We validate the effectiveness of our MIP-based MCPP planner through experiments that compare it with two state-of-the-art MCPP planners on various instances, demonstrating a reduction in the coverage time by an average of 42.42% and 39.16% over them, respectively.
• Abstract（参考訳）: 本研究は,全ロボットの最大走行時間として定義される被加重地と加重地の両方について,時間最適化型マルチロボットカバーパス計画(mcpp)について検討する。 具体的には,MCPP から Rooted Min-Max Tree Cover (RMMTC) への削減に焦点を当てる。 RMMTCを最適に解くためのMixed Integer Programming (MIP)モデルを提案する。 さらに, MIPモデルの変数数を削減し, 大規模MCPPインスタンスの効率を向上する2つの準最適有効ヒューリスティックを提案する。 両ヒューリスティックスは、すべての RMMTC インスタンスに対して、完全である(すなわち、存在すれば解を見つけることを保証する)大きさの MIP モデルをもたらすことを示す。 さらに,従来のMIPモデルと小型MIPモデルの両方の効率を改善するために,モデル最適化ウォームスタートの利用について検討する。 MIPをベースとしたMCPPプランナの有効性を,2つの最先端MCPPプランナと比較し,それぞれ平均42.42%,39.16%のカバレッジ時間を短縮した実験により検証した。

関連論文リスト

• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
  大規模言語モデルを用いた最適化に基づく構造解析手法を提案する。 我々は,プルーニングモデルの損失を最適化することにより,確率空間におけるプルーニングマスクを直接学習する。 A100 GPUで13Bモデルに対して約35GBのメモリで2.7時間動作させる。
  論文  参考訳（メタデータ） (2024-06-15T09:31:03Z)
• Deep learning enhanced mixed integer optimization: Learning to reduce model dimensionality [0.0]
  この研究は、Mixed-Integer Programmingに固有の計算複雑性に対処するフレームワークを導入する。 ディープラーニングを利用することで、MIPインスタンス間の共通構造を特定し、活用する問題固有モデルを構築する。 本稿では,モデルの堅牢性と一般化性を高める合成データを生成するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-17T19:15:13Z)
• Deep Model Predictive Optimization [21.22047409735362]
  ロボット工学における大きな課題は、現実世界で複雑でアジャイルな振る舞いを可能にする堅牢なポリシーを設計することである。 本稿では,MPC最適化アルゴリズムの内ループを体験を通して直接学習するDeep Model Predictive Optimization (DMPO)を提案する。 DMPOは、MFRLでトレーニングされたエンドツーエンドポリシーを19%削減することで、最高のMPCアルゴリズムを最大27%向上させることができる。
  論文  参考訳（メタデータ） (2023-10-06T21:11:52Z)
• Mitigating Out-of-Distribution Data Density Overestimation in Energy-Based Models [54.06799491319278]
  深部エネルギーベースモデル(EBM)は、複雑な分布を学習する能力によって注目されている。 EBMの訓練には、Langevin Monte Carlo (LMC) を用いた最大推定(MLE)を用いることが多い。 短周期LCCのMLEが, 誤った密度推定でEMMに収束する理由を考察する。
  論文  参考訳（メタデータ） (2022-05-30T02:49:17Z)
• Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning [63.83425382922157]
  インテリジェント・リフレクション・サーフェス(IRS)は将来の無線ネットワークに広く応用されることが想定されている。 本稿では,エネルギー収穫能力を備えた協調型IRSデバイスを用いたマルチユーザ通信システムについて検討する。
  論文  参考訳（メタデータ） (2022-03-26T20:37:14Z)
• Learning to Schedule Heuristics for the Simultaneous Stochastic Optimization of Mining Complexes [2.538209532048867]
  提案したL2P(Learning-to-perturb)ハイパーヒューリスティックは,マルチ隣り合うシミュレートアニールアルゴリズムである。 L2Pは、効率、堅牢性、一般化能力に重点を置いて、いくつかの実世界の鉱業施設で試験されている。 その結果,反復回数を30～50%削減し,計算時間を30～45%削減した。
  論文  参考訳（メタデータ） (2022-02-25T18:20:14Z)
• Ranking and Tuning Pre-trained Models: A New Paradigm of Exploiting Model Hubs [136.4492678691406]
  本稿では,事前学習したモデルのランク付けとチューニングにより,モデルハブを利用する新しいパラダイムを提案する。 最高のランク付けされたPTMは、モデルのアーキテクチャを好まない場合は、微調整とデプロイが可能です。 チューニング部は、専用メソッドを超越した、複数 PTM チューニングのための新しい手法を導入する。
  論文  参考訳（メタデータ） (2021-10-20T12:59:23Z)
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization [76.51980153902774]
  フェデレーテッド・ラーニング(FL)はパラメータ伝達中にFLモデルに対する外部攻撃に対して脆弱である。 本稿では,最先端の防御アグリゲーション機構に対処する有効なMPアルゴリズムを提案する。 実験の結果,提案したCMPアルゴリズムは,既存の攻撃機構よりも効果的で,かなり優れていることが示された。
  論文  参考訳（メタデータ） (2021-01-28T03:28:18Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Improving the Performance of Stochastic Local Search for Maximum Vertex Weight Clique Problem Using Programming by Optimization [21.407603070913588]
  我々はMVWCPを解くための新しい、柔軟で高パラメトリックなフレームワークを開発した。 我々は、MVWCPを広範囲の顕著なベンチマークで解く上で、最先端の進歩を実現している。
  論文  参考訳（メタデータ） (2020-02-27T04:22:19Z)

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

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