The Parameterized Complexity of Coordinated Motion Planning

• URL: http://arxiv.org/abs/2312.07144v2
• Date: Sat, 16 Dec 2023 22:16:55 GMT
• Title: The Parameterized Complexity of Coordinated Motion Planning
• Authors: Eduard Eiben, Robert Ganian, Iyad Kanj
• Abstract summary: In Coordinated Motion Planning (CMP), $k$ robots occupy $k$ distinct starting gridpoints and need to reach $k$ distinct destination gridpoints. The goal is to compute a schedule for moving the $k$ robots to their destinations which minimizes a certain objective target. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters.
• Score: 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.

Related papers

• Large-Scale Multi-Robot Coverage Path Planning on Grids with Path Deconfliction [2.5580729045474015]
  We study Multi-Robot Coverage Path Planning (MCPP) on a 4-neighbor 2D grid G, which aims to compute paths for multiple robots to cover all cells of G. We reformulate the problem directly on G, revolutionizing grid-based MCPP solving and establishing new NP-hardness results. We show that our approach significantly improves solution quality and efficiency, managing up to 100 robots on grids as large as 256x256 within minutes of runtime.
  arXiv  Detail & Related papers  (2024-11-03T22:37:56Z)
• A Meta-Engine Framework for Interleaved Task and Motion Planning using Topological Refinements [51.54559117314768]
  Task And Motion Planning (TAMP) is the problem of finding a solution to an automated planning problem. We propose a general and open-source framework for modeling and benchmarking TAMP problems. We introduce an innovative meta-technique to solve TAMP problems involving moving agents and multiple task-state-dependent obstacles.
  arXiv  Detail & Related papers  (2024-08-11T14:57:57Z)
• Message-Passing Monte Carlo: Generating low-discrepancy point sets via Graph Neural Networks [64.39488944424095]
  We present the first machine learning approach to generate low-discrepancy point sets named Message-Passing Monte Carlo points. MPMC points are empirically shown to be either optimal or near-optimal with respect to the discrepancy for low dimension and small number of points.
  arXiv  Detail & Related papers  (2024-05-23T21:17:20Z)
• Physics-informed Neural Motion Planning on Constraint Manifolds [6.439800184169697]
  Constrained Motion Planning (CMP) aims to find a collision-free path between the given start and goal configurations on the kinematic constraint manifold. We propose the first physics-informed CMP framework that solves the Eikonal equation on the constraint manifold and trains neural function for CMP without expert data. Our results show that the proposed approach efficiently solves various CMP problems in both simulation and real-world, including object manipulation under orientation constraints and door opening with a high-dimensional 6-DOF robot manipulator.
  arXiv  Detail & Related papers  (2024-03-09T02:24:02Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Intelligent Trajectory Design for RIS-NOMA aided Multi-robot Communications [59.34642007625687]
  The goal is to maximize the sum-rate of whole trajectories for multi-robot system by jointly optimizing trajectories and NOMA decoding orders of robots. An integrated machine learning (ML) scheme is proposed, which combines long short-term memory (LSTM)-autoregressive integrated moving average (ARIMA) model and dueling double deep Q-network (D$3$QN) algorithm.
  arXiv  Detail & Related papers  (2022-05-03T17:14:47Z)
• Convex Optimization for Parameter Synthesis in MDPs [19.808494349302784]
  Probabilistic model checking aims to prove whether a Markov decision process satisfies a temporal logic specification. We develop two approaches that iteratively obtain locally optimal runtime solutions. We demonstrate the approaches on a satellite parameter synthesis problem with hundreds of thousands of parameters and their scalability on a wide range of commonly used benchmarks.
  arXiv  Detail & Related papers  (2021-06-30T21:23:56Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes [7.766921168069532]
  Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots through which they can navigate from their initial positions to specified goal positions. In this paper, we enhance existing SAT-based algorithm for MRPP via spartification of the set of candidate paths for each robot from which target Boolean encoding is derived.
  arXiv  Detail & Related papers  (2021-03-08T00:57:42Z)
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization [76.51980153902774]
  Federated learning (FL) is vulnerable to external attacks on FL models during parameters transmissions. In this paper, we propose effective MP algorithms to combat state-of-the-art defensive aggregation mechanisms. Our experimental results demonstrate that the proposed CMP algorithms are effective and substantially outperform existing attack mechanisms.
  arXiv  Detail & Related papers  (2021-01-28T03:28:18Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  This paper considers the peak Constrained Markov Decision Process (PCMDP), where the agent chooses the policy to maximize total reward in the finite horizon as well as satisfy constraints at each epoch with probability 1. We propose a model-free algorithm that converts PCMDP problem to an unconstrained problem and a Q-learning based approach is applied.
  arXiv  Detail & Related papers  (2020-03-11T23:23:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.