論文の概要: Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and
Delivery Tasks
- arxiv url: http://arxiv.org/abs/2201.06014v2
- Date: Wed, 19 Jan 2022 02:44:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-20 12:12:01.832390
- Title: Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and
Delivery Tasks
- Title(参考訳): マルチエージェントピックアップおよび配送タスクのためのスタンバイベースデッドロック回避方法
- Authors: Tomoki Yamauchi, Yuki Miyashita and Toshiharu Sugawara
- Abstract要約: スタンバイベースデッドロック回避(SBDA)と呼ばれるデッドロック回避手法を提案する。
SBDAは、調音点ファイリングアルゴリズムを用いて、リアルタイムに決定された待機ノードを使用する。
提案手法が従来の手法より優れていることを示す。
- 参考スコア(独自算出の注目度): 2.3204178451683264
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The multi-agent pickup and delivery (MAPD) problem, in which multiple agents
iteratively carry materials without collisions, has received significant
attention. However, many conventional MAPD algorithms assume a specifically
designed grid-like environment, such as an automated warehouse. Therefore, they
have many pickup and delivery locations where agents can stay for a lengthy
period, as well as plentiful detours to avoid collisions owing to the freedom
of movement in a grid. By contrast, because a maze-like environment such as a
search-and-rescue or construction site has fewer pickup/delivery locations and
their numbers may be unbalanced, many agents concentrate on such locations
resulting in inefficient operations, often becoming stuck or deadlocked. Thus,
to improve the transportation efficiency even in a maze-like restricted
environment, we propose a deadlock avoidance method, called standby-based
deadlock avoidance (SBDA). SBDA uses standby nodes determined in real-time
using the articulation-point-finding algorithm, and the agent is guaranteed to
stay there for a finite amount of time. We demonstrated that our proposed
method outperforms a conventional approach. We also analyzed how the parameters
used for selecting standby nodes affect the performance.
- Abstract(参考訳): 複数のエージェントが衝突せずに反復的に材料を運ぶマルチエージェントピックアップ・アンド・デリバリー(MAPD)問題に注目が集まっている。
しかし、従来のMAPDアルゴリズムの多くは、自動倉庫など、特定の設計のグリッドのような環境を前提としている。
そのため、長い期間エージェントが滞在できるピックアップと配送の場所が多く、またグリッド内の移動の自由による衝突を避けるために多くの回り道がある。
対照的に、捜索救助や建設現場のような迷路のような環境は、ピックアップ/配達の場所が少なく、その数は不均衡である可能性があるため、多くのエージェントはそのような場所に集中し、効率の悪さを招き、しばしば立ち往生またはデッドロックされる。
そこで我々は,迷路型制限環境においても輸送効率を向上させるために,スタンバイベースデッドロック回避(SBDA)と呼ばれるデッドロック回避手法を提案する。
SBDAは調音点探索アルゴリズムを用いてリアルタイムに決定された待機ノードを使用し、エージェントは有限時間滞在することが保証される。
提案手法が従来の手法より優れていることを示す。
また,待機ノード選択のパラメータが性能に与える影響についても検討した。
関連論文リスト
- Terraforming -- Environment Manipulation during Disruptions for
Multi-Agent Pickup and Delivery [11.034208232337749]
自動倉庫では、在庫ポッドを指定されたワークステーションに移動させ、密集したポッドで形成された狭い通路を航行することで、移動ロボットのチームがパッケージングプロセスを満たす。
この問題は一般にMAPD(Multi-Agent Pickup and Delivery)問題としてモデル化され、固定グラフ上のエージェントに対する衝突のない経路を繰り返し計画することで解決される。
既存のアプローチでは、エージェントは現在のタスクに対応するポッドのみを動かすことができるという仮定が制限されているが、他のポッドは静止障害である(全てのポッドが可動しているにもかかわらず)。
この行動は、ポッド操作を介して追加の回廊を開くことで避けられる必要のない長い経路をもたらす可能性がある。
論文 参考訳(メタデータ) (2023-05-19T08:19:24Z) - DIR-AS: Decoupling Individual Identification and Temporal Reasoning for
Action Segmentation [84.78383981697377]
完全な教師付きアクションセグメンテーションは、高密度アノテーションによるフレームワイドアクション認識に作用し、しばしば過剰なセグメンテーションの問題に悩まされる。
本研究では, 時間的ピラミッド拡張と時間的ピラミッドプールを併用して, 効率的なマルチスケールアテンションを実現するため, 新たなローカル・グローバルアテンション機構を開発した。
GTEAでは82.8%(+2.6%)、Breakfastでは74.7%(+1.2%)の精度を実現し,本手法の有効性を示した。
論文 参考訳(メタデータ) (2023-04-04T20:27:18Z) - Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。
MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。
本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
論文 参考訳(メタデータ) (2023-03-30T14:42:41Z) - Traj-MAE: Masked Autoencoders for Trajectory Prediction [69.7885837428344]
軌道予測は、危険を予測して信頼性の高い自動運転システムを構築する上で重要な課題である。
本稿では,運転環境におけるエージェントの複雑な動作をよりよく表現する,軌道予測のための効率的なマスク付きオートエンコーダを提案する。
複数エージェント設定と単一エージェント設定の両方の実験結果から,Traj-MAEが最先端手法と競合する結果が得られることが示された。
論文 参考訳(メタデータ) (2023-03-12T16:23:27Z) - Reinforcement Learning with a Terminator [80.34572413850186]
我々は, TerMDP のパラメータを学習し, 推定問題の構造を活用し, 状態ワイドな信頼境界を提供する。
我々はこれらを用いて証明可能な効率のよいアルゴリズムを構築し、終端を考慮し、その後悔を抑える。
論文 参考訳(メタデータ) (2022-05-30T18:40:28Z) - Deadlock-Free Method for Multi-Agent Pickup and Delivery Problem Using
Priority Inheritance with Temporary Priority [2.064612766965483]
本稿では,PIBT法を用いて優先度継承を拡張することで,マルチエージェントピックアップ・デリバリ問題(MAPD問題)の制御手法を提案する。
PIBTは、バイコネクテッドな領域としてモデル化された環境にのみ適用でき、木のような死の端を含む場合、PIBTはデッドロックを引き起こす可能性がある。
提案手法は,PIBT機能を保ちながら,デッドロックを伴わずに,木形パスのある環境でMAPDタスクを実行できる。
論文 参考訳(メタデータ) (2022-05-25T05:45:22Z) - 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) - 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) - Stochastic bandits with arm-dependent delays [102.63128271054741]
我々は、単純なUCBベースのアルゴリズムであるPatentBanditsを提案する。
問題に依存しない境界も問題に依存しない境界も、性能の低い境界も提供します。
論文 参考訳(メタデータ) (2020-06-18T12:13:58Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳(メタデータ) (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。