論文の概要: Optimal Multi-Agent Path Finding for Precedence Constrained Planning
Tasks
- arxiv url: http://arxiv.org/abs/2202.10449v1
- Date: Tue, 8 Feb 2022 07:26:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-27 21:38:57.221333
- Title: Optimal Multi-Agent Path Finding for Precedence Constrained Planning
Tasks
- Title(参考訳): 事前制約のある計画タスクのための最適マルチエージェント経路探索
- Authors: Kushal Kedia, Rajat Kumar Jenamani, Aritra Hazra, Partha Pratim
Chakrabarti
- Abstract要約: 我々は,PC-MAPF (Precedence Constrained Multi-Agent Path Finding) 問題の拡張について検討する。
そこで我々は,PC-CBS (Precedence Constrained Conflict Based Search) という新しいアルゴリズムを提案する。
本アルゴリズムは, 各種倉庫集合体, マルチエージェントピックアップ, 配送タスクに対して性能をベンチマークし, 最近提案された効率的なベースラインのサブ最適性を評価する。
- 参考スコア(独自算出の注目度): 0.7742297876120561
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-Agent Path Finding (MAPF) is the problem of finding collision-free
paths for multiple agents from their start locations to end locations. We
consider an extension to this problem, Precedence Constrained Multi-Agent Path
Finding (PC-MAPF), wherein agents are assigned a sequence of planning tasks
that contain precedence constraints between them. PC-MAPF has various
applications, for example in multi-agent pickup and delivery problems where
some objects might require multiple agents to collaboratively pickup and move
them in unison. Precedence constraints also arise in warehouse assembly
problems where before a manufacturing task can begin, its input resources must
be manufactured and delivered. We propose a novel algorithm, Precedence
Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal
solutions for this class of problems. PC-CBS utilizes a Precedence-Constrained
Task-Graph to define valid intervals for each planning task and updates them
when precedence conflicts are encountered. We benchmark the performance of this
algorithm over various warehouse assembly, and multi-agent pickup and delivery
tasks, and use it to evaluate the sub-optimality of a recently proposed
efficient baseline.
- Abstract(参考訳): MAPF(Multi-Agent Path Finding)は、開始地点から終了地点まで複数のエージェントの衝突のない経路を見つける問題である。
本稿では,PC-MAPF(Precedence Constrained Multi-Agent Path Finding)という,先行制約を含む計画タスクの順序をエージェントに割り当てる手法を提案する。
pc-mapfには様々な用途があり、例えばマルチエージェントピックアップや配送問題では、複数のエージェントが協調してそれらをピックアップして移動させる必要がある。
また、製造作業が開始される前に、その入力資源を製造・納入しなければならない倉庫組立問題にも先行制約が生じる。
そこで本研究では,本問題の最適解を求める新しいアルゴリズム,precedence restricteded conflict based search (pc-cbs)を提案する。
PC-CBSはPrecedence-Constrained Task-Graphを使用して、各計画タスクの有効間隔を定義し、優先順位の衝突が発生したときに更新する。
我々は,このアルゴリズムの性能を様々な倉庫アセンブリ,マルチエージェントピックアップおよび配送タスク上でベンチマークし,最近提案する効率的なベースラインのサブ最適化性を評価する。
関連論文リスト
- Optimal Task Assignment and Path Planning using Conflict-Based Search
with Precedence and Temporal Constraints [5.9176395108304805]
本稿では,TAPF-PTC問題におけるタスク割り当てと経路探索について検討する。
我々は、競合ベースの検索(CBS)を拡張して、優先度と時間的制約に従うタスク割り当てと衝突のない経路を同時に生成する。
実験により,我々のアルゴリズムであるCBS-TA-PTCは,優先度と時間的制約を効果的に解決できることを示した。
論文 参考訳(メタデータ) (2024-02-13T20:07:58Z) - Scalable Mechanism Design for Multi-Agent Path Finding [90.68703851865585]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが特定の目標地点に向かって共有領域を同時に移動するための経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似アルゴリズムを用いることが不可欠である。
本稿では,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) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳(メタデータ) (2023-07-25T12:33:53Z) - Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。
MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。
本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
論文 参考訳(メタデータ) (2023-03-30T14:42:41Z) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
本稿では,複数エージェントの結合状態空間の予測被覆時間を最小化し,マルチエージェントオプションを構築するマルチエージェントDeep Covering Option Discoveryを提案する。
また、MARLプロセスにマルチエージェントオプションを採用するための新しいフレームワークを提案する。
提案アルゴリズムは,アテンション機構とエージェントの相互作用を効果的に把握し,マルチエージェントオプションの同定に成功した。
論文 参考訳(メタデータ) (2022-10-07T00:40:59Z) - MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal
Sequencing and Path Finding [10.354181009277623]
監視やロジスティクスといったマルチエージェントアプリケーションでは、多数のモバイルエージェントが協調し、多数の目標地点を安全に訪問することがしばしば期待されている。
本稿では、このマルチエージェント問題に対する最適解を計算するMS*と呼ばれる新しいアルゴリズムを紹介します。
計算結果から,提案アルゴリズムは標準ラップトップ上でのCPU時間1分で20エージェント,50ゴールのマルチエージェント問題を解くことができることがわかった。
論文 参考訳(メタデータ) (2021-03-18T01:57:35Z) - Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
k-Robust Conflict-BasedSearch (k-CBS)は、最大k遅延のロバストな座標と衝突のない計画を生成するアルゴリズムです。
そこで我々は,k-robust計画に特有な様々な対称性の破れ制約を導入し,矛盾するエージェントのペアに対して,効率よく相反する最適経路を見つける。
論文 参考訳(メタデータ) (2021-02-17T11:09:33Z) - 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) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳(メタデータ) (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。