Genetic Informed Trees (GIT*): Path planning via reinforced genetic programming heuristics

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 R⁴ to R¹⁶ to and was tested on a real-world mobile manipulation task. A video showcasing our experimental results is available at https://youtu.be/URjXbc_BiYg.

Keywords

Genetic algorithm / Reinforced genetic programming / Generative heuristics / Optimal path planning

CRediT authorship contribution statement

Liding Zhang: Conceptualization. Kuanqi Cai: Conceptualization. Zhenshan Bing: Writing - review & editing. Chaoqun Wang: Supervision. Alois Knoll: Visualization.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Appendix A. Supplementary data

Supplementary material related to this article can be found online at https://doi.org/10.1016/j.birob.2025.100237.

References

[1] J.D. Gammell, M.P. Strub, Asymptotically optimal sampling-based motion planning methods, Annu. Rev. Control. Robot. Auton. Syst. 4 (2021) 295-318.

[2] K. Cai, W. Chen, C. Wang, H. Zhang, M.Q.-H. Meng, Curiosity-based robot navigation under uncertainty in crowded environments, IEEE Robot. Autom. Lett. 8 (2) (2023) 800-807.

[3] K. Cai, R. Laha, Y. Gong, L. Chen, L. Zhang, L.F. Figueredo, S. Haddadin, Demonstration to adaptation: A user-guided framework for sequential and real-time planning,in:2024 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, 2024, pp. 9871-9878.

[4] P.E. Hart, N.J. Nilsson, B. Raphael, A formal basis for the heuristic determi-nation of minimum cost paths, IEEE Trans. Syst. Sci. Cybern. 4 (2) (1968) 100-107.

[5] O. Khatib, Real-time obstacle avoidance for manipulators and mobile robots, Int. J. Robot. Res. 5 (1) (1986) 90-98.

[6] S. Karaman, E. Frazzoli, Sampling-based algorithms for optimal motion planning, Int. J. Robot. Res. 30 (7) (2011) 846-894.

[7] K. Cai, W. Chen, D. Dugas, R. Siegwart, J.J. Chung, Sampling-based path planning in highly dynamic and crowded pedestrian flow, IEEE Trans. Intell. Transp. Syst. 24 (12) (2023) 14732-14742.

[8] L. Zhang, K. Cai, Z. Sun, Z. Bing, C. Wang, L. Figueredo, S. Haddadin, A. Knoll, Motion planning for robotics: A review for sampling-based planners, Biomim. Intell. Robot. 5 (1) (2025) 100207.

[9] K. Cai, C. Wang, J. Cheng, C.W. De Silva, M.Q.-H. Meng, Mobile robot path planning in dynamic environments: A survey, Instrumentation (2020).

[10] S.M. LaValle, J.J. Kuffner Jr., Randomized kinodynamic planning, Int. J. Robot. Res. 20 (5) (2001) 378-400.

[11] L.E. Kavraki, P. Svestka, J.-C. Latombe, M.H. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. Robot. Autom. 12 (4) (1996) 566-580.

[12] K. Cai, C. Wang, S. Song, H. Chen, M.Q.-H. Meng, Risk-aware path planning under uncertainty in dynamic environments, J. Intell. Robot. Syst. 101 (2021) 1-15.

[13] K. Cai, W. Chen, C. Wang, S. Song, M.Q.-H. Meng, Human-aware path planning with improved virtual Doppler method in highly dynamic environments, IEEE Trans. Autom. Sci. Eng. 20 (2) (2023) 1304-1321.

[14] K.L. Downing, Reinforced genetic programming, Genet. Program. Evolvable Mach. 2 (2001) 259-288.

[15] K. Sastry, D. Goldberg, G. Kendall,Genetic algorithms, Search Methodologies, Springer, Boston, MA, 2005.

