MeshA*: Efficient Path Planing With Motion Primitives

• URL: http://arxiv.org/abs/2412.10320v1
• Date: Fri, 13 Dec 2024 18:00:21 GMT
• Title: MeshA*: Efficient Path Planing With Motion Primitives
• Abstract summary: We study a path planning problem where the possible move actions are represented as a finite set of motion primitives aligned with the grid representation of the environment.<n>We suggest a novel technique rooted in the idea of searching over the grid cells (as in vanilla A*) simultaneously fitting the possible sequences of the motion primitives into these cells.<n>The resultant algorithm, MeshA*, provably preserves the guarantees on completeness and optimality, on the one hand, and is shown to notably outperform conventional lattice-based planning.
• Score: 1.0550841723235613
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a path planning problem where the possible move actions are represented as a finite set of motion primitives aligned with the grid representation of the environment. That is, each primitive corresponds to a short kinodynamically-feasible motion of an agent and is represented as a sequence of the swept cells of a grid. Typically heuristic search, i.e. A*, is conducted over the lattice induced by these primitives (lattice-based planning) to find a path. However due to the large branching factor such search may be inefficient in practice. To this end we suggest a novel technique rooted in the idea of searching over the grid cells (as in vanilla A*) simultaneously fitting the possible sequences of the motion primitives into these cells. The resultant algorithm, MeshA*, provably preserves the guarantees on completeness and optimality, on the one hand, and is shown to notably outperform conventional lattice-based planning (x1.5 decrease in the runtime), on the other hand. Moreover, we suggest an additional pruning technique that additionally decreases the search space of MeshA*. The resultant planner is combined with the regular A* to retain completeness and is shown to further increase the search performance at the cost of negligible decrease of the solution quality.

Related papers

• Smooth Feedback Motion Planning with Reduced Curvature [2.227314660022684]
  Existing algorithms produce paths with unnecessary bending, leading to slower motion and higher control effort.<n>A novel geometric algorithm constructs a maximal star-shaped chain of simplexes around the goal.<n> Simulations demonstrate that our method generates measurably more direct paths, reducing total bending by an average of 91.40% and LQR control effort by an average of 45.47%.
  arXiv  Detail & Related papers  (2026-04-02T04:48:55Z)
• Gradient-Based Join Ordering [0.532836690371986]
  Join ordering is the problem of selecting the most efficient sequence in which to evaluate joins in a database query.<n>Traditional approaches cast this problem as a discrete runtime search over binary trees guided by a cost model.<n>We show that, when the cost model is differentiable, the query plans can be continuously relaxed into a soft adjacency matrix.<n>Using a learned Graph Neural Network as the cost model, we demonstrate that this gradient-based approach can find comparable and even lower-cost plans.
  arXiv  Detail & Related papers  (2025-11-18T13:24:28Z)
• Search-Based Robot Motion Planning With Distance-Based Adaptive Motion Primitives [1.8874301050354767]
  This work proposes a motion planning algorithm for robotic manipulators that combines sampling-based and search-based planning methods.<n>The core contribution of the proposed approach is the usage of burs of free configuration space (C-space) as adaptive motion primitives.<n>Results demonstrate that the bur-based approach outperforms fixed-primitive planning in complex scenarios.
  arXiv  Detail & Related papers  (2025-07-01T21:33:33Z)
• A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives [21.108406629056173]
  We consider the bi-objective shortest-path (BOSP) problem in the presence of correlated objectives.<n>BOSP is generally computationally challenging as the size of the search space is exponential in the number of objective functions and the graph size.<n>We propose an efficient algorithm that reduces the search effort in the presence of correlated objectives.
  arXiv  Detail & Related papers  (2025-05-28T11:26:14Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Flow Priors for Linear Inverse Problems via Iterative Corrupted Trajectory Matching [35.77769905072651]
  We propose an iterative algorithm to approximate the MAP estimator efficiently to solve a variety of linear inverse problems. Our algorithm is mathematically justified by the observation that the MAP objective can be approximated by a sum of $N$ local MAP'' objectives. We validate our approach for various linear inverse problems, such as super-resolution, deblurring, inpainting, and compressed sensing.
  arXiv  Detail & Related papers  (2024-05-29T06:56:12Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Stochastic Direct Search Method for Blind Resource Allocation [6.574808513848414]
  We study direct search (also known as pattern search) methods for linearly constrained and derivative-free optimization. We show that direct search methods achieves finite regret in the deterministic and unconstrained case. We propose a simple extension of direct search that achieves a regret upper-bound of the order of $T2/3$.
  arXiv  Detail & Related papers  (2022-10-11T07:40:45Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
  Inspired by sum-of-infeasibilities methods in convex optimization, we propose a novel procedure for analyzing verification queries on networks with extensive branching functions. An extension to a canonical case-analysis-based complete search procedure can be achieved by replacing the convex procedure executed at each search state with DeepSoI.
  arXiv  Detail & Related papers  (2022-03-19T15:05:09Z)
• CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial Optimization Problems [0.0]
  This paper proposes a search algorithm by expanding search space from a Markov chain to a depth limited tree based on SA. At each iteration, the algorithm will select the best near-optimal solution within the feasible search space by exploring along the tree in the sense of look ahead' Our results show that above the primals SA and CIM, our high-level tree search strategy is able to provide solutions within fewer epochs for Ising formulated NP-optimization problems.
  arXiv  Detail & Related papers  (2022-03-09T10:07:26Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• 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)
• Asymptotic study of stochastic adaptive algorithm in non-convex landscape [2.1320960069210484]
  This paper studies some assumption properties of adaptive algorithms widely used in optimization and machine learning. Among them Adagrad and Rmsprop, which are involved in most of the blackbox deep learning algorithms.
  arXiv  Detail & Related papers  (2020-12-10T12:54:45Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  Activation Relaxation (AR) algorithm provides a simple and robust approach for approximating the backpropagation of error algorithm. We show that the algorithm can be further simplified and made more biologically plausible by introducing a learnable set of backwards weights. We also investigate whether another biologically implausible assumption of the original AR algorithm -- the frozen feedforward pass -- can be relaxed without damaging performance.
  arXiv  Detail & Related papers  (2020-10-13T08:02:38Z)

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.