A cell-decomposition based path planner for 3D navigation in constrained workspaces

• URL: http://arxiv.org/abs/2605.10086v1
• Date: Mon, 11 May 2026 07:06:53 GMT
• Title: A cell-decomposition based path planner for 3D navigation in constrained workspaces
• Abstract summary: This paper proposes a cell decomposition algorithm for binary occupancy grids.<n>It ensures mutual complete visibility from each cell to at least one adjacent cell.<n>We formulate both second-order cone programs (SOCP) and their mixed-integer variant (MISOCP) within the proposed framework.
• Score: 2.9223917785251294
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper proposes a cell decomposition algorithm for binary occupancy grids that ensures mutual complete visibility from each cell to at least one adjacent cell. This decomposition establishes a simplified framework for verifying path feasibility that can be easily embedded in optimization problems. To illustrate its utility, we formulate both second-order cone programs (SOCP) and their mixed-integer variant (MISOCP) within the proposed framework. Furthermore, we propose the KSP-SOCP method, which combines Yen's k-shortest path algorithm with the SOCP, achieving improved solutions compared to a standard SOCP approach while avoiding the computational burden of MISOCP. The cell decomposition algorithm, KSP-SOCP, and MISOCP approaches were evaluated in 9 city-like workspaces. The decomposition efficiently partitioned each map, enabling both optimization methods to compute feasible paths. The proposed KSP-SOCP achieved time performance comparable to the MISOCP while requiring less memory, making it highly suitable for large-scale problems.

Related papers

• Conflict-Driven Clause Learning with VSIDS Heuristics for Discrete Facility Layout [0.0]
  This paper studies the use of Conflict-Driven Clause Learning (CDCL) withDSs as a computational engine for discrete facility layout problems.<n>We develop a CNF-based formulation for layout feasibility and compare CDCL-based SAT solving against CPSAT and MILP formulations.
  arXiv  Detail & Related papers  (2025-12-19T20:03:37Z)
• A Gradient Meta-Learning Joint Optimization for Beamforming and Antenna Position in Pinching-Antenna Systems [63.213207442368294]
  We consider a novel optimization design for multi-waveguide pinching-antenna systems.<n>The proposed GML-JO algorithm is robust to different choices and better performance compared with the existing optimization methods.
  arXiv  Detail & Related papers  (2025-06-14T17:35:27Z)
• CSF: Fixed-outline Floorplanning Based on the Conjugate Subgradient Algorithm Assisted by Q-Learning [9.16178663078742]
  We propose a nonsmooth analytic floorplanning model addressed by the conjugate subgradient algorithm (CSA)<n> Experimental results on the MCNC and GSRC benchmarks demonstrate that the proposed fixed-outline floorplanning algorithm based on CSAQ (CSF)<n>It is also demonstrated that the CSF is competitive to the state-of-the-art algorithms on floorplanning scenarios only containing hard modules.
  arXiv  Detail & Related papers  (2025-04-04T04:01:26Z)
• Research on reinforcement learning based warehouse robot navigation algorithm in complex warehouse layout [13.945240113332352]
  This paper proposes a new method of Proximal Policy Optimization (PPO) and Dijkstra's algorithm, Proximal policy-Dijkstra (PP-D) PP-D method realizes efficient strategy learning and real-time decision making through PPO, and uses Dijkstra algorithm to plan the global optimal path.
  arXiv  Detail & Related papers  (2024-11-09T09:44:03Z)
• A new simplified MOPSO based on Swarm Elitism and Swarm Memory: MO-ETPSO [0.0]
  Elitist PSO (MO-ETPSO) is adapted for multi-objective optimization problems. The proposed algorithm integrates core strategies from the well-established NSGA-II approach. A novel aspect of the algorithm is the introduction of a swarm memory and swarm elitism.
  arXiv  Detail & Related papers  (2024-02-20T09:36:18Z)
• Floorplanning of VLSI by Mixed-Variable Optimization [42.82770651937298]
  This paper proposes memetic algorithms to solve mixed-variable floorplanning problems. Proposed algorithms are superior to some celebrated B*-tree based floorplanning algorithms.
  arXiv  Detail & Related papers  (2024-01-27T06:34:16Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.