論文の概要: Deadlock-Free Method for Multi-Agent Pickup and Delivery Problem Using Priority Inheritance with Temporary Priority

• arxiv url: http://arxiv.org/abs/2205.12504v1
• Date: Wed, 25 May 2022 05:45:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-26 15:07:16.931477
• Title: Deadlock-Free Method for Multi-Agent Pickup and Delivery Problem Using Priority Inheritance with Temporary Priority
• Title（参考訳）: プライオリティ継承を用いたマルチエージェントピックアップ・デリバリー問題に対するデッドロックフリー手法
• Authors: Yukita Fujitani, Tomoki Yamauchi, Yuki Miyashita and Toshiharu Sugawara
• Abstract要約: 本稿では,PIBT法を用いて優先度継承を拡張することで,マルチエージェントピックアップ・デリバリ問題(MAPD問題)の制御手法を提案する。 PIBTは、バイコネクテッドな領域としてモデル化された環境にのみ適用でき、木のような死の端を含む場合、PIBTはデッドロックを引き起こす可能性がある。 提案手法は,PIBT機能を保ちながら,デッドロックを伴わずに,木形パスのある環境でMAPDタスクを実行できる。
• 参考スコア（独自算出の注目度）: 2.064612766965483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proposes a control method for the multi-agent pickup and delivery problem (MAPD problem) by extending the priority inheritance with backtracking (PIBT) method to make it applicable to more general environments. PIBT is an effective algorithm that introduces a priority to each agent, and at each timestep, the agents, in descending order of priority, decide their next neighboring locations in the next timestep through communications only with the local agents. Unfortunately, PIBT is only applicable to environments that are modeled as a bi-connected area, and if it contains dead-ends, such as tree-shaped paths, PIBT may cause deadlocks. However, in the real-world environment, there are many dead-end paths to locations such as the shelves where materials are stored as well as loading/unloading locations to transportation trucks. Our proposed method enables MAPD tasks to be performed in environments with some tree-shaped paths without deadlock while preserving the PIBT feature; it does this by allowing the agents to have temporary priorities and restricting agents' movements in the trees. First, we demonstrate that agents can always reach their delivery without deadlock. Our experiments indicate that the proposed method is very efficient, even in environments where PIBT is not applicable, by comparing them with those obtained using the well-known token passing method as a baseline.
• Abstract（参考訳）: 本稿では,より一般的な環境に適用可能なバックトラッキング(pibt)方式による優先度継承を拡張し,マルチエージェントピックアップ・デリバリー問題(マップ問題)の制御手法を提案する。 PIBTは、各エージェントに優先順位を導入する効果的なアルゴリズムであり、各タイムステップごとに、優先度の順に、エージェントは、ローカルエージェントとの通信のみで次のタイムステップで隣の場所を決定する。 残念なことに、pibtはバイコネクテッドエリアとしてモデル化された環境にのみ適用でき、木型のパスのようなデッドエンドを含む場合、pibtはデッドロックを引き起こす可能性がある。 しかし、現実世界の環境では、材料が保管されている棚や輸送トラックへの荷降ろし場所など、多くのデッドエンドの経路がある。 提案手法は, PIBT機能を維持しながら, デッドロックのない木形経路の環境下でMAPDタスクを行えるようにし, エージェントが一時的に優先順位をつけ, エージェントの動きを制限できるようにする。 まず,エージェントがデッドロックなしで常に配信に到達できることを実証する。 提案手法は,PIBTが適用できない環境においても,よく知られたトークンパス法をベースラインとして得られた手法と比較することにより,極めて効率的であることを示す。

関連論文リスト

• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• AlberDICE: Addressing Out-Of-Distribution Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimation [65.4532392602682]
  オフライン強化学習(RL)の主な課題の1つは、データ収集ポリシーから逸脱した学習ポリシーから生じる分散シフトである。 これはしばしば、政策改善中のアウト・オブ・ディストリビューション(OOD)アクションを避けることで対処される。 本稿では,定常分布最適化に基づく個別エージェントの集中学習を行うオフラインMARLアルゴリズムAlberDICEを紹介する。
  論文  参考訳（メタデータ） (2023-11-03T18:56:48Z)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  マルチエージェントパスフィンディング(MAPF)問題は通常、グラフに制限されたエージェントの集合に対する競合のないパスの集合を見つけるよう要求する。 本研究では,エージェントの位置や目標に関する情報をすべて収集する中央制御器が存在しない場合の分散MAPF設定について検討する。 我々は,先行するエージェントに新たな目標を連続的に割り当てることを含むMAPFの実用上重要な寿命変化に焦点をあてる。
  論文  参考訳（メタデータ） (2023-10-02T13:51:32Z)
• AI planning in the imagination: High-level planning on learned abstract search spaces [68.75684174531962]
  我々は,エージェントが訓練中に学習する抽象的な検索空間において,エージェントが計画することを可能にする,PiZeroと呼ばれる新しい手法を提案する。 本研究では,旅行セールスマン問題,ソコバン問題,2048年,施設立地問題,パックマン問題など,複数の分野で評価を行った。
  論文  参考訳（メタデータ） (2023-08-16T22:47:16Z)
• Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
  MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。 MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。 本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
  論文  参考訳（メタデータ） (2023-03-30T14:42:41Z)
• Continual Test-Time Domain Adaptation [94.51284735268597]
  テスト時ドメイン適応は、ソースデータを使用しずに、ソース事前訓練されたモデルをターゲットドメインに適応することを目的としている。 CoTTAは実装が容易で、市販の事前訓練モデルに簡単に組み込むことができる。
  論文  参考訳（メタデータ） (2022-03-25T11:42:02Z)
• Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via Environment Manipulation [12.401344261399613]
  マルチエージェントパスフィニング(Multi-agent pathfinding)は、障害が散らばった環境において、開始時から目標地点まで、エージェントのチームが衝突のない経路を計画することに関心がある。 我々はMAPFの新たな拡張を導入し、Terraforming MAPF (tMAPF) と呼び、いくつかのエージェントが障害を移動して他のエージェントへの道をクリアする役割を担っている。 我々は、tMAPFに取り組むために、CBSとPBSという2つの最先端アルゴリズムを拡張し、静的な障害物設定で可能な限り優れた解を常に上回ることを示す。
  論文  参考訳（メタデータ） (2022-03-20T12:18:35Z)
• Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks [0.7742297876120561]
  我々は,PC-MAPF (Precedence Constrained Multi-Agent Path Finding) 問題の拡張について検討する。 そこで我々は,PC-CBS (Precedence Constrained Conflict Based Search) という新しいアルゴリズムを提案する。 本アルゴリズムは, 各種倉庫集合体, マルチエージェントピックアップ, 配送タスクに対して性能をベンチマークし, 最近提案された効率的なベースラインのサブ最適性を評価する。
  論文  参考訳（メタデータ） (2022-02-08T07:26:45Z)
• Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks [2.3204178451683264]
  スタンバイベースデッドロック回避(SBDA)と呼ばれるデッドロック回避手法を提案する。 SBDAは、調音点ファイリングアルゴリズムを用いて、リアルタイムに決定された待機ノードを使用する。 提案手法が従来の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2022-01-16T10:28:52Z)
• Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
  MAPF (Multi Agent Path Finding) は、空間的に拡張されたエージェントに対する競合のない経路の同定を必要とする。 これらは、Convoy Movement ProblemやTraning Schedulingといった現実世界の問題に適用できる。 提案手法であるDecentralized Multi Agent Path Finding (DeMAPF) は、MAPFを経路計画と割り当ての問題の系列として扱う。
  論文  参考訳（メタデータ） (2021-06-03T18:07:26Z)
• 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)

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

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