論文の概要: An Efficient Approach to the Online Multi-Agent Path Finding Problem by Using Sustainable Information

• arxiv url: http://arxiv.org/abs/2301.04446v1
• Date: Wed, 11 Jan 2023 13:04:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-12 17:46:38.054746
• Title: An Efficient Approach to the Online Multi-Agent Path Finding Problem by Using Sustainable Information
• Title（参考訳）: 持続可能情報を用いたオンラインマルチエージェント経路探索問題への効率的なアプローチ
• Authors: Mingkai Tang, Boyi Liu, Yuanhang Li, Hongji Liu, Ming Liu, Lujia Wang
• Abstract要約: 多エージェント経路探索(MAPF)は、衝突せずにエージェントをゴールへ移動させる問題である。 本稿では,持続可能な情報を活用したオンラインMAPFの3段階的解決手法を提案する。 我々のアルゴリズムは、エージェント数の設定が異なる場合、平均1.48倍の速度でSOTAより高速である。
• 参考スコア（独自算出の注目度）: 10.367412630626834
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent path finding (MAPF) is the problem of moving agents to the goal vertex without collision. In the online MAPF problem, new agents may be added to the environment at any time, and the current agents have no information about future agents. The inability of existing online methods to reuse previous planning contexts results in redundant computation and reduces algorithm efficiency. Hence, we propose a three-level approach to solve online MAPF utilizing sustainable information, which can decrease its redundant calculations. The high-level solver, the Sustainable Replan algorithm (SR), manages the planning context and simulates the environment. The middle-level solver, the Sustainable Conflict-Based Search algorithm (SCBS), builds a conflict tree and maintains the planning context. The low-level solver, the Sustainable Reverse Safe Interval Path Planning algorithm (SRSIPP), is an efficient single-agent solver that uses previous planning context to reduce duplicate calculations. Experiments show that our proposed method has significant improvement in terms of computational efficiency. In one of the test scenarios, our algorithm can be 1.48 times faster than SOTA on average under different agent number settings.
• Abstract（参考訳）: 多エージェント経路探索 (MAPF) は, 衝突せずに目標頂点へエージェントを移動させる問題である。 オンラインMAPF問題では、新しいエージェントがいつでも環境に追加され、現在のエージェントは将来のエージェントに関する情報を持っていない。 既存のオンラインメソッドが以前の計画コンテキストを再利用できないため、冗長な計算が可能となり、アルゴリズム効率が低下する。 そこで本稿では,持続可能情報を利用したオンラインmapfの3段階解法を提案する。 高レベルの解決アルゴリズムであるSustainable Replan Algorithm (SR)は、計画コンテキストを管理し、環境をシミュレートする。 中レベルの解決アルゴリズムであるSustainable Conflict-Based Search (SCBS)は、コンフリクトツリーを構築し、計画コンテキストを維持する。 低レベルソルバであるsustainable reverse safe interval path planning algorithm (srsipp)は、以前のプランニングコンテキストを使用して重複計算を減らす効率的な単一エージェントソルバである。 実験により,提案手法は計算効率の点で有意な改善が得られた。 テストシナリオの1つでは、エージェント数設定の異なる平均で、我々のアルゴリズムはSOTAの1.48倍高速である。

関連論文リスト

• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  マルチエージェントパスフィンディング(MAPF)問題は通常、グラフに制限されたエージェントの集合に対する競合のないパスの集合を見つけるよう要求する。 本研究では,エージェントの位置や目標に関する情報をすべて収集する中央制御器が存在しない場合の分散MAPF設定について検討する。 我々は,先行するエージェントに新たな目標を連続的に割り当てることを含むMAPFの実用上重要な寿命変化に焦点をあてる。
  論文  参考訳（メタデータ） (2023-10-02T13:51:32Z)
• Distributed Allocation and Scheduling of Tasks with Cross-Schedule Dependencies for Heterogeneous Multi-Robot Teams [2.294915015129229]
  本稿では,異なるロボットのタスクが時間的・優先的な制約に強く結びついているミッションに対して,タスク割り当てとスケジューリングを行うアルゴリズムを提案する。 マルチロボットシステムによって維持される温室の実用ユースケースへの計画手順の適用。
  論文  参考訳（メタデータ） (2021-09-07T13:44:28Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。 この問題をある程度緩和する手法を提案する。
  論文  参考訳（メタデータ） (2021-08-11T10:42:11Z)
• Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities [7.766921168069532]
  このトピックの過去の発展と現在の傾向から学んだ教訓を示し、その広範な影響について議論します。 最適MAPF解決のための2つの主要なアプローチは、(1)MAPFを直接解決する専用の検索ベース手法、(2)MAPFインスタンスを異なる確立された形式でインスタンスに還元するコンパイルベース手法である。
  論文  参考訳（メタデータ） (2021-04-23T20:13:12Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。 深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-19T13:10:20Z)

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

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