論文の概要: Anytime Single-Step MAPF Planning with Anytime PIBT

• arxiv url: http://arxiv.org/abs/2504.07841v1
• Date: Thu, 10 Apr 2025 15:21:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-11 12:19:45.067150
• Title: Anytime Single-Step MAPF Planning with Anytime PIBT
• Title（参考訳）: PIBTを用いたワンステップMAPF計画
• Authors: Nayesha Gandotra, Rishi Veerapaneni, Muhammad Suhail Saleem, Daniel Harabor, Jiaoyang Li, Maxim Likhachev,
• Abstract要約: PIBTと同一のワンステップ解を素早く発見し,任意の方法で連続的に改善するAnytime PIBTを開発した。 我々は、任意のPIBTがミリ秒以内の単一ステップソリューションの品質を迅速に向上し、最適な単一ステップアクションを見つけることができることを実験的に検証した。
• 参考スコア（独自算出の注目度）: 22.013151675093795
• License:
• Abstract: PIBT is a popular Multi-Agent Path Finding (MAPF) method at the core of many state-of-the-art MAPF methods including LaCAM, CS-PIBT, and WPPL. The main utility of PIBT is that it is a very fast and effective single-step MAPF solver and can return a collision-free single-step solution for hundreds of agents in less than a millisecond. However, the main drawback of PIBT is that it is extremely greedy in respect to its priorities and thus leads to poor solution quality. Additionally, PIBT cannot use all the planning time that might be available to it and returns the first solution it finds. We thus develop Anytime PIBT, which quickly finds a one-step solution identically to PIBT but then continuously improves the solution in an anytime manner. We prove that Anytime PIBT converges to the optimal solution given sufficient time. We experimentally validate that Anytime PIBT can rapidly improve single-step solution quality within milliseconds and even find the optimal single-step action. However, we interestingly find that improving the single-step solution quality does not have a significant effect on full-horizon solution costs.
• Abstract（参考訳）: PIBTは、LaCAM、CS-PIBT、WPPLなど多くの最先端MAPFメソッドの中核にある、人気のあるマルチエージェントパスファインディング(MAPF)メソッドである。 PIBTの主な用途は、非常に高速で効果的なシングルステップMAPF解決器であり、1ミリ秒未満で数百のエージェントに対して衝突のないシングルステップ解を返すことができることである。 しかし、PIBTの主な欠点は、その優先順位に関して非常に欲求的であり、結果としてソリューションの品質が低下する点である。 さらにPIBTは、利用可能なすべての計画時間を使用できず、最初に見つけたソリューションを返します。 そこで我々はAnytime PIBTを開発し、PIBTと同一のワンステップの解がすぐに見つかるが、任意の方法で解を継続的に改善する。 任意のPIBTが十分な時間で最適解に収束することを証明する。 我々は、任意のPIBTがミリ秒以内の単一ステップソリューションの品質を迅速に向上し、最適な単一ステップアクションを見つけることができることを実験的に検証した。 しかし, 単段階解法の品質向上は, 完全水平解法コストに有意な影響を及ぼさないことが興味深い。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Accelerating Diffusion Sampling with Optimized Time Steps [69.21208434350567]
  拡散確率モデル(DPM)は高分解能画像合成において顕著な性能を示した。 彼らのサンプリング効率は、通常多くのサンプリングステップのため、依然として望まれている。 DPM用高次数値ODEソルバの最近の進歩により、サンプリングステップがはるかに少ない高品質な画像の生成が可能になった。
  論文  参考訳（メタデータ） (2024-02-27T10:13:30Z)
• Achieving Instance-dependent Sample Complexity for Constrained Markov Decision Process [4.685121820790546]
  マルコフ決定過程(CMDP)の強化学習問題について考察する。 これは$O(frac1Deltacdotepsiloncdotlog2(1/epsilon))$ sample complexity boundとなる。 本アルゴリズムは一次空間で動作し,CMDP問題に対する一次LPを各期間にオンライン的に解決する。
  論文  参考訳（メタデータ） (2024-02-26T06:08:25Z)
• Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics [5.710487978627656]
  非重み付きおよび地形の時間最適マルチロボット被覆経路計画(MCPP)について検討する。 具体的には、MCPP から Min-Max Rooted Tree Cover (MMRTC) への削減に焦点を当てる。 MMRTCを最適に解くために,Mixed Programming(MIP)モデルを提案する。
  論文  参考訳（メタデータ） (2023-06-30T12:31:29Z)
• Multi-Objective Population Based Training [62.997667081978825]
  Population Based Training (PBT) は効率的なハイパーパラメータ最適化アルゴリズムである。 本研究ではPBTの多目的版であるMO-PBTを紹介する。
  論文  参考訳（メタデータ） (2023-06-02T10:54:24Z)
• Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
  MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。 MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。 本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
  論文  参考訳（メタデータ） (2023-03-30T14:42:41Z)
• An Efficient Solution to s-Rectangular Robust Markov Decision Processes [49.05403412954533]
  テクスツ長方形ロバストマルコフ決定過程(MDP)に対する効率的なロバストな値反復法を提案する。 我々は,L_p$の水充填補題を用いて,ベルマン作用素を具体的形式で導出した。 最適な政策の正確な形を明らかにし、これは、その利点に比例する行動を起こす確率で、新しいしきい値ポリシーであることが判明した。
  論文  参考訳（メタデータ） (2023-01-31T13:54:23Z)
• A Two-phase Framework with a B\'{e}zier Simplex-based Interpolation Method for Computationally Expensive Multi-objective Optimization [11.834904868909037]
  本稿では,B'ezier Simplexに基づく計算コストの高い多目的最適化手法を用いた2相フレームワークを提案する。 TPBの第1フェーズは、最先端の単目的誘導体をフル活用することができる。 TPBの第2フェーズは、与えられた問題が単純であるときにその単純構造を利用することにより、B'ezierの単純なモデルが最適解集合を近似できるという事実を利用する。
  論文  参考訳（メタデータ） (2022-03-29T07:11:53Z)
• Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning [156.5667417159582]
  本稿では,逐次情報設計の新たなモデル,すなわちマルコフ説得過程(MPP)を提案する。 MPPのプランニングは、ミオピックレシーバーに同時に説得されるシグナルポリシーを見つけ、送信者の最適な長期累積ユーティリティを誘導する、というユニークな課題に直面している。 我々は,楽観主義と悲観主義の両原理の新たな組み合わせを特徴とする,実証可能な効率のよい非回帰学習アルゴリズム,Optimism-Pessimism Principle for Persuasion Process (OP4) を設計する。
  論文  参考訳（メタデータ） (2022-02-22T05:41:43Z)
• STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations [27.353023427198806]
  我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。 POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。 我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-05-28T18:07:16Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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