The deployment of autonomous vehicles (AVs) in unstructured and dynamic environments such as construction, military, and commercial operations demands robust navigation strategies capable of adapting to continuously changing obstacles. Traditional graph-based path planning methods often fail in these settings, leading to inefficient and suboptimal trajectories. In this paper, we propose a dynamically updating navigation framework that integrates real-time obstacle clustering, a Dynamically constrained Delaunay Triangulation (D2T), and an enhanced Ant Colony Optimization (eACO) algorithm. Our approach first clusters proximate obstacles using LiDAR data to simplify the environment representation. A local D2T graph is then incrementally constructed around the robot, facilitating efficient map updates. The eACO algorithm leverages a greedy exploration strategy, enhanced by L´evy flight, to find near optimal paths within the D2T graph. Finally, a velocity obstacle-based local reactive navigator ensures safe real-time obstacle avoidance. Extensive simulations and comparison studies validate the framework’s superior performance in path length, computational speed, and overall adaptability compared to state-of-the-art path planning techniques.
- Open Access
- Article
Author Information
Received: 09 Oct 2025 | Revised: 10 Nov 2025 | Accepted: 21 Nov 2025 | Published: 08 Jan 2026
Abstract
Keywords
delaney triangulation | autonomous vehicle | graph-based path planning | navigation | obstacle clustering
References
- 1.
Jan, G.E.; Lei, T.; Sun, C.C.; et al. On the problems of drone formation and light shows. IEEE Trans. Consum. Electron. 2024, 70, 5259–5268.
- 2.
Lei, T.; Li, G.; Luo, C.; et al. An informative planning-based multi-layer robot navigation system as applied in a poultry barn. Intell. Robot. 2022, 2, 313–332.
- 3.
Sellers, T.; Lei, T.; Luo, C.; et al. Enhancing human-robot cohesion through hat methods: A crowd-avoidance model for safety aware navigation. In Proceedings of the 2024 IEEE 4th International Conference on Human-Machine Systems (ICHMS), Toronto, ON, Canada, 15–17 May 2024; pp. 1–6.
- 4.
Lei, T.; Chintam, P.; Luo, C.; et al. A convex optimization approach to multi-robot task allocation and path planning. Sensors 2023, 23, 5103.
- 5.
Hicks, M.; Lei, T.; Luo, C.; et al. A Bio-Inspired Goal-Directed Cognitive Map Approach to Robot Navigation and Mapping. In Proceedings of the 2025 IEEE Congress on Evolutionary Computation (CEC), Hangzhou, China, 8–12 June 2025; pp. 1–8.
- 6.
Riser, E.; Sellers, T.; Lei, T.; et al. Multirobot navigation using improved RRT*-SMART with digital twin technology. In Proceedings of the SPIE Conference: Autonomous Systems: Sensors, Processing, and Security for Ground, Air, Sea, and Space Vehicles and Infrastructure 2024, National Harbor, MD, USA, 21–26 April 2024; Volume 13052, pp. 114–125.
- 7.
Lei, T.; Luo, C.; Sellers, T.; et al. Multitask allocation framework with spatial dislocation collision avoidance for multiple aerial robots. IEEE Trans. Aerosp. Electron. Syst. 2022, 58, 5129–5140.
- 8.
Sellers, T.; Lei, T.; Carruth, D.; et al. Deep Learning-Based Heterogeneous System for Autonomous Navigation. In Proceedings of the SPIE, San Diego, CA, USA, 20–25 August 2023; Volume 12539, pp. 140–153.
- 9.
Black, B.; Sellers, T.; Lei, T.; et al. Optimal multi-target navigation via graph-based algorithms in complex environments. In Proceedings of the 2024 IEEE 33rd International Symposium on Industrial Electronics (ISIE), Ulsan, Republic of Korea, 18–21 June 2024; pp. 1–6.
- 10.
Sellers, T.; Lei, T.; Luo, C.; et al. A node selection algorithm to graph-based multi-waypoint optimization navigation and mapping. Intell. Robot. 2022, 2, 333–54.
- 11.
Rogers, J.H., III; Sellers, T.; Lei, T.; et al. Centroid-based cell decomposition robot path planning algorithm integrated with a bio-inspired approach. In Proceedings of the SPIE Conference: Unmanned Systems Technology XXVI. SPIE, National Harbor, MD, USA, 23–25 April 2024; Volume 13055, pp. 43–51.
- 12.
Sellers, T.; Lei, T.; Luo, C.; et al. Human autonomy teaming-based safety-aware navigation through bio-inspired and graph-based algorithms. Biomim. Intell. Robot. 2024, 4, 100189.
- 13.
Lei, T.; Chintam, P.; Carruth, D.W.; et al. Human-autonomy teaming-based robot informative path planning and mapping algorithms with tree search mechanism. In Proceedings of the 2022 IEEE 3rd International Conference on Human-Machine Systems (ICHMS), Orlando, FL, USA, 17–19 November 2022; pp. 1–6.
- 14.
Mandalika, A.; Salzman, O.; Srinivasa, S. Lazy Receding Horizon A* for Efficient Path Planning in Graphs with Expensive-to-Evaluate Edges. Proc. Int. Conf. Autom. Plan. Sched. 2018, 28, 476–484.
- 15.
Maurovic, I.; Seder, M.; Lenac, K.; et al. Path Planning for Active SLAM Based on the D* Algorithm With Negative Edge Weights. IEEE Trans. Syst. Man Cybern. Syst. 2017, 48, 1321–1331.
- 16.
Lei, T.; Luo, C.; Jan, G.E.; et al. Variable Speed Robot Navigation by an ACO Approach. In International Conference on Swarm Intelligence (ICSI); Springer: Cham, Switzerland, 2019; pp. 232–242.
- 17.
Scheffe, P.; Pedrosa, M.V.A.; Flaßkamp, K.; et al. Receding Horizon Control Using Graph Search for Multi-Agent Trajectory Planning. IEEE Trans. Control Syst. Technol. 2022, 31, 673–688.
- 18.
Lei, T.; Luo, C.; Ball, J.E.; et al. A Hybrid Fireworks Algorithm to Navigation and Mapping. In Handbook of Research on Fireworks Algorithms and Swarm Intelligence; IGI Global: Hershey, PA, USA, 2020; pp. 213–232.
- 19.
Graf, U.; Borges, P.; Hern´andez, E.; et al. Optimization-Based Terrain Analysis and Path Planning in Unstructured Environments. In Proceedings of the 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada, 20–24 May 2019; pp. 5614–5620.
- 20.
Niewola, A.; Podsedkowski, L. L* Algorithm—A Linear Computational Complexity Graph Searching Algorithm for Path Planning. J. Intell. Robot. Syst. 2018, 91, 425–444.
- 21.
Lei, T.; Chintam, P.; Luo, C.; et al. Multi-Robot directed coverage path planning in row-based environments. In Proceedings of the 2022 IEEE Fifth International Conference on Artificial Intelligence and Knowledge Engineering (AIKE), Laguna Hills, CA, USA, 19–21 September 2022; pp. 114–121.
- 22.
Bhattacharya, S.; Ghrist, R.; Kumar, V. Persistent Homology for Path Planning in Uncertain Environments. IEEE Trans. Robot. 2015, 31, 578–590.
- 23.
Lei, T.; Luo, C.; Sellers, T.; et al. A Bat-Pigeon Algorithm to Crack Detection-Enabled Autonomous Vehicle Navigation and Mapping. Intell. Syst. Appl. 2021, 12, 200053.
- 24.
Alarabi, S.; Lei, T.; Santora, M.; et al. Multi-robot path planning using potential field-based simulated annealing approach. In Proceedings of the SPIE Conference: Unmanned Systems Technology XXVI, National Harbor, MD, USA, 21–26 April 2024; Volume 13055, pp. 102–117.
- 25.
Chintam, P.; Lei, T.; Osmanoglu, B.; et al. Informed sampling space driven robot informative path planning. Robot. Auton. Syst. 2024, 175, 104656.
- 26.
Lei, T.; Sellers, T.; Luo, C.; et al. Digital twin-based multi-objective autonomous vehicle navigation approach as applied in infrastructure construction. IET Cyber-Syst. Robot. 2024, 6, e12110.
- 27.
Sellers, T.; Lei, T.; Jan, G.E.; et al. Multi-Objective Optimization Robot Navigation Through a Graph-Driven PSO Mechanism. In International Conference on Sensing and Imaging; Springer: Cham, Switzerland, 2022; pp. 66–77.
- 28.
Short, D.; Lei, T.; Carruth, D.W.; et al. A bio-inspired algorithm in image-based path planning and localization using visual features and maps. Intell. Robot. 2023, 3, 222–41.
- 29.
Hicks, M.; Lei, T.; Luo, C.; et al. A bio-inspired goal-directed cognitive map model for robot navigation and exploration. IEEE Trans. Cogn. Dev. Syst. 2025, 17, 1125–1140.
- 30.
Steen, S.; Lei, T.; Luo, C.; et al. A Moss Growth Optimization Approach to Robot Path Planning. In Proceedings of the S2025 IEEE Congress on Evolutionary Computation (CEC), Hangzhou, China, 8–12 June 2025; pp. 1–4.
- 31.
Lei, T.; Luo, C.; Yang, S.X.; et al. Bio-inspired Intelligence-based Multi-agent Navigation with Safety-aware Considerations. IEEE Trans. Artif. Intell. 2024, 5, 2946–2961.
- 32.
Rogers, J.H.; Sellers, T.; Lei, T.; et al. Sensor-based multi-waypoint autonomous robot navigation with graph-based models. In Proceedings of the SPIE Conference: Autonomous Systems: Sensors, Processing and Security for Ground, Air, Sea, and Space Vehicles and Infrastructure 2023, Orlando, FL, USA, 30 April–5 May 2023; Volume 12540, pp. 215–224.
- 33.
Sellers, T.; Lei, T.; Rogers, H.; et al. Autonomous Multi-Robot Allocation and Formation Control for Remote Sensing in Environmental Exploration. In Proceedings of the SPIE, Orlando, FL, USA, 30 April–5 May 2023; Volume 12540, pp. 225–241.
- 34.
Short, D.L.; Lei, T.; Liu, L.; et al. A Neural Network Approach to Image-Based Navigation and Localization. In Proceedings of the 2025 International Joint Conference on Neural Networks (IJCNN), Rome, Italy, 30 June–5 July 2025; pp. 1–7.
- 35.
Jayaraman, E.; Lei, T.; Rahimi, S.; et al. Immune System Algorithms to Environmental Exploration of Robot Navigation and Mapping. In Advances in Swarm Intelligence, Proceedings of the 12th International Conference, ICSI 2021, Qingdao, China, 17–21 July 2021; Springer: Cham, Switzerland, 2021; pp. 73–84.
- 36.
Lei, T.; Sellers, T.; Rahimi, S.; et al. A Nature-Inspired Algorithm to Adaptively Safe Navigation of a COVID-19 Disinfection Robot. In International Conference on Intelligent Robotics and Application(ICIRA); Springer International Publishing: Cham, Switzerland, 2021; pp. 123–134.
- 37.
Chen, X.; Li, S.; Kumar, V. Deep reinforcement learning for dynamic obstacle avoidance in unstructured environments. Int. J. Robot. Res. 2023, 42, 299–317.
- 38.
Zhang, Y.; Pavone, M.; Fisac, J.F. GNN-based predictive navigation in dynamic scenes using spatiotemporal graphs. In Proceedings of the Robotics: Science and Systems (RSS), Delft, The Netherlands, 15–19 July 2024.
- 39.
Liu, W.; Zhang, H.; Chen, Y.; et al. Graph-based reinforcement learning for autonomous navigation in dynamic environments. IEEE Robot. Autom. Lett. 2023, 8, 2125–2132.
- 40.
Wang, J.; Singh, A.; Dolan, J.M. Transformer-based path planning for autonomous vehicles in crowded environments. In Proceedings of the 2024 IEEE International Conference on Robotics and Automation (ICRA), Yokohama, Japan, 13–17 May 2024; pp. 1–7.
- 41.
Lei, T.; Sellers, T.; Luo, C.; et al. Graph-based robot optimal path planning with bio-inspired algorithms. Biomim. Intell. Robot. 2023, 3, 100119.
- 42.
Karaman, S.; Frazzoli, E. Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 2011, 30, 846–894.
- 43.
Manandhar, S.K. Efficient Algorithms for Clustering Polygonal Obstacles. Efficient Algorithms for Clustering Polygonal Obstacles. UNLV Theses, Dissertations, Professional Papers, and Capstones. 2016, 2704.http://dx.doi.org/10.34917/9112138
- 44.
Berg, M.; Cheong, O.; Kreveld, M.; et al. Computational Geometry: Algorithms and Applications, 3rd ed.; Springer: Berlin, Germany, 2008.
- 45.
Mantegna, R.N. Fast, accurate algorithm for numerical simulation of Levy stable stochastic processes. Phys. Rev. E 1994, 49, 4677.
- 46.
Lei, T.; Luo, C.; Jan, G.E.; et al. Deep Learning-Based Complete Coverage Path Planning With Re-Joint and Obstacle Fusion Paradigm. Front. Robot. AI 2022, 9, 843816.
- 47.
Dorigo, M.; St¨utzle, T. The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances. Handb. Metaheuristics 2006, 57, 227–263.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Suite 4002 Level 4, 447 Collins Street, Melbourne, Victoria 3000, Australia
General Inquiries: info@sciltp.com