Incremental Generalized Hybrid A*

2025-08-18 · Sidharth Talia, Oren Salzman, Siddhartha Srinivasa arxiv

We address the problem of efficiently organizing search over very large trees, which arises in many applications ranging from autonomous driving to aerial vehicles. Here, we are motivated by off-road autonomy, where real-time planning is essential. Classical approaches use graphs of motion primitives and exploit dominance to mitigate the curse of dimensionality and prune expansions efficiently. However, for complex dynamics, repeatedly solving two-point boundary-value problems makes graph construction too slow for fast kinodynamic planning. Hybrid A* (HA*) addressed this challenge by searching over a tree of motion primitives and introducing approximate pruning using a grid-based dominance check. However, choosing the grid resolution is difficult: too coarse risks failure, while too fine leads to excessive expansions and slow planning. We propose Incremental Generalized Hybrid A* (IGHA*), an anytime tree-search framework that dynamically organizes vertex expansions without rigid pruning. IGHA* provably matches or outperforms HA*. For both on-road kinematic and off-road kinodynamic planning queries for a car-like robot, variants of IGHA* use 6x fewer expansions to the best solution compared to an optimized version of HA* (HA*M, an internal baseline). In simulated off-road experiments in a high-fidelity simulator, IGHA* outperforms HA*M when both are used in the loop with a model predictive controller. We demonstrate real-time performance both in simulation and on a small-scale off-road vehicle, enabling fast, robust planning under complex dynamics. Website: https://personalrobotics.github.io/IGHAStar/

📄 PDF Abstract BibTeX arXiv:2508.13392

Code (0)

등록된 구현이 없습니다.

Tasks

Autonomous Driving

Bidirectional Incremental Generalized Hybrid A*

2026-05-28 · Sidharth Talia, Oren Salzman, Siddhartha Srinivasa arxiv

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 …

Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs

2014-02-04 · Frans Adriaan Oliehoek, Matthijs T. J. Spaan, Christopher Amato, Shimon Whiteson

This article presents the state-of-the-art in optimal solution methods for decentralized partially observable Markov decision processes (Dec-POMDPs), which are general models for collaborative multiagent planning under u…

Clustering

Generalized and Incremental Few-Shot Learning by Explicit Learning and Calibration without Forgetting

2021-08-18 · ICCV 2021 10 · Anna Kukleva, Hilde Kuehne, Bernt Schiele

Both generalized and incremental few-shot learning have to deal with three major challenges: learning novel classes from only few samples per class, preventing catastrophic forgetting of base classes, and classifier cali…

Classifier calibration Few-Shot Learning

Incremental Generalized Category Discovery

2023-04-27 · ICCV 2023 1 · Bingchen Zhao, Oisin Mac Aodha

We explore the problem of Incremental Generalized Category Discovery (IGCD). This is a challenging category incremental learning setting where the goal is to develop models that can correctly categorize images from previ…

Fine-Grained Visual Categorization Incremental Learning

SATHUR: Self Augmenting Task Hallucinal Unified Representation for Generalized Class Incremental Learning

2023-08-13 · Sathursan Kanagarajah, Thanuja Ambegoda, Ranga Rodrigo

Class Incremental Learning (CIL) is inspired by the human ability to learn new classes without forgetting previous ones. CIL becomes more challenging in real-world scenarios when the samples in each incremental step are …

class-incremental learning Class Incremental Learning Incremental Learning