Hierarchical routing

Hierarchical routing is a method to scale navigation systems by organizing road networks into levels of detail. Higher levels represent broader routes (e.g., highways), while lower levels detail finer-grained roads. Navigation algorithms utilize these levels to compute efficient routes while minimizing unnecessary computations.

Key Concept: Anchor Points

Anchor points are key connections between different levels of the hierarchy. They ensure continuity when transitioning between higher-level tiles (e.g., highways) and lower-level tiles (e.g., city streets).

Anchor points are used at various levels:

1. Global Planning:
   • High-level algorithms (e.g., Level 0) compute routes between anchor points, ignoring local details.
   • Example: Route includes “Highway A → Exit C → Highway B.”
2. Local Refinement:
   • Anchor points connect high-level routes to finer-level roads.
   • Example: “Exit C” is connected to “City Road D” in Level 1 or Level 2.

Precomputed Connections

During preprocessing, all anchor points are identified and indexed to ensure that:

• Every tile stores a list of inbound and outbound anchor points.
• Boundary edges are consistent across tiles and levels.

---

Preprocessing for Hierarchical Routing

Preprocessing ensures that the road network is partitioned into levels and optimized for navigation.

1. Tile Partitioning:
   • Divide the road network into tiles using a quadtree or other spatial indexing methods.
   • Each tile corresponds to a specific level of detail (e.g., Level 0 for highways, Level 2 for local streets).
2. Hierarchy Construction:
   • Aggregate roads into hierarchical levels:
     • Level 0: Highways and inter-city roads.
     • Level 1: Major urban roads and regional connectors.
     • Level 2: Local roads and neighborhood streets.
   • Simplify lower levels into higher-level representations.
3. Anchor Point Identification:
   • Analyze tile boundaries to detect intersections between levels.
   • Example:
     • A highway in Level 0 connects to a city road in Level 1 via an anchor point.
     • Anchor points are stored as metadata in both tiles.
4. Edge Aggregation:
   • Compress multiple edges into a single high-level edge for Level 0.
   • Expand high-level edges into detailed paths at Level 1 or Level 2.
5. Boundary Validation:
   • Ensure shared edges and anchor points are consistent across adjacent tiles.

---

Algorithms for Multi-Level Navigation

Hierarchical navigation uses algorithms like A* or Dijkstra, augmented to work across levels. The choice depends on requirements for speed and accuracy.

A* and Dijkstra in Hierarchical Routing

• Global Planning:
  • Use A* or Dijkstra on Level 0 to compute the rough route.
  • A* is often preferred due to its heuristic optimization (e.g., Euclidean distance to destination).
• Local Refinement:
  • Drill down into Level 1 and Level 2 tiles near the source and destination.
  • Dijkstra may be used if the local graph size is small enough for exhaustive search.

Augmented Algorithms

1. Multi-Level Dijkstra:
   • Dijkstra’s algorithm is modified to work across hierarchical levels:
     • High-level tiles are processed first.
     • Edges leading to anchor points trigger lower-level expansions.
2. Hierarchical A*:
   • Combines A*’s heuristic with hierarchical optimizations:
     • High-level heuristics guide the global path.
     • Local refinement uses detailed heuristics for precise navigation.

---

Guaranteeing Continuity

Challenges:

• Ensuring that higher-level edges (e.g., highways) connect to lower-level roads (e.g., local streets).
• Maintaining consistent boundary data across tiles and levels.

Solutions:

1. Anchor Point Metadata:
   • Every tile stores a list of its anchor points, shared across levels and neighboring tiles.
2. Dynamic Edge Expansion:
   • High-level edges dynamically expand into detailed paths as needed.
3. Bidirectional Search:
   • Use bidirectional search to validate paths when crossing levels:
     • Search forward from the source and backward from the destination.
     • Merge paths at anchor points.