Combinatorics of a Discrete Trajectory Space for Robot Motion Planning

• URL: http://arxiv.org/abs/2005.12064v1
• Date: Mon, 25 May 2020 12:14:20 GMT
• Title: Combinatorics of a Discrete Trajectory Space for Robot Motion Planning
• Abstract summary: complexity of the problem is directly related to the dimension of the robot's configuration space. We present a discrete robot model based on the fundamental hardware specifications of a robot.
• Score: 4.477410849696538
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motion planning is a difficult problem in robot control. The complexity of the problem is directly related to the dimension of the robot's configuration space. While in many theoretical calculations and practical applications the configuration space is modeled as a continuous space, we present a discrete robot model based on the fundamental hardware specifications of a robot. Using lattice path methods, we provide estimates for the complexity of motion planning by counting the number of possible trajectories in a discrete robot configuration space.

Related papers

• Simulation-Informed Diffusion for Decentralized Multi-robot Motion Planning [56.240199425429445]
  Multi-robot motion planning requires each robot to generate collision-free trajectories from local observations.<n>Most existing planners generate trajectories from a static snapshot of the local observation.<n>This paper introduces Simulation-Informed Diffusion (SID), a decentralized framework built on constraint-aware diffusion models.
  arXiv  Detail & Related papers  (2026-05-26T21:17:53Z)
• Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement [0.9199488958939335]
  A fundamental challenge in multi-robot motion planning is achieving sufficient coordination without incurring the large computational expense of searching the joint configuration space of the robot group.<n>We present a method for multiple mobile robot motion planning that achieves an improvement in planning time up to an order of magnitude by leveraging the insight that we can use discrete search over a workspace decomposition to provide coordination between robots during planning.
  arXiv  Detail & Related papers  (2026-05-19T18:44:09Z)
• Fast Motion Planning for Non-Holonomic Mobile Robots via a Rectangular Corridor Representation of Structured Environments [43.11194204846493]
  We present a complete framework for fast motion planning of non-holonomic autonomous mobile robots.<n>Our approach introduces a deterministic free-space decomposition that creates a compact graph of overlapping rectangular corridors.<n>The framework then performs online motion planning by finding a sequence of rectangles and generating a near-time-optimal, kinematically-feasible trajectory.
  arXiv  Detail & Related papers  (2026-02-10T12:18:14Z)
• Efficient Computation of a Continuous Topological Model of the Configuration Space of Tethered Mobile Robots [9.67618824743514]
  We build a topological model of the configuration space of a tethered robot starting from a polygonal representation of the workspace where the robot moves.<n>We show how this approach improves the performances of existing algorithms that build other types of representations of the configuration space.<n>The proposed model can be computed in a fraction of the time required to build traditional homotopy-augmented graphs.
  arXiv  Detail & Related papers  (2025-12-08T08:45:17Z)
• Deploying Foundation Model-Enabled Air and Ground Robots in the Field: Challenges and Opportunities [65.98704516122228]
  The integration of foundation models (FMs) into robotics has enabled robots to understand natural language and reason about the semantics in their environments.<n>This paper addresses the deployment of FM-enabled robots in the field, where missions often require a robot to operate in large-scale and unstructured environments.<n>We present the first demonstration of large-scale LLM-enabled robot planning in unstructured environments with several kilometers of missions.
  arXiv  Detail & Related papers  (2025-05-14T15:28:43Z)
• Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models [57.45019514036948]
  Simultaneous MRMP Diffusion (SMD) is a novel approach integrating constrained optimization into the diffusion sampling process to produce kinematically feasible trajectories. The paper introduces a comprehensive MRMP benchmark to evaluate trajectory planning algorithms across scenarios with varying robot densities, obstacle complexities, and motion constraints.
  arXiv  Detail & Related papers  (2025-02-05T20:51:28Z)
• Unifying 3D Representation and Control of Diverse Robots with a Single Camera [48.279199537720714]
  We introduce Neural Jacobian Fields, an architecture that autonomously learns to model and control robots from vision alone. Our approach achieves accurate closed-loop control and recovers the causal dynamic structure of each robot.
  arXiv  Detail & Related papers  (2024-07-11T17:55:49Z)
