Bidirectional Incremental Generalized Hybrid A*

• URL: http://arxiv.org/abs/2605.30647v1
• Date: Thu, 28 May 2026 23:04:37 GMT
• Title: Bidirectional Incremental Generalized Hybrid A*
• Abstract summary: We show that Bi-IGHA* substantially reduces expansions on R3, R4, and R6 planning problems.<n>We also show that Bi-IGHA* achieves equivalent closed-loop performance with kinodynamic planning for high-speed off-road autonomy.
• Score: 5.811502603310249
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We focus on the problem of efficient anytime kinodynamic planning for systems with complex dynamics in unstructured environments that make precomputing motion primitives infeasible. Directly applying A* to such problems is computationally infeasible due to the curse of dimensionality. Methods such as Hybrid A* addressed this burden by discretizing the state space, but in turn creating a coupling between tree discovery and the discretization resolution. The Incremental Generalized Hybrid A* (IGHA*) performs search over a hierarchy of resolutions in an anytime fashion to break this coupling, by freezing vertices to use in later search iterations rather than pruning them. However, the frozen vertices can hide solution-supporting vertices from the search at a particular iteration. While classical bidirectional search is motivated by the reduction of search depth, extending IGHA* into the bidirectional setting (termed Bi-IGHA*) obtains additional benefit by fundamentally mitigating the behaviour induced by frozen vertices hiding solutions. We show that Bi-IGHA* preserves IGHA*'s guarantees on monotonic cost improvement and termination. We empirically show that Bi-IGHA* substantially reduces expansions on R3, R4, and R6 planning problems, and achieves equivalent closed-loop performance with kinodynamic planning for high-speed off-road autonomy while requiring significantly fewer expansions. Website: https://personalrobotics.github.io/IGHAStar/biighastar.html

Related papers

• Fast and Efficient Approximate Nearest Neighbor Search for High-Dimensional LLM Embeddings [0.0]
  SISAP Indexing Challenge benchmarks Approximate Nearest Neighbor Search (ANNS) algorithms under rigorous constraints.<n>This paper presents our submissions for the 2026 edition, addressing both $k$-Nearest Neighbor Graph (kNNG) construction on 1024-dimensional BGE-M3 embeddings and Maximum Inner Product Search (MIPS) on unnormalized Llama-3.2-8B features.
  arXiv  Detail & Related papers  (2026-07-23T06:35:12Z)
• Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
  Model merging combines several independently fine-tuned experts into a single multi-task model without any training data.<n>State-of-the-art merging methods formulate merging as a layer-wise interference problem.<n>We propose SWUDI, a closed-form method that combines a soft exponential filter, which matches the gradient-flow trajectory of iterative descent.
  arXiv  Detail & Related papers  (2026-06-05T14:00:47Z)
• Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics [5.729787815551408]
  We propose BiXDFBnB, a bidirectional depth-first branch-and-bound algorithm that adapts the Single-Frontier Bidirectional Search framework.<n>Because SFBDS operates on paired states, front-to-front avoids the overhead typically associated with bidirectional frontier management.<n>BiXDFBnB is applied to several types of longest-path problems: Longest Simple Path (LSP), Snakes, and Coil-in-the-Box (CIB)
  arXiv  Detail & Related papers  (2026-06-04T09:53:18Z)
• Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition [51.22672287601796]
  Penalty-based methods have become popular for solving bilevel optimization (BLO) problems.<n>They often require inner-loop iteration to solve the lower-level (LL) problem and small outer-loop step sizes to handle the increased smoothness induced by large penalty terms.<n>This work considers the general BLO problems with coupled constraints (CCs) and leverages a novel penalty reformulation that decouples the upper- and lower-level variables.
  arXiv  Detail & Related papers  (2025-11-20T20:48:14Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree.<n>We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference.<n> Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• MeshA*: Efficient Path Planing With Motion Primitives [1.0550841723235613]
  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.
  arXiv  Detail & Related papers  (2024-12-13T18:00:21Z)
• Second-Order Forward-Mode Automatic Differentiation for Optimization [10.783826845783745]
  This paper introduces a second-order hyperplane search, a novel optimization step that generalizes a second-order line search from a line to a $k$-dimensional hyperplane. This, combined with the forward-mode gradient method, yields a second-order optimization algorithm that consists of forward passes only.
  arXiv  Detail & Related papers  (2024-08-19T21:12:41Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Online Dynamic Submodular Optimization [0.0]
  We propose new algorithms with provable performance for online binary optimization. We numerically test our algorithms in two power system applications: fast-timescale demand response and real-time distribution network reconfiguration.
  arXiv  Detail & Related papers  (2023-06-19T10:37:15Z)
• Highly Parallel Autoregressive Entity Linking with Discriminative Correction [51.947280241185]
  We propose a very efficient approach that parallelizes autoregressive linking across all potential mentions. Our model is >70 times faster and more accurate than the previous generative method.
  arXiv  Detail & Related papers  (2021-09-08T17:28:26Z)
• Efficient Person Search: An Anchor-Free Approach [86.45858994806471]
  Person search aims to simultaneously localize and identify a query person from realistic, uncropped images. To achieve this goal, state-of-the-art models typically add a re-id branch upon two-stage detectors like Faster R-CNN. In this work, we present an anchor-free approach to efficiently tackling this challenging task, by introducing the following dedicated designs.
  arXiv  Detail & Related papers  (2021-09-01T07:01:33Z)
• Simple and Effective Prevention of Mode Collapse in Deep One-Class Classification [93.2334223970488]
  We propose two regularizers to prevent hypersphere collapse in deep SVDD. The first regularizer is based on injecting random noise via the standard cross-entropy loss. The second regularizer penalizes the minibatch variance when it becomes too small.
  arXiv  Detail & Related papers  (2020-01-24T03:44:47Z)

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.