Optimal Multi-target Navigation via Graph-based Algorithms in Complex Environments

Abstract

In the advancing field of autonomous robotics, efficient navigation through dynamically changing and complex environments presents a significant challenge. This research introduces a refined methodology that employs Generalized Voronoi Diagrams (GVD) to define clear, navigable paths in environments dense with obstacles, particularly in indoor settings where navigation becomes exceedingly intricate. The essence of this innovation is a graph structure that outlines near-optimal pathways, enhancing traditional pathfinding methods with a refined strategy that surpasses basic straight-line distance calculations. This system integrates a tailored dynamic programming technique for effective target sequencing, harmoniously combined with the Dynamic Window Approach (DWA) to swiftly adjust to new obstacles or environmental changes. The proposed solution not only increases the precision of navigation in complicated areas but is also highly adaptable to varying conditions, showcasing scalability and flexibility. Through comprehensive simulation and comparison studies, our approach is validated, showcasing its remarkable computational efficiency and obstacle avoidance, thereby marking a significant advancement in the field of autonomous robotic navigation.