Computational Tradeoff in Minimum Obstacle Displacement Planning for Robot Navigation

• URL: http://arxiv.org/abs/2302.07114v1
• Date: Tue, 14 Feb 2023 15:17:40 GMT
• Title: Computational Tradeoff in Minimum Obstacle Displacement Planning for Robot Navigation
• Abstract summary: We look into the minimum obstacle displacement (MOD) planning problem from a mobile robot motion planning perspective. This problem finds an optimal path to goal by displacing movable obstacles when no path exists due to collision with obstacles. This work looks into approximate solutions that are computationally less intensive and differ from the optimal solution by a factor of the optimal cost.
• Score: 1.6058099298620423
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we look into the minimum obstacle displacement (MOD) planning problem from a mobile robot motion planning perspective. This problem finds an optimal path to goal by displacing movable obstacles when no path exists due to collision with obstacles. However this problem is computationally expensive and grows exponentially in the size of number of movable obstacles. This work looks into approximate solutions that are computationally less intensive and differ from the optimal solution by a factor of the optimal cost.

Related papers

• Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles [49.315843050082925]
  We present a bi approach for minimum-time motion planning convex obstacles that is guaranteed to converge.<n>We find that the proposed method produces high-quality trajectories with times to produce state-of-the-art decomposition of variables.
  arXiv  Detail & Related papers  (2026-08-03T19:48:24Z)
• Navigating the Clutter: Waypoint-Based Bi-Level Planning for Multi-Robot Systems [54.887871365121775]
  Multi-robot control in cluttered environments is a challenging problem that involves complex physical constraints.<n>We propose a hybrid multi-robot control framework that jointly optimize task and motion planning.<n>Our approach consistently improves task success over motion-agnostic and VLA-based baselines.
  arXiv  Detail & Related papers  (2026-04-22T22:58:47Z)
• Local Path Optimization in The Latent Space Using Learned Distance Gradient [14.220732305518583]
  Constrained motion planning is a common but challenging problem in robotic manipulation.<n>In this paper, we propose a method that trains a neural network to predict the minimum distance between the robot and obstacles.<n>The learned distance gradient is then used to calculate the direction of movement in the latent space to move the robot away from obstacles.
  arXiv  Detail & Related papers  (2025-12-30T14:56:09Z)
• Locally Optimal Solutions to Constraint Displacement Problems via Path-Obstacle Overlaps [2.80151930790841]
  We present a unified approach for constraint displacement problems in which a robot finds a feasible path by displacing constraints or obstacles.<n>Several examples are provided that successfully demonstrate our approach on two distinct classes of constraint displacement problems.
  arXiv  Detail & Related papers  (2025-11-15T13:14:30Z)
• Search-Based Path Planning among Movable Obstacles [8.023424148846265]
  This paper introduces two PAMO formulations, i.e., bi-objective and resource constrained problems in an occupancy grid. We develop PAMO*, a search method with completeness and solution optimality guarantees, to solve the two problems. We then extend PAMO* to hybrid-state PAMO* to plan in continuous spaces with high-fidelity interaction between the robot and the objects.
  arXiv  Detail & Related papers  (2024-10-24T00:02:58Z)
• 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)
• 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)
• POA: Passable Obstacles Aware Path-planning Algorithm for Navigation of a Two-wheeled Robot in Highly Cluttered Environments [53.41594627336511]
  Passable Obstacles Aware (POA) planner is a novel navigation method for two-wheeled robots in a cluttered environment. Our algorithm allows two-wheeled robots to find a path through passable obstacles.
  arXiv  Detail & Related papers  (2023-07-16T19:44:27Z)
• DDPEN: Trajectory Optimisation With Sub Goal Generation Model [70.36888514074022]
  In this paper, we produce a novel Differential Dynamic Programming with Escape Network (DDPEN) We propose to utilize a deep model that takes as an input map of the environment in the form of a costmap together with the desired position. The model produces possible future directions that will lead to the goal, avoiding local minima which is possible to run in real time conditions.
  arXiv  Detail & Related papers  (2023-01-18T11:02:06Z)
• Learning Agile Paths from Optimal Control [7.515638424396695]
  Motion planning algorithms are of central importance for deploying robots in the real world. These algorithms often drastically reduce the dimensionality of the problem for the sake of feasibility. This work proposes an approach to resolve these issues simultaneously by training a machine learning model on the outputs of an optimal control approach.
  arXiv  Detail & Related papers  (2022-11-30T23:58:48Z)
• 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)
• Minimum Displacement Motion Planning for Movable Obstacles [1.7513645771137178]
  We define a metric for robot-obstacle intersection that measures the extent of the intersection. The planner first finds a path through the obstacles that minimizes the robot-obstacle intersections. The metric is then used to iteratively displace the obstacles to achieve a feasible path.
  arXiv  Detail & Related papers  (2022-04-27T07:14:13Z)
• Vision-Based Mobile Robotics Obstacle Avoidance With Deep Reinforcement Learning [49.04274612323564]
  Obstacle avoidance is a fundamental and challenging problem for autonomous navigation of mobile robots. In this paper, we consider the problem of obstacle avoidance in simple 3D environments where the robot has to solely rely on a single monocular camera. We tackle the obstacle avoidance problem as a data-driven end-to-end deep learning approach.
  arXiv  Detail & Related papers  (2021-03-08T13:05:46Z)
• Bypassing or flying above the obstacles? A novel multi-objective UAV path planning problem [0.0]
  This study proposes a novel integer programming model for a collision-free discrete drone path planning problem. Considering the possibility of bypassing obstacles or flying above them, this study aims to minimize the path length, energy consumption, and maximum path risk simultaneously.
  arXiv  Detail & Related papers  (2020-04-12T13:42:05Z)

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.