論文の概要: 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をグリッド上の一定パス長で確立できるため、注目すべきである。
関連論文リスト
- Physics-informed Neural Motion Planning on Constraint Manifolds [6.439800184169697]
Constrained Motion Planning (CMP) は、運動論的制約多様体上の与えられた開始と目標設定の間の衝突のない経路を見つけることを目的としている。
制約多様体上のアイコン方程式を解き、専門家データなしでCMPの神経機能を訓練する最初の物理インフォームドCMPフレームワークを提案する。
提案手法は,方向制約下での物体操作や,高次元6-DOFロボットマニピュレータを用いたドア開口など,シミュレーションおよび実世界の様々なCMP問題を効率的に解決する。
論文 参考訳(メタデータ) (2024-03-09T02:24:02Z) - A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman
Problem based on a Graph of Convex Sets [30.186830876548147]
本稿では,移動目標トラベリングセールスマン問題(MT-TSP)の最適解を求める新しい定式化を提案する。
問題は、補給所から始まるエージェントの最も短い経路を見つけ、割り当てられた時間ウィンドウ内で1度だけ移動対象のセットを訪れ、補給所に戻ることである。
MT-TSPのためのMICP(Mixed Conic Program)の定式化について検討した。
論文 参考訳(メタデータ) (2024-03-07T22:03:36Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳(メタデータ) (2022-09-15T07:22:58Z) - Simultaneous Contact-Rich Grasping and Locomotion via Distributed
Optimization Enabling Free-Climbing for Multi-Limbed Robots [60.06216976204385]
移動, 把握, 接触問題を同時に解くための効率的な運動計画フレームワークを提案する。
ハードウェア実験において提案手法を実証し, より短い計画時間で, 傾斜角45degで自由クライミングを含む様々な動作を実現できることを示す。
論文 参考訳(メタデータ) (2022-07-04T13:52:10Z) - 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) - Collaborative Intelligent Reflecting Surface Networks with Multi-Agent
Reinforcement Learning [63.83425382922157]
インテリジェント・リフレクション・サーフェス(IRS)は将来の無線ネットワークに広く応用されることが想定されている。
本稿では,エネルギー収穫能力を備えた協調型IRSデバイスを用いたマルチユーザ通信システムについて検討する。
論文 参考訳(メタデータ) (2022-03-26T20:37:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。