Genetic Informed Trees (GIT*): Path Planning via Reinforced Genetic Programming Heuristics

Liding Zhang, Kuanqi Cai, Zhenshan Bing, Chaoqun Wang, Alois Knoll · 2025

Read Genetic Informed Trees (GIT*): Path Planning via Reinforced Genetic Programming Heuristics by Liding Zhang, Kuanqi Cai, Zhenshan Bing, Chaoqun Wang, Alois Knoll (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20871.txt.

Introduction

Liding Zhang and co-authors present a robot path planner in this 2025 study. Planning a path means finding a route from start to goal that is both possible and near best, guided by a score that points the search the right way. The team builds on a tree-based planner and feeds its guide score far more facts about the scene, such as push-away forces from obstacles and the changing value of each point.

A second system then breeds better guide scores by genetic programming, with rewards steering the breeding. Tests ran on problems from four to sixteen dimensions, plus a real robot arm task. Their planner beat rival single-shot planners on speed and path quality within a fixed time budget. The authors share a video of the trials.

Catalog record

CREATORLiding Zhang, Kuanqi Cai, Zhenshan Bing, Chaoqun Wang, Alois Knoll
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20871

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Genetic Informed Trees (GIT*): Path Planning via Reinforced Genetic Programming Heuristics Liding Zhang, Kuanqi Cai, Zhenshan Bing, Chaoqun Wang, Alois Knoll Abstract Optimal path planning involves finding a feasible state sequence between a start and a goal that optimizes an objective. This process relies on heuristic functions to guide the search direction. While a robust function can improve search efficiency and solution quality, current methods often overlook available environmental data and simplify the function structure due to the complexity of information relationships. This study introduces Genetic Informed Trees (GIT*), which improves upon Effort Informed Trees (EIT*) by integrating a wider array of environmental data, such as repulsive forces from obstacles and the dynamic importance of vertices, to refine heuristic functions for better guidance. Furthermore, we integrated reinforced genetic programming (RGP), which combines genetic programming with reward system feedback to mutate genotype-generative heuristic functions for GIT*. RGP leverages a multitude of data types, thereby improving computational efficiency and solution quality within a set timeframe. Comparative analyses demonstrate that GIT* surpasses existing single-query, sampling-based planners in problems ranging from ℝ 4 \mathbb{R}^{4} to ℝ 16 \mathbb{R}^{16} and was tested on a real-world mobile manipulation task. A video showcasing our experimental results is available at https://youtu.be/URjXbc_BiYg . I Introduction Path planning is a fundamental challenge in robotic automation, involving the determination of a sequence of valid states that guide a robot from a starting point to a desired goal while avoiding obstacles [ 1 ] . Many algorithms have been proposed to address this problem, such as the A* algorithm [ 2 ] , Artificial Potential Field (APF) algorithm [ 3 ] , and sampling-based algorithms [ 4 ] . The A* algorithm’s performance declines with higher dimensionality, while the APF algorithm often converges to local minima. Sampling-based algorithms have gained popularity due to their efficient exploration of the state space [ 5 ] . However, they often require significant time to find the optimal solution. In multi-dimensional environments, such as autonomous vehicles and robot manipulators, it is essential to compute an efficient path to conserve power [ 6 ] . Fig. 1: GIT* utilizes a population of G-heuristics (i.e., \psi_{1},\psi_{2} …) with chromosome behaviors. The example of G-heuristics is illustrated above, which are trained using a reward function over multiple generations through RGP. The best G-heuristic is employed for pathfinding guidance. GIT*’s performance is evaluated in beer barrel, shelf, and kitchen model scenarios. The motivation for this paper is to improve the convergence rate and find successful solutions faster with lower initial solution costs based on the genetic-based generation of heuristics. Sampling-based algorithms like Rapidly-exploring Random Trees (RRT) [ 7 ] , Probabilistic Roadmaps (PRM) [ 8 ] , and variant algorithms of RRTs [ 9 ] have been widely used for recent path planning work and have demonstrated effectiveness in practical applications. However, these algorithms’ performance fluctuates greatly in different environments. On the other hand, in optimization algorithm research, a combined method known as Reinforced Genetic Programming (RGP) [ 10 ] is proposed. We introduced genotype-generative heuristic (G-heuristic) functions based on RGP for optimal edge evaluation, incorporating a fitness reward function to facilitate autonomous learning and adjustment of exploration strategies based on environmental feedback. This approach integrates the Genetic Algorithm (GA) [ 11 ] to assess bio-inspired chromosome behavior (e.g., crossover, mutation, reproduction ) for integration with sampling-based planners. However, the G-heuristic cannot be directly applied to robot path planning because it does not consider environmental constraints (e.g., obstacle avoidance ) or robustness across various scenarios. Therefore, the G-heuristic must be trained across different benchmarking datasets using reward feedback for robustness. Inspired by RGP technology, this paper presents the Genetic Informed Trees (GIT*) algorithm, which generates a heuristic function using problem-specific information via RGP. This heuristic enhances efficiency by minimizing expanded vertices. GIT* uses invalid samples within obstacles and start/goal points to create an APF, incorporating obstacle shapes and locations, and tracks sample visit frequency to account for the dynamic importance of states. The G-heuristics represent a symbolic regression problem tackled by RGP. It involves evolving nonlinear expressions to refine the heuristic. As shown in Fig. 2 , G-heuristic enables GIT* to find the initial solution quickly and then expand. GIT* incorporates additional graph search techniques, such as truncation and inflation, to balance exploitation and exploration, dynamically modified using RGP. GIT* has shown improvements over state-of-the-art (SOTA) methods in time to find the initial solution, initial solution quality, and final solution quality in both generalized simulation benchmarks and real-world experiments. The contributions of this paper are summarized as follows: 1. An efficient optimal genotype-generative heuristic function based on reinforced genetic programming, trained with a dataset from the random problem domain. 2. A novel sampling-based path planning algorithm, GIT*, integrates the trained genotype-generative heuristic function to rapidly obtain high-quality solutions. 3. Demonstrating the effectiveness of GIT* across various dimensional environments and optimization objectives. II Related work start start start start goal goal goal goal {X}_{\text{obs}} {X}_{\text{obs}} {X}_{\text{obs}} {X}_{\text{obs}} (a) EIT* (t_{n}) (b) EIT* (t_{n+1}) (c) GIT* (t_{n}) (d) GIT* (t_{n+1}) Fig. 2: Four snapshots show EIT* and GIT* exploration strategies in reverse search. GIT* employs G-heuristics, while EIT* maintains a linear combination heuristic. Yellow points indicate valid samples in obstacle-free areas. The blue line represents the reverse tree at time t_{n} , the pink line represents it at time t_{n+1} , and the dashed red lines are optimized reverse edges. Heuristic functions optimize path planning by estimating goal-state costs, which is crucial across multiple dimensions. Informed planners with heuristics outperform their uninformed counterparts [ 12 ] . Effective heuristics should be accurate and efficient, yet balancing these traits can be challenging [ 13 ] . RRT-Connect [ 14 ] extends the RRT framework by growing two trees: one from the start state and the other from the goal, using heuristic-guided planning to accelerate path convergence. However, RRT-Connect lacks asymptotic optimality and does not improve solution quality with more computation time [ 15 ] . Cost heuristics in tree growth are demonstrated by Heuristically-guided RRT (hRRT) [ 16 ] and Generalized Bidirectional RRT (GBRRT) [ 17 ] . hRRT uses a priori heuristics for exploration within RRT’s Voronoi regions, while GBRRT, a bidirectional RRT variant, employs reverse tree-computed heuristics to guide the forward tree. However, these algorithms do not provide bounds on solution quality [ 18 ] . To overcome this limitation, some planners combine graph-based and sampling-based approaches. Batch Informed Trees (BIT*) [ 19 ] uses A* on a random geometric graph (RGG) formed by random samples, improving approximation as samples increase. While BIT* efficiently refines its search, it still has limitations in using problem-specific information. Advanced BIT* (ABIT*) [ 20 ] enhances BIT* by introducing inflated and truncated factors, balancing the exploration and exploitation. Adaptively Informed Trees (AIT*) [ 13 ] and Effort Informed Trees (EIT*) [ 13 ] further enhance efficiency with bidirectional search strategies. EIT* uses adaptive sparse collision checks, reducing expensive collision detections. The forward and reverse trees inform each other, sharing complementary information to optimize the search [ 9 ] . However, EIT* did not leverage the information from the invalid sample/nearest neighbor in the planning domain. GIT* integrates APF and dynamic importance for further guidance. II-A

Read the complete text