[16] J.D. Gammell, T.D. Barfoot, S.S. Srinivasa, Informed sampling for asymp-totically optimal path planning, IEEE Trans. Robot. 34 (4) (2018) 966-984.

[17] L. Zhang, Y. Ling, Z. Bing, F. Wu, S. Haddadin, A. Knoll, Tree-based grafting approach for bidirectional motion planning with local subsets optimization, IEEE Robot. Autom. Lett. 10 (6) (2025) 5815-5822.

[18] M.P. Strub, J.D. Gammell, Adaptively informed trees (AIT^*) and effort informed trees (EIT^*): Asymmetric bidirectional sampling-based path planning, Int. J. Robot. Res. 41 (4) (2022) 390-417.

[19] E. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1) (1959) 269-271.

[20] M. Likhachev, G. Gordon, S. Thrun, ARA^*: Anytime A^* with provable bounds on sub-optimality,in: Advances in Neural Information Processing Systems, vol. 16, MIT Press, 2003.

[21] R. Bellman, Dynamic Programming, Princeton Univ, Press Princeton, New Jersey, 1957.

[22] J.J. Kuffner, S.M. LaValle,RRT-connect: An efficient approach to single-query path planning,in:Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), Vol. 2, IEEE, 2000, pp. 995-1001.

[23] J. Wang, B. Li, M.Q.-H. Meng, Kinematic constrained bi-directional RRT with efficient branch pruning for robot path planning, Expert Syst. Appl. 170 (2021) 114541.

[24] C. Urmson, R. Simmons,Approaches for heuristically biasing RRT growth, in:Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No.03CH37453), Vol.2, IEEE, 2003, pp. 1178-1183.

[25] S. Nayak, M.W. Otte, Bidirectional sampling-based motion planning with-out two-point boundary value solution, IEEE Trans. Robot. 38 (6) (2022) 3636-3654.

[26] I.-B. Jeong, S.-J. Lee, J.-H. Kim, Quick-RRT^*: Triangular inequality-based implementation of RRT^* with improved initial solution and convergence rate, Expert Syst. Appl. 123 (2019) 82-90.

[27] J.D. Gammell, S.S. Srinivasa, T.D. Barfoot, Informed RRT^*: Optimal sampling-based path planning focused via direct sampling of an admissible ellip-soidal heuristic, in: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, 2014, pp. 2997-3004.

[28] J. Wang, T. Zhang, N. Ma, Z. Li, H. Ma, F. Meng, M.Q. Meng, A survey of learning-based robot motion planning, IET Cyber- Syst. Robot. 3 (2021) 302-314.

[29] A.H. Qureshi, Y. Miao, A. Simeonov, M.C. Yip, Motion planning networks: Bridging the gap between learning-based and classical motion planners, IEEE Trans. Robot. 37 (1) (2021) 48-66.

[30] J. Wang, W. Chi, C. Li, C. Wang, M.Q.-H. Meng, Neural RRT^*: Learning-based optimal path planning, IEEE Trans, Autom. Sci. Eng. 17 (4) (2020) 1748-1758.

[31] Z. Huang, H. Chen, J. Pohovey, K. Driggs-Campbell, Neural informed RRT^*: Learning-based path planning with point cloud state representations under admissible ellipsoidal constraints, in: 2024 IEEE International Conference on Robotics and Automation, ICRA, 2024, pp. 8742-8748.

[32] M. Zucker, N. Ratliff, A.D. Dragan, M. Howard, M. Vecerik, T.F.Y. Wang, J.-P. van der Smagt, J.A. Bagnell, CHOMP: Covariant Hamiltonian optimization for motion planning, Int. J. Robot. Res. 32 (9-10) (2013) 1164-1193.

[33] M. Kalakrishnan, S. Chitta, E. Theodorou, P. Pastor, S. Schaal, STOMP: Stochastic trajectory optimization for motion planning, in: 2011 IEEE International Conference on Robotics and Automation, ICRA, Shanghai, China, 2011, pp. 4569-4574.

