VERNE: A Spatial Data Structure Representing Railway Networks for Autonomous Robot Navigation

Efficient representation and querying of railway networks are crucial for autonomous railway systems and digital infrastructure management. This paper introduces <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">VEctorial Railway NEtwork (VERNE)</b>, an interpretable data structure and algorithm that integrates vector-based spatial partitioning with a railway-specific topological framework to enhance network representation and navigation. VERNE is designed to optimize query efficiency, reduce memory footprint, and ensure scalability for real-time applications. Its internal mechanism results from a comparative performance analysis between a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-d tree, an STRtree and two custom algorithms, highlighting trade-offs in computational efficiency and memory overhead. The proposed approach is validated using datasets from both the French and Swedish railway networks, demonstrating its effectiveness in real-world scenarios. The results indicate that VERNE provides a robust and scalable solution for railway infrastructure modeling, offering improvements in localization speed and computational efficiency. Another advantage is that it inherently manipulates atomic elements which can contain any information relevant to directly perform navigation onboard an autonomous robot. This work contributes to the advancement of railway digitalization by providing a structured methodology for spatial data processing in autonomous railway systems.