論文の概要: Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent

• arxiv url: http://arxiv.org/abs/2003.12924v1
• Date: Sun, 29 Mar 2020 02:18:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-18 13:58:01.140949
• Title: Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent
• Title（参考訳）: 確率勾配Descence を用いたマルチエージェント経路探索のための最適化方向ロードマップグラフ
• Authors: Christian Henkel and Marc Toussaint
• Abstract要約: 我々はODRM(Optimized Directed Roadmap Graph)と呼ばれる新しいアプローチを提案する。 ODRMは、マルチロボットナビゲーションにおける衝突回避を可能にする有向ロードマップグラフを構築する方法である。 実験の結果,単純な集中型プランナさえあれば,他のマルチエージェントプランナでは解決できない,多数のエージェントで解決できることがわかった。
• 参考スコア（独自算出の注目度）: 33.31762612175859
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel approach called Optimized Directed Roadmap Graph (ODRM). It is a method to build a directed roadmap graph that allows for collision avoidance in multi-robot navigation. This is a highly relevant problem, for example for industrial autonomous guided vehicles. The core idea of ODRM is, that a directed roadmap can encode inherent properties of the environment which are useful when agents have to avoid each other in that same environment. Like Probabilistic Roadmaps (PRMs), ODRM's first step is generating samples from C-space. In a second step, ODRM optimizes vertex positions and edge directions by Stochastic Gradient Descent (SGD). This leads to emergent properties like edges parallel to walls and patterns similar to two-lane streets or roundabouts. Agents can then navigate on this graph by searching their path independently and solving occurring agent-agent collisions at run-time. Using the graphs generated by ODRM compared to a non-optimized graph significantly fewer agent-agent collisions happen. We evaluate our roadmap with both, centralized and decentralized planners. Our experiments show that with ODRM even a simple centralized planner can solve problems with high numbers of agents that other multi-agent planners can not solve. Additionally, we use simulated robots with decentralized planners and online collision avoidance to show how agents are a lot faster on our roadmap than on standard grid maps.
• Abstract（参考訳）: 我々はODRM(Optimized Directed Roadmap Graph)と呼ばれる新しいアプローチを提案する。 マルチロボットナビゲーションにおける衝突回避を可能にする有向ロードマップグラフを構築する方法である。 これは、例えば産業用自動運転車両など、非常に関連する問題である。 ODRMの中核となる考え方は、有向的なロードマップは、エージェントが同じ環境で互いに避けなければならない場合に有用である環境固有の特性をエンコードできるということである。 Probabilistic Roadmaps (PRMs)のように、ODRMの最初のステップは、C空間からサンプルを生成することだ。 2番目のステップでは、Stochastic Gradient Descent (SGD) によって頂点位置とエッジ方向を最適化する。 これは壁と平行な縁のような創発的な特性と、2車線の通りやラウンドアバウトに似たパターンをもたらす。 エージェントは、そのパスを独立して検索し、実行時に発生するエージェント・エージェント衝突を解決することで、このグラフをナビゲートすることができる。 ODRMが生成するグラフを最適化されていないグラフと比較すると、エージェントとエージェントの衝突が著しく少ない。 中央集権型と分散型の両方のプランナーでロードマップを評価します。 実験の結果,odrmでは,単純な集中型プランナーでも,多数のエージェントで解決できない問題を解決できることがわかった。 さらに、分散プランナーとオンライン衝突回避を備えたシミュレーションロボットを使用して、標準的なグリッドマップよりもエージェントがロードマップ上で非常に高速であることを示す。

関連論文リスト

• Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
  提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。 我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。 古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
  論文  参考訳（メタデータ） (2024-04-25T07:41:47Z)
• Guidance Graph Optimization for Lifelong Multi-Agent Path Finding [47.51678151084153]
  MAPF(Multi-Agent Path Finding)のスループット向上のためのガイダンスの活用法について検討する。 本稿では、生涯MAPFのためのガイダンスの多目的表現としてガイダンスグラフを紹介する。 任意の寿命のMAPFアルゴリズムとマップのガイダンスを自動生成する2つのGGOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-02T14:38:04Z)
• 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)
• GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
  精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。 不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。 我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
  論文  参考訳（メタデータ） (2022-11-04T16:10:50Z)
• CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces [20.389416558418382]
  協調時間ロードマップ(CTRM)と呼ばれる新しいロードマップの概念を提案する。 CTRMは、エージェント同士の衝突を避けるために、他のエージェントの振る舞いを考慮する方法で、潜在的な溶液経路の周りの重要な位置に集中することができる。 我々は、関連する問題事例と妥当なソリューションのコレクションから生成モデルを学習する機械学習アプローチを開発した。
  論文  参考訳（メタデータ） (2022-01-24T05:43:59Z)
• 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)
• Multi-Agent Routing Value Iteration Network [88.38796921838203]
  疎結合グラフの学習値に基づいてマルチエージェントルーティングを行うことができるグラフニューラルネットワークに基づくモデルを提案する。 最大25ノードのグラフ上で2つのエージェントでトレーニングしたモデルでは,より多くのエージェントやノードを持つ状況に容易に一般化できることが示されている。
  論文  参考訳（メタデータ） (2020-07-09T22:16:45Z)

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

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