[34] J. Schulman, Y. Duan, J. Ho, A. Lee, I. Awwal, H. Bradlow, P. Abbeel, Motion planning with sequential convex optimization and convex collision checking, Int. J. Robot. Res. 33 (9) (2014) 1251-1270.

[35] T. Marcucci, M. Petersen, D. von Wrangel, R. Tedrake, Motion planning around obstacles with convex optimization, Sci. Robot. 8 (84) (2023).

[36] J.D. Gammell, S.S. Srinivasa, T.D. Barfoot, Batch informed trees (BIT^*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs, in: 2015 IEEE International Conference on Robotics and Automation, ICRA, IEEE, 2015, pp. 3067-3074.

[37] J.D. Gammell, T.D. Barfoot, S.S. Srinivasa, Batch informed trees (BIT^*): Informed asymptotically optimal anytime search, Int. J. Robot. Res. 39 (5)(2020) 543-567.

[38] M.P. špace0mmStrub, J.D. Gammell, Advanced BIT^*(ABIT^*): Sampling-based planning with advanced graph-search techniques, in: 2020 IEEE Inter-national Conference on Robotics and Automation, ICRA, IEEE, 2020, pp. 130-136.

[39] L. Zhang, Z. Bing, K. Chen, L. Chen, K. Cai, Y. Zhang, F. Wu, P. Krumbholz, Z. Yuan, S. Haddadin, A. Knoll, Flexible informed trees (FIT^*): Adaptive batch-size approach in informed sampling-based path planning,in:2024 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, 2024, pp. 3146-3152.

[40] M.P. Strub, J.D. Gammell, Adaptively informed trees (AIT): Fast asymptot-ically optimal path planning through adaptive heuristics, in: 2020 IEEE International Conference on Robotics and Automation, ICRA, IEEE, 2020, pp. 3191-3198.

[41] L. Zhang, Z. Bing, Y. Zhang, K. Cai, L. Chen, F. Wu, S. Haddadin, A. Knoll, Elliptical K-nearest neighbors: Path optimization via Coulomb’s law and invalid vertices in C-space obstacles,in:2024 IEEE/RSJ Inter-national Conference on Intelligent Robots and Systems, IROS, 2024, pp. 12032-12039.

[42] C.-H. Wei, J.-S. Liu, Hybridizing RRT and variable-length genetic algorithm for smooth path generation, in: 2011 IEEE International Conference on Robotics and Biomimetics, 2011, pp. 626-632.

[43] X. Wang, Genetic RRT: Asymptotically optimal sampling-based path plan-ning via optimization of genetic algorithm, Highlights Sci. Eng. Technol. 43 (2023) 215-222.

[44] G. Rudolph, Convergence analysis of canonical genetic algorithms, IEEE Trans. Neural Netw. 5 (1) (1994) 96-101.

[45] G. Rudolph, Convergence Properties of Evolutionary Algorithms, Verlag Dr. Kovač, 1997.

[46] I.A. Sucan, M. Moll, L.E. Kavraki, The open motion planning library, IEEE Robot. Autom. Mag. 19 (4) (2012) 72-82.

[47] M. Moll, I.A. Sucan, L.E. Kavraki, Benchmarking motion planning algo-rithms: An extensible infrastructure for analysis and visualization, IEEE Robot. Autom. Mag. 22 (3) (2015) 96-102.

[48] J.D. Gammell, M.P. Strub, V.N. Hartmann, Planner developer tools (PDT): Reproducible experiments and statistical analysis for developing and testing motion planners,in:Proceedings of the Workshop on Evaluating Motion Planning Performance (EMPP), IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, 2022.

[49] M. Virgolin, S.P. Pissis, Symbolic regression is NP-hard, Trans. Mach. Learn. Res. (2022).

[50] M. Penrose, Random geometric graphs, vol.5, OUP Oxford 2003.