論文の概要: The Parameterized Complexity of Coordinated Motion Planning

• arxiv url: http://arxiv.org/abs/2312.07144v2
• Date: Sat, 16 Dec 2023 22:16:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-19 19:10:21.313153
• Title: The Parameterized Complexity of Coordinated Motion Planning
• Title（参考訳）: 協調運動計画のパラメータ化複雑性
• Authors: Eduard Eiben, Robert Ganian, Iyad Kanj
• Abstract要約: コーディネート・モーション・プランニング(CMP)では、$k$ロボットが異なるスタート・グリッドポイントを$k$で占有し、異なる目的地・グリッドポイントに$k$で到達する必要がある。 目標は、目標目標を最小限に抑えるために、$k$のロボットを目的地に移動するためのスケジュールを計算することだ。 本稿では,CMP-MとCMP-Lのパラメータ化複雑性を2つの基本パラメータについて検討する。
• 参考スコア（独自算出の注目度）: 28.39902924923273
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which $k$ robots occupy $k$ distinct starting gridpoints and need to reach $k$ distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the $k$ robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous $(n^2-1)$-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids.
• Abstract（参考訳）: コーディネートドモーションプランニング(cmp)では、k$ロボットが異なる出発グリッドポイントを占有し、k$の異なる目的地グリッドポイントに到達する必要がある矩形グリッドが与えられます。 それぞれの時間ステップで、他のロボットと衝突しない場合、どのロボットも隣のグリッドポイントに移動したり、現在のグリッドポイントにとどまったりすることができる。 目標は、k$ロボットを目的地に移動させるスケジュールを計算し、スケジュール内の時間ステップの数、すなわち、ロボットが移動する総長さを、目標とする目標を最小化することである。 対象目標の最小化から生じる問題を,CMP-M,後者をCMP-Lと呼ぶ。 CMP-M と CMP-L はどちらも SoCG 2021 の計算幾何学的挑戦として提起された基本的な問題であり、CMP は特殊ケースとして有名な$(n^2-1)$-puzzle も具体化している。 本稿では,CMP-MとCMP-Lのパラメータ化複雑性を,ロボットの数と対象目標の2つの最も基本的なパラメータについて検討する。 本研究は,従来のパラメータ化の下で,問題の最適解に関する新たな構造的洞察に依存した,両問題の固定パラメータトラクタビリティを確立するための新しいアプローチを開発する。 対象目標によってパラメータ化されると、CMP-MがパラNPハードとなる間、CMP-Lは固定パラメータ抽出可能であることを示す。 後者の結果は、以前知られていた問題に対する難解性の境界を改良するだけでなく、基礎的な縮小によって、従来のVertex DisjointとEdge Disjoint PathsのNP-hardnessをグリッド上の一定パス長で確立できるため、注目すべきである。

関連論文リスト

• Large-Scale Multi-Robot Coverage Path Planning on Grids with Path Deconfliction [2.5580729045474015]
  マルチロボット被覆経路計画(MCPP: Multi-Robot Coverage Path Planning)を4つの隣接する2DグリッドG上で検討し、複数のロボットがGのすべてのセルをカバーする経路を計算することを目的とした。 問題を直接Gで修正し、グリッドベースのMCPPの解法を革新し、新しいNP硬度結果を確立する。 提案手法は,最大100台のロボットを最大256x256まで実行時間内にグリッド上で管理することにより,ソリューションの品質と効率を大幅に向上することを示す。
  論文  参考訳（メタデータ） (2024-11-03T22:37:56Z)
• A Meta-Engine Framework for Interleaved Task and Motion Planning using Topological Refinements [51.54559117314768]
  タスク・アンド・モーション・プランニング(タスク・アンド・モーション・プランニング、TAMP)は、自動化された計画問題の解決策を見つけるための問題である。 本稿では,TAMP問題のモデル化とベンチマークを行うための,汎用的でオープンソースのフレームワークを提案する。 移動エージェントと複数のタスク状態依存障害を含むTAMP問題を解決する革新的なメタ技術を導入する。
  論文  参考訳（メタデータ） (2024-08-11T14:57:57Z)
• Message-Passing Monte Carlo: Generating low-discrepancy point sets via Graph Neural Networks [64.39488944424095]
  本稿では,Message-Passing Monte Carlo という低差点集合を生成する機械学習手法を提案する。 MPMC点は、低次元と少数の点との差に関して、最適かほぼ最適であることが実証的に示されている。
  論文  参考訳（メタデータ） (2024-05-23T21:17:20Z)
• Physics-informed Neural Motion Planning on Constraint Manifolds [6.439800184169697]
  Constrained Motion Planning (CMP) は、運動論的制約多様体上の与えられた開始と目標設定の間の衝突のない経路を見つけることを目的としている。 制約多様体上のアイコン方程式を解き、専門家データなしでCMPの神経機能を訓練する最初の物理インフォームドCMPフレームワークを提案する。 提案手法は,方向制約下での物体操作や,高次元6-DOFロボットマニピュレータを用いたドア開口など,シミュレーションおよび実世界の様々なCMP問題を効率的に解決する。
  論文  参考訳（メタデータ） (2024-03-09T02:24:02Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Intelligent Trajectory Design for RIS-NOMA aided Multi-robot Communications [59.34642007625687]
  目的は,ロボットの軌道とNOMA復号命令を協調的に最適化することで,マルチロボットシステムにおける全軌道の総和率を最大化することである。 ARIMAモデルとDouble Deep Q-network (D$3$QN)アルゴリズムを組み合わせたML方式を提案する。
  論文  参考訳（メタデータ） (2022-05-03T17:14:47Z)
• Convex Optimization for Parameter Synthesis in MDPs [19.808494349302784]
  確率論的モデル検査は、マルコフ決定プロセスが時間論理の仕様を満たすかどうかを証明することを目的としている。 我々は、局所最適実行時ソリューションを反復的に得る2つのアプローチを開発する。 数十万のパラメータを持つ衛星パラメータ合成問題に対するアプローチと,その拡張性を,広く使用されているベンチマーク上で実証する。
  論文  参考訳（メタデータ） (2021-06-30T21:23:56Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes [7.766921168069532]
  複数のロボット(MRPP)の経路計画は、ロボットが最初の位置から指定された目標位置までナビゲートできる非衝突経路を見つけるタスクを表します。 本稿では,既存の SAT ベースの MRPP アルゴリズムを,対象の Boolean 符号化を導出する各ロボットの候補経路の集合を分割することで拡張する。
  論文  参考訳（メタデータ） (2021-03-08T00:57:42Z)
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization [76.51980153902774]
  フェデレーテッド・ラーニング(FL)はパラメータ伝達中にFLモデルに対する外部攻撃に対して脆弱である。 本稿では,最先端の防御アグリゲーション機構に対処する有効なMPアルゴリズムを提案する。 実験の結果,提案したCMPアルゴリズムは,既存の攻撃機構よりも効果的で,かなり優れていることが示された。
  論文  参考訳（メタデータ） (2021-01-28T03:28:18Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)

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

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