Testing Autonomous Driving Systems (ADS) is critical for validating their safety in operational environments. High-fidelity simulators enable the testing of ADS through virtual driving scenarios, especially those that are hazardous to replicate in real-world settings. However, existing testing approaches suffer from inadequate coverage of real-world traffic situations due to over-simplified modeling of vehicle movements (e.g., insufficient diversity in driving styles), resulting in undetected critical ADS failures. In this article, we propose a testing framework to discover diverse failures of ADS in driving scenarios that embody real-world traffic complexity. The framework leverages advanced traffic simulation methods to encode vehicle movements and generates realistic yet safety-critical driving scenarios for ADS by mutating vehicle movements. To efficiently explore driving scenarios that pose different challenges for ADS and expose diverse ADS failures, this framework further leverages a dynamic prioritization mechanism that prioritizes vehicle movements likely to trigger unique ADS behaviors. Specifically, we propose a method to estimate the possibility based on encoded vehicle movements. We implement this framework and evaluate it with three representative ADS from the famous CARLA Leaderboard. Empirical evaluation demonstrates that the proposed approach discovers more unique failures of ADS than existing testing frameworks.

Shortest path query on road networks is a fundamental problem to support many location-based services and wide variant applications. Contraction Hierarchies(CH) is widely adopted to accelerate the shortest path query by leveraging shortcuts among vertices. However, the state-of-the-art CH construction method named$\mathsf{VCHCons}$suffers from inefficiencies due to their strong reliance on pre-determined vertex order. This leads to the generation of a large number of invalid shortcuts and the limit of parallel processing capability. Motivated by it, in this paper, an innovative CH construction algorithm called$\mathsf{ECHCons}$is devised following an edge-centric paradigm, which addresses the issue of invalid shortcut production by introducing a novel edge-ordering strategy. Furthermore, it optimizes shortcut calculation within a dynamically constructed optimal subgraph, which is significantly smaller than the original network, thus shrinking the traversal space during index construction. To further enhance efficiency and overcome the limitations in parallelism inherent to$\mathsf{VCHCons}$, our approach leverages batch contraction of edges and introduces a well-defined lower bound technique to unlock more efficient parallel computation resources. Our approach provides both theoretical guarantee and practical advancement in CH construction. Extensive and comprehensive experiments are conducted on real road networks. The experimental results demonstrate the effectiveness and efficiency of our proposed approach.