論文の概要: Graph Coloring to Reduce Computation Time in Prioritized Planning

• arxiv url: http://arxiv.org/abs/2501.10812v1
• Date: Sat, 18 Jan 2025 16:22:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 14:20:25.697439
• Title: Graph Coloring to Reduce Computation Time in Prioritized Planning
• Title（参考訳）: 優先計画における計算時間削減のためのグラフカラー化
• Authors: Patrick Scheffe, Julius Kahle, Bassam Alrifaee,
• Abstract要約: 本稿では,結合DAGの最長経路長を削減するため,PPの優先順位付け手法を提案する。 この問題を,結合DAGの最長経路長に対応する色数を求めるグラフカラー化問題にマッピングできることを実証する。 エージェントの優先度を決定するために,分散グラフカラー化アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Distributing computations among agents in large networks reduces computational effort in multi-agent path finding (MAPF). One distribution strategy is prioritized planning (PP). In PP, we couple and prioritize interacting agents to achieve a desired behavior across all agents in the network. We characterize the interaction with a directed acyclic graph (DAG). The computation time for solving MAPF problem using PP is mainly determined through the longest path in this DAG. The longest path depends on the fixed undirected coupling graph and the variable prioritization. The approaches from literature to prioritize agents are numerous and pursue various goals. This article presents an approach for prioritization in PP to reduce the longest path length in the coupling DAG and thus the computation time for MAPF using PP. We prove that this problem can be mapped to a graph-coloring problem, in which the number of colors required corresponds to the longest path length in the coupling DAG. We propose a decentralized graph-coloring algorithm to determine priorities for the agents. We evaluate the approach by applying it to multi-agent motion planning (MAMP) for connected and automated vehicles (CAVs) on roads using, a variant of MAPF.
• Abstract（参考訳）: 大規模ネットワークにおけるエージェント間の分散計算は、マルチエージェントパス探索(MAPF)における計算労力を削減する。 配電戦略の一つが優先順位付け計画(PP)である。 PPでは、ネットワーク内のすべてのエージェントに対して望ましい振る舞いを達成するために、相互作用するエージェントをペアで優先順位付けします。 有向非巡回グラフ(DAG)との相互作用を特徴付ける。 PPを用いたMAPF問題の解法時間は主に、このDAGにおいて最も長い経路で決定される。 最も長い経路は、固定された非方向のカップリンググラフと変数の優先順位付けに依存する。 文学からエージェントの優先順位付けへのアプローチは多岐にわたっており、様々な目標を追求している。 本稿では,結合DAGの最長経路長を削減し,PPを用いたMAPFの計算時間を短縮する手法を提案する。 この問題を,結合DAGの最長経路長に対応する色数を求めるグラフカラー化問題にマッピングできることを実証する。 エージェントの優先度を決定するために,分散グラフカラー化アルゴリズムを提案する。 MAPFの変種を用いて、道路上でのコネクテッドおよび自動走行車両(CAV)のマルチエージェント動作計画(MAMP)に適用することで、アプローチを評価する。

関連論文リスト

• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。 最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。 本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
  論文  参考訳（メタデータ） (2024-01-30T14:26:04Z)
• Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution [7.2988406091449605]
  BTPG(Bidirectional Temporal Plan Graph)と呼ばれる新しいグラフィカルな表現を導入し,実行中の注文を切り替えることで,不要な待ち時間を回避する。 実験の結果, BTPG は TPG に順調に優れ, 不要待ち時間が 8-20% 減少することがわかった。
  論文  参考訳（メタデータ） (2023-12-30T20:23:27Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  マルチエージェントパスフィンディング問題は、グラフに閉じ込められたエージェントのグループに対するコンフリクトフリーパスのセットを見つけることである。 本研究では、エージェントが他のエージェントをローカルにのみ観察できる分散MAPF設定に焦点を当てた。 MAPFタスクのための分散マルチエージェントモンテカルロ木探索法を提案する。
  論文  参考訳（メタデータ） (2023-12-26T06:57:22Z)
• Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding [29.76466191644455]
  MAPF(Multi-Agent Path Finding)は、ロボット工学における基本的な問題であり、エージェントのチームに対して衝突のない経路の計算を求める。 本稿では,MAPFにエージェントを誘導する手法を提案する。 各エージェントが1つの宛先を持つワンショットMAPFと、エージェントが常に新しい宛先を割り当てる終身MAPFの2つの大規模設定でこのアイデアを評価する。
  論文  参考訳（メタデータ） (2023-08-22T07:17:39Z)
• A fast topological approach for predicting anomalies in time-varying graphs [0.0]
  トポロジカルデータ解析(TDA)からの永続化ダイアグラム(PD)は、点間距離が明確に定義されたデータ形状記述法として人気がある。 本稿では,グラフデータから形状情報を抽出する計算効率の良いフレームワークを提案する。 実際のデータアプリケーションでは、暗号取引ネットワークの異常な価格予測において、我々のアプローチは最大で22%上昇する。
  論文  参考訳（メタデータ） (2023-05-11T01:54:45Z)
• GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
  精度や一般化を犠牲にすることなく、全てのエージェントとマップに対して効率的な共有符号化を提案する。 不均一空間グラフにおけるエージェントとマップ要素間の幾何学的関係を表現するために、ペアワイズ相対的な位置符号化を利用する。 我々のデコーダは視点非依存であり、レーングラフ上でエージェント目標を予測し、多様かつコンテキスト対応のマルチモーダル予測を可能にする。
  論文  参考訳（メタデータ） (2022-11-04T16:10:50Z)
• Direct Dense Pose Estimation [138.56533828316833]
  複雑な人間のポーズ推定は、RGB画像と人体の表面との密接な対応を学習する問題である。 従来より密集したポーズ推定手法は、すべてMask R-CNNフレームワークに基づいており、まず各人物のバウンディングボックスを識別しようとするトップダウン方式で動作している。 そこで我々は,DDP (Direct Dense Pose) という,高密度ポーズ推定問題の解法を提案する。
  論文  参考訳（メタデータ） (2022-04-04T06:14:38Z)
• Spatio-Temporal Joint Graph Convolutional Networks for Traffic Forecasting [75.10017445699532]
  近年、時間グラフモデリング問題として交通予測の定式化に焦点が移っている。 本稿では,道路網における交通予測の精度向上のための新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-11-25T08:45:14Z)
• 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)

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

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