論文の概要: Robust Multi-Agent Pickup and Delivery with Delays

• arxiv url: http://arxiv.org/abs/2303.17422v1
• Date: Thu, 30 Mar 2023 14:42:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-31 13:10:31.765820
• Title: Robust Multi-Agent Pickup and Delivery with Delays
• Title（参考訳）: 遅延によるロバストなマルチエージェントピックアップとデリバリ
• Authors: Giacomo Lodigiani, Nicola Basilico, Francesco Amigoni
• Abstract要約: MAPD(Multi-Agent Pickup and Delivery)は、エージェント群に対する衝突のない経路の計算の問題である。 MAPDの現在のアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。 本稿では,不完全な実行の影響を抑える計画経路によって堅牢性を保証する2つの手法を提案する。
• 参考スコア（独自算出の注目度）: 5.287544737925232
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-Agent Pickup and Delivery (MAPD) is the problem of computing collision-free paths for a group of agents such that they can safely reach delivery locations from pickup ones. These locations are provided at runtime, making MAPD a combination between classical Multi-Agent Path Finding (MAPF) and online task assignment. Current algorithms for MAPD do not consider many of the practical issues encountered in real applications: real agents often do not follow the planned paths perfectly, and may be subject to delays and failures. In this paper, we study the problem of MAPD with delays, and we present two solution approaches that provide robustness guarantees by planning paths that limit the effects of imperfect execution. In particular, we introduce two algorithms, k-TP and p-TP, both based on a decentralized algorithm typically used to solve MAPD, Token Passing (TP), which offer deterministic and probabilistic guarantees, respectively. Experimentally, we compare our algorithms against a version of TP enriched with online replanning. k-TP and p-TP provide robust solutions, significantly reducing the number of replans caused by delays, with little or no increase in solution cost and running time.
• Abstract（参考訳）: MAPD (Multi-Agent Pickup and Delivery) は、エージェントのグループにとって衝突のない経路を計算し、ピックアップの場所から安全に配送できる問題である。 これらの場所は実行時に提供され、MAPDは古典的マルチエージェントパスファインディング(MAPF)とオンラインタスク割り当てを組み合わせたものである。 現在のMAPDのアルゴリズムは、実際のアプリケーションで遭遇する現実的な問題の多くを考慮していない。 本稿では,遅延を伴うmapdの問題について検討し,不完全実行の影響を制限するプランニングパスによるロバスト性を保証する2つの手法を提案する。 特に, 2つのアルゴリズム, k-TP と p-TP を導入し,それぞれ決定論的および確率論的保証を提供するMAPD, Token Passing (TP) を解いた。 実験では,オンラインリプランニングに富んだtpとアルゴリズムを比較した。 k-TPとp-TPはロバストなソリューションを提供し、遅延によるリプランの数を大幅に削減し、ソリューションコストと実行時間はほとんどあるいは全く増加しない。

関連論文リスト

• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  我々は任意の解法によって生成されるPOMDP実行から高品質なトレースを学習する。 我々は、データと時間効率のIndu Logic Programming(ILP)を利用して、解釈可能な信念に基づくポリシー仕様を生成する。 ASP(Answer Set Programming)で表現された学習は、ニューラルネットワークよりも優れた性能を示し、より少ない計算時間で最適な手作りタスクに類似していることを示す。
  論文  参考訳（メタデータ） (2024-02-29T15:36:01Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• An Efficient Approach to the Online Multi-Agent Path Finding Problem by Using Sustainable Information [10.367412630626834]
  多エージェント経路探索(MAPF)は、衝突せずにエージェントをゴールへ移動させる問題である。 本稿では,持続可能な情報を活用したオンラインMAPFの3段階的解決手法を提案する。 我々のアルゴリズムは、エージェント数の設定が異なる場合、平均1.48倍の速度でSOTAより高速である。
  論文  参考訳（メタデータ） (2023-01-11T13:04: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)
• Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
  絡み合いルーティングは、2つの任意のノード間のリモート絡み合い接続を確立する。 量子ネットワークにおける複数のソース・デスティネーション(SD)ペアの忠実性を保証するために、精製可能な絡み合わせルーティング設計を提案する。
  論文  参考訳（メタデータ） (2021-11-15T14:07:22Z)
• 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)
• 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)
• 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)

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

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