Hard-Exclusion Bidirectional A*: Constraint-Safe, Real-Time Pathfinding for Dynamic Urban Networks

Abstract

Urban navigation systems in dynamic environments face a fundamental challenge: delivering real-time, verifiably safe, and efficient pathfinding solutions that adapt to unpredictable obstacles while maintaining computational feasibility. Existing approaches either rely on static precomputation unsuitable for dynamic updates (Contraction Hierarchies) or employ soft-penalty methods incapable of guaranteeing strict obstacle avoidance. This paper introduces an enhanced Bidirectional A* algorithm incorporating a hard exclusion mechanism that ensures provable safety by completely pruning paths violating user-defined safety margins around dynamic obstacles. Integrated with k-d tree spatial indexing for efficient proximity queries, the algorithm achieves average execution times ranging from  0.80 ms to 4,189 ms depending on obstacle density and avoidance radius, with the majority of constrained configurations completing under 2 seconds, while low-density configurations may require up to 4 seconds due to extensive search space exploration for real-time deployment. The system is implemented in Python 3.9, leveraging OSMnx for graph construction and scipy.spatial.cKDTree for spatial indexing. Empirical evaluation on the complex urban networks of Kathmandu and Lalitpur across 1,600 experimental configurations systematically varies obstacle density and avoidance radius to quantify critical trade-offs among safety, path efficiency, and reliability. Results demonstrate that the algorithm maintains high reliability (≤20% failure rate) under moderate constraints, exhibits "fail-fast" behavior in overly constrained scenarios, and exhibits Path Length Inflation of 2.685× at most for safety-critical applications. The Path Vulnerability Index further reveals that network topology fundamentally influences feasible routing under dynamic disruption. These findings provide a validated framework for safety-critical navigation systems, enabling configurability across operational requirements while maintaining verifiable guarantees that distinguish this approach from existing penalty-based methods and establishing a foundation for next-generation intelligent transportation systems.