論文の概要: Speedup Techniques for Switchable Temporal Plan Graph Optimization

• arxiv url: http://arxiv.org/abs/2412.15908v1
• Date: Fri, 20 Dec 2024 13:59:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-23 16:20:03.097596
• Title: Speedup Techniques for Switchable Temporal Plan Graph Optimization
• Title（参考訳）: 切り替え可能な時間計画グラフ最適化のための高速化手法
• Authors: He Jiang, Muhan Lin, Jiaoyang Li,
• Abstract要約: MAPF (Multi-Agent Path Finding) は、複数エージェントの衝突のない経路を計画することに焦点を当てている。 MAPF計画の実行中、エージェントは予期せぬ遅延に遭遇し、非効率性、デッドロック、さらには衝突に至る可能性がある。 本稿では,グラフベーススイッチブルエッジサーチ(GSES)を4つの高速化手法により大幅に高速化する改良GSESを提案する。
• 参考スコア（独自算出の注目度）: 7.478072166004144
• License:
• Abstract: Multi-Agent Path Finding (MAPF) focuses on planning collision-free paths for multiple agents. However, during the execution of a MAPF plan, agents may encounter unexpected delays, which can lead to inefficiencies, deadlocks, or even collisions. To address these issues, the Switchable Temporal Plan Graph provides a framework for finding an acyclic Temporal Plan Graph with the minimum execution cost under delays, ensuring deadlock- and collision-free execution. Unfortunately, existing optimal algorithms, such as Mixed Integer Linear Programming and Graph-Based Switchable Edge Search (GSES), are often too slow for practical use. This paper introduces Improved GSES, which significantly accelerates GSES through four speedup techniques: stronger admissible heuristics, edge grouping, prioritized branching, and incremental implementation. Experiments conducted on four different map types with varying numbers of agents demonstrate that Improved GSES consistently achieves over twice the success rate of GSES and delivers up to a 30-fold speedup on instances where both methods successfully find solutions.
• Abstract（参考訳）: MAPF (Multi-Agent Path Finding) は、複数エージェントの衝突のない経路を計画することに焦点を当てている。 しかし、MAPF計画の実行中、エージェントは予期せぬ遅延に遭遇し、非効率性、デッドロック、さらには衝突に至る可能性がある。 これらの問題に対処するため、Switchable Temporal Plan Graphは、遅延の最小実行コストで非循環的な時間プラングラフを見つけるためのフレームワークを提供し、デッドロックと衝突のない実行を保証する。 残念ながら、Mixed Integer Linear Programming や Graph-Based Switchable Edge Search (GSES) のような既存の最適アルゴリズムは、実用上は遅すぎることが多い。 本稿では,より強力な許容的ヒューリスティックス,エッジグループ化,優先順位付き分岐,インクリメンタル実装という4つの高速化手法により,GSESを大幅に高速化する改良GSESを紹介する。 エージェント数が異なる4つの異なるマップタイプで実施された実験では、改良GSESはGSESの成功率の2倍以上を一貫して達成し、両方の方法が解を見つけることができるインスタンス上で最大30倍のスピードアップを実現している。

関連論文リスト

• A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution [9.839983977902671]
  Switchable-Edge Search (SES) は最適通過順序を見つけるために設計されたA*スタイルのアルゴリズムである。 本研究では,SESの最適性を証明し,シミュレーションによる効率評価を行う。
  論文  参考訳（メタデータ） (2024-03-26T23:10:41Z)
• Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution [7.2988406091449605]
  BTPG(Bidirectional Temporal Plan Graph)と呼ばれる新しいグラフィカルな表現を導入し,実行中の注文を切り替えることで,不要な待ち時間を回避する。 実験の結果, BTPG は TPG に順調に優れ, 不要待ち時間が 8-20% 減少することがわかった。
  論文  参考訳（メタデータ） (2023-12-30T20:23:27Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。 USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
  論文  参考訳（メタデータ） (2023-12-19T02:27:22Z)
• GRASP: Accelerating Shortest Path Attacks via Graph Attention [1.3270612461223892]
  機械学習(ML)の最近の進歩は、古典的な最適化アルゴリズムの補助と加速を約束している。 本稿では,GRASPアルゴリズムを提案する。 Graph Accelerated Shortest Path Attackは,実行時間を最大10倍高速化するML支援最適化アルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-12T02:03:10Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  任意の切削平面制約を加えることができるような境界伝搬手順を一般化する。 MIPソルバは、境界プロパゲーションベースの検証器を強化するために高品質な切削面を生成することができる。 本手法は,oval20ベンチマークを完全解き,oval21ベンチマークの2倍のインスタンスを検証できる最初の検証器である。
  論文  参考訳（メタデータ） (2022-08-11T10:31:28Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
  k-Robust Conflict-BasedSearch (k-CBS)は、最大k遅延のロバストな座標と衝突のない計画を生成するアルゴリズムです。 そこで我々は,k-robust計画に特有な様々な対称性の破れ制約を導入し,矛盾するエージェントのペアに対して,効率よく相反する最適経路を見つける。
  論文  参考訳（メタデータ） (2021-02-17T11:09:33Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  複数の自動誘導車両 (AGV) が共通作業空間をナビゲートし, 様々な作業を行う。 一つのアプローチは、Action Dependency Graph (ADG)を構築し、そのルートに沿って進むとAGVの順序を符号化する。 ワークスペースが人間やサードパーティロボットのような動的障害によって共有されている場合、AGVは大きな遅延を経験することができる。 本稿では,各AGVの経路完了時間を最小限に抑えるために,非循環ADGを繰り返し修正するオンライン手法を提案する。
  論文  参考訳（メタデータ） (2020-10-11T14:39:50Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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