論文の概要: A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution
- arxiv url: http://arxiv.org/abs/2403.18145v1
- Date: Tue, 26 Mar 2024 23:10:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-28 18:55:29.775643
- Title: A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution
- Title(参考訳): マルチロボット計画実行のためのリアルタイムスケジューリングアルゴリズム
- Authors: Ying Feng, Adittyo Paul, Zhe Chen, Jiaoyang Li,
- Abstract要約: Switchable-Edge Search (SES) は最適通過順序を見つけるために設計されたA*スタイルのアルゴリズムである。
本研究では,SESの最適性を証明し,シミュレーションによる効率評価を行う。
- 参考スコア(独自算出の注目度): 9.839983977902671
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One area of research in multi-agent path finding is to determine how replanning can be efficiently achieved in the case of agents being delayed during execution. One option is to reschedule the passing order of agents, i.e., the sequence in which agents visit the same location. In response, we propose Switchable-Edge Search (SES), an A*-style algorithm designed to find optimal passing orders. We prove the optimality of SES and evaluate its efficiency via simulations. The best variant of SES takes less than 1 second for small- and medium-sized problems and runs up to 4 times faster than baselines for large-sized problems.
- Abstract(参考訳): マルチエージェントパス探索における研究の1つの分野は、実行中にエージェントが遅延した場合に、いかに効率的に再計画が達成できるかを決定することである。
1つの選択肢は、エージェントの通過順序、すなわちエージェントが同じ場所を訪れたシーケンスを再スケジュールすることである。
そこで本研究では,最適通過順序を求めるために設計されたA*スタイルのアルゴリズムであるSwitchable-Edge Search (SES)を提案する。
本研究では,SESの最適性を証明し,シミュレーションによる効率評価を行う。
SESの最良の変種は、小規模および中規模の問題では1秒未満で、大規模問題ではベースラインの最大4倍の速度で実行される。
関連論文リスト
- A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。
我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
論文 参考訳(メタデータ) (2025-02-14T15:21:27Z) - Speedup Techniques for Switchable Temporal Plan Graph Optimization [7.478072166004144]
MAPF (Multi-Agent Path Finding) は、複数エージェントの衝突のない経路を計画することに焦点を当てている。
MAPF計画の実行中、エージェントは予期せぬ遅延に遭遇し、非効率性、デッドロック、さらには衝突に至る可能性がある。
本稿では,グラフベーススイッチブルエッジサーチ(GSES)を4つの高速化手法により大幅に高速化する改良GSESを提案する。
論文 参考訳(メタデータ) (2024-12-20T13:59:15Z) - Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions [5.5233853454863615]
MAPF(Multi-Agent Path Finding)は、各開始地点から各目標地点まで、複数のエージェントの衝突のない経路を求める。
多くのMAPFアルゴリズムは数千のエージェントを処理できるが、エージェントの各アクションが時間単位を必要とするという仮定に依存している。
本稿では,新たなプランナを開発し,スケーラビリティのためのソリューション品質をトレードオフする。
論文 参考訳(メタデータ) (2024-12-16T11:36:24Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳(メタデータ) (2024-06-21T05:57:08Z) - MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
MG-MAPF問題は、各エージェントが少なくとも1回は衝突することなく、予め割り当てられた複数のゴールポイントを訪問する必要がある。
そこで本研究では,単一エージェントパスフィンディング(Single-Adnt pathfinding)とセーフ区間探索(Single-Adnt pathfinding)の分離に基づくMulti-Goal Conflict-Based Search (MGCBS)を提案する。
提案手法は, 常に最適な結果を得ることができ, 評価において最先端の手法よりも最大7倍高速に実行することができる。
論文 参考訳(メタデータ) (2024-04-30T12:49:54Z) - Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。
基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。
我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文 参考訳(メタデータ) (2022-09-27T17:51:31Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳(メタデータ) (2021-09-13T18:10:52Z) - Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。
この問題をある程度緩和する手法を提案する。
論文 参考訳(メタデータ) (2021-08-11T10:42:11Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳(メタデータ) (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。