論文の概要: Conflict-Based Search for Explainable Multi-Agent Path Finding

• arxiv url: http://arxiv.org/abs/2202.09930v1
• Date: Sun, 20 Feb 2022 23:13:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-23 09:50:57.754007
• Title: Conflict-Based Search for Explainable Multi-Agent Path Finding
• Title（参考訳）: コンフリクトに基づく説明可能なマルチエージェント経路探索
• Authors: Justin Kottinger, Shaull Almagor, Morteza Lahijanian
• Abstract要約: 安全クリティカルなアプリケーションでは、人間の監督者は、この計画が本当に衝突のないものであることを検証したいかもしれない。 MAPF問題は、簡潔な説明を認める非衝突経路のセットを要求する。 従来のMAPFアルゴリズムは、説明可能なMAPFを直接処理するものではない。 我々は、MAPFのためのよく研究されたアルゴリズムである Conflict Based Search (CBS) を適用して、説明可能なMAPFを扱う。
• 参考スコア（独自算出の注目度）: 7.734726150561088
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the Multi-Agent Path Finding (MAPF) problem, the goal is to find non-colliding paths for agents in an environment, such that each agent reaches its goal from its initial location. In safety-critical applications, a human supervisor may want to verify that the plan is indeed collision-free. To this end, a recent work introduces a notion of explainability for MAPF based on a visualization of the plan as a short sequence of images representing time segments, where in each time segment the trajectories of the agents are disjoint. Then, the explainable MAPF problem asks for a set of non-colliding paths that admits a short-enough explanation. Explainable MAPF adds a new difficulty to MAPF, in that it is NP-hard with respect to the size of the environment, and not just the number of agents. Thus, traditional MAPF algorithms are not equipped to directly handle explainable-MAPF. In this work, we adapt Conflict Based Search (CBS), a well-studied algorithm for MAPF, to handle explainable MAPF. We show how to add explainability constraints on top of the standard CBS tree and its underlying A* search. We examine the usefulness of this approach and, in particular, the tradeoff between planning time and explainability.
• Abstract（参考訳）: マルチエージェントパス探索(mapf)問題では、各エージェントが初期位置から目標に達するように、環境内のエージェントの非衝突パスを見つけることが目標である。 安全クリティカルなアプリケーションでは、人間の監督者は、計画が実際に衝突のないものであることを確認したいかもしれない。 この目的のために、最近の研究では、時間セグメントを表す画像の短いシーケンスとして計画の視覚化に基づいてMAPFの説明可能性の概念を導入し、各時間セグメントにおいてエージェントの軌道が切り離されている。 そして、説明可能なMAPF問題は、短い説明を許容する非衝突経路の集合を求める。 説明可能なMAPFは、エージェントの数だけでなく、環境の大きさに関してNPハードであるという点において、MAPFに新たな困難をもたらす。 したがって、従来のMAPFアルゴリズムは説明可能なMAPFを直接扱うことができない。 本研究では、MAPFのためのよく研究されたアルゴリズムであるConflict Based Search (CBS) を用いて、説明可能なMAPFを扱う。 CBSツリーとその基盤となるA*検索の上に、説明可能性の制約を加える方法を示す。 このアプローチの有用性,特に計画時間と説明可能性のトレードオフについて検討する。

関連論文リスト

• MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale [46.35418789518417]
  マルチエージェントパスフィンディング(Multi-agent pathfinding)は、共有環境における複数のエージェントの衝突のないパスを見つけることを必要とする、難しい計算問題である。 我々はMAPF-GPTと呼ばれるMAPF問題の基盤モデルを構築した。 擬似学習を用いて、部分観測可能性の条件下での行動を生成するための準最適専門家軌道のセットに関する政策を訓練した。 MAPF-GPTは、様々な問題インスタンスにおいて、現在最も優れた学習可能なMAPF解法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-08-29T12:55:10Z)
• 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)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
  MAPF(Multi-Agent Path Finding)は、ロボット工学における基本的な問題であり、エージェントのチームに対して衝突のない経路の計算を求める。 本稿では,MAPFにエージェントを誘導する手法を提案する。 各エージェントが1つの宛先を持つワンショットMAPFと、エージェントが常に新しい宛先を割り当てる終身MAPFの2つの大規模設定でこのアイデアを評価する。
  論文  参考訳（メタデータ） (2023-08-22T07:17:39Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。 具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。 また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
  論文  参考訳（メタデータ） (2023-07-25T12:33:53Z)
• LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
  MAPF(LaCAM)の遅延制約付加探索という,マルチエージェントパスフィンディング(MAPF)のための新しい完全アルゴリズムを提案する。 LaCAMは2段階の検索を使って、何百ものエージェントでも素早くソリューションを見つける。 実験の結果,LaCAMは様々なシナリオにおいて最先端のMAPFアルゴリズムに匹敵する,あるいは優れることがわかった。
  論文  参考訳（メタデータ） (2022-11-24T06:27:18Z)
• POGEMA: Partially Observable Grid Environment for Multiple Agents [64.88759709443819]
  POGEMAは、部分的に観測可能なマルチエージェントパスフィンディング(PO-MAPF)問題に挑戦するためのサンドボックスである。 様々なPO-MAPFに合わせることができ、プランニングと学習のための優れた試験場として機能する。
  論文  参考訳（メタデータ） (2022-06-22T09:39:50Z)
• Leveraging Experience in Lifelong Multi-Agent Pathfinding [12.401344261399613]
  Lifelong Multi-Agent Path Finding (L-MAPF) では、エージェントのチームが互いに衝突を避けながらタスクのストリームを実行する。 本稿では,新しいRHCRにインスパイアされたアプローチであるexRHCRを紹介する。 ExRHCRはL-MAPFをRHCRよりも25%高速に解決し、与えられたタスクストリームのスループットを最大で16%向上させる。
  論文  参考訳（メタデータ） (2022-02-09T10:41:35Z)
• 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)

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

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