• RoboScript: Code Generation for Free-Form Manipulation Tasks across Real and Simulation [77.41969287400977]
  This paper presents textbfRobotScript, a platform for a deployable robot manipulation pipeline powered by code generation. We also present a benchmark for a code generation benchmark for robot manipulation tasks in free-form natural language. We demonstrate the adaptability of our code generation framework across multiple robot embodiments, including the Franka and UR5 robot arms.
  arXiv  Detail & Related papers  (2024-02-22T15:12:00Z)
• Neural Potential Field for Obstacle-Aware Local Motion Planning [46.42871544295734]
  We propose a neural network model that returns a differentiable collision cost based on robot pose, obstacle map, and robot footprint. Our architecture includes neural image encoders, which transform obstacle maps and robot footprints into embeddings. Experiment on Husky UGV mobile robot showed that our approach allows real-time and safe local planning.
  arXiv  Detail & Related papers  (2023-10-25T05:00:21Z)
• Direct Robot Configuration Space Construction using Convolutional Encoder-Decoders [7.780531445879181]
  We apply a convolutional encoder-decoder framework for calculating highly accurate approximations to configuration spaces. Our model achieves an average 97.5% F1-score for predicting C-free and C-clsn for 2-D robotic workspaces with a dual-arm robot.
  arXiv  Detail & Related papers  (2023-03-10T02:08:56Z)
• Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance [2.846144602096543]
  Multi-robot motion planning (MRMP) is the problem of finding collision-free paths for a set of robots in a continuous state space. We extend an existing single-robot motion planning method to leverage the improved efficiency provided by topological guidance. We demonstrate our method's ability to efficiently plan paths in complex environments with many narrow passages, scaling to robot teams of size up to 25 times larger than existing methods.
  arXiv  Detail & Related papers  (2022-10-13T16:26:01Z)
• Simultaneous Contact-Rich Grasping and Locomotion via Distributed Optimization Enabling Free-Climbing for Multi-Limbed Robots [60.06216976204385]
  We present an efficient motion planning framework for simultaneously solving locomotion, grasping, and contact problems. We demonstrate our proposed framework in the hardware experiments, showing that the multi-limbed robot is able to realize various motions including free-climbing at a slope angle 45deg with a much shorter planning time.
  arXiv  Detail & Related papers  (2022-07-04T13:52:10Z)
• SABER: Data-Driven Motion Planner for Autonomously Navigating Heterogeneous Robots [112.2491765424719]
  We present an end-to-end online motion planning framework that uses a data-driven approach to navigate a heterogeneous robot team towards a global goal. We use model predictive control (SMPC) to calculate control inputs that satisfy robot dynamics, and consider uncertainty during obstacle avoidance with chance constraints. recurrent neural networks are used to provide a quick estimate of future state uncertainty considered in the SMPC finite-time horizon solution. A Deep Q-learning agent is employed to serve as a high-level path planner, providing the SMPC with target positions that move the robots towards a desired global goal.
  arXiv  Detail & Related papers  (2021-08-03T02:56:21Z)
• Large Scale Distributed Collaborative Unlabeled Motion Planning with Graph Policy Gradients [122.85280150421175]
  We present a learning method to solve the unlabelled motion problem with motion constraints and space constraints in 2D space for a large number of robots. We employ a graph neural network (GNN) to parameterize policies for the robots.
  arXiv  Detail & Related papers  (2021-02-11T21:57:43Z)
• Towards Multi-Robot Task-Motion Planning for Navigation in Belief Space [1.4824891788575418]
  We present an integrated multi-robot task-motion planning framework for navigation in knowledge-intensive domains. In particular, we consider a distributed multi-robot setting incorporating mutual observations between the robots. The framework is intended for motion planning under motion and sensing uncertainty, which is formally known as belief space planning.
  arXiv  Detail & Related papers  (2020-10-01T06:45:17Z)
• Predicting Sample Collision with Neural Networks [5.713670854553366]
  We present a framework to address the cost of expensive primitive operations in sampling-based motion planning. We evaluate our framework on multiple planning problems with a variety of robots in 2D and 3D workspaces.
  arXiv  Detail & Related papers  (2020-06-30T14:56:14Z)
• Piecewise linear regressions for approximating distance metrics [1.1241621778067437]
  This paper presents a data structure that summarizes distances between configurations across a robot configuration space. The paper explores the use of the data structure constructed for a single robot to provide a for challenging multi-robot motion planning problems.
  arXiv  Detail & Related papers  (2020-02-27T22:23:58Z)

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.