A Dynamically Updating Graph-Based Navigation Scheme for Autonomous Vehicles

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.