TAD

Took A Detour

A fastest-path routing algorithm on city road graphs using non-uniform speed modelling based on turns, road width, and curvature.

Description

TAD (Took a Detour) is a high-fidelity pathfinding algorithm that proves the shortest path isn't always the fastest. Unlike standard GPS algorithms that rely on static speed limits, TAD uses kinodynamic path planning to calculate the fastest route based on vehicle acceleration, braking capabilities, road width, and junction geometry.

Key Features

• Physics-Based Weighting: Calculates $V_{max}$ for every turn using the relationship between road width and turning radius.
• Kinodynamic Constraints: Users can input specific Acceleration and Deceleration rates to see how different vehicles (e.g., a sports car vs. a heavy truck) choose different "fastest" paths.
• Width-Aware Routing: Factors in "Effective Radius" ($R_{eff}$); wider roads allow for "clipping the apex," enabling higher speeds through junctions.
• State-Based Dijkstra: A modified search algorithm that tracks entry-velocity to accurately penalize "momentum loss" at sharp corners.

Logic

1. The Geometry of the "Apex"

TAD assumes drivers don't turn at sharp 90° angles but follow a curved arc. A wider road allows for a shallower arc due to a larger radius. We calculate the Effective Radius ($R_{eff}$) at a junction using the deflection angle ($\theta$) and the available road width ($W$):

$$R_{eff} \approx \frac{W}{\sin(\frac{\theta}{2})}$$

The maximum safe velocity through that junction ($V_{turn}$) is then constrained by the centripetal friction limit ($\mu \approx 0.7$):

$$V_{turn} = \min(V_{limit}, \sqrt{\mu \cdot g \cdot R_{eff}})$$

2. Momentum-Aware Edge Weighting

Unlike standard Dijkstra where edge weights are static, TAD weights are dynamic. The cost of an edge depends on the vehicle's speed at the start of that edge. The algorithm simulates three distinct phases for every segment:

• Phase A: The Deceleration Zone: If the entry speed is higher than the upcoming $V_{turn}$, TAD calculates the time ($t_d$) and distance ($d_d$) required to brake.
• Phase B: The Recovery Zone: After the turn, TAD calculates the time ($t_a$) and distance ($d_a$) required to accelerate back to the road's speed limit (60mph).
• Phase C: The Cruise Zone: If there is remaining distance in the segment, the time spent at top speed is added.

The Result: A 100-meter "shortcut" with two sharp turns might be assigned a higher time cost than a 200-meter curved "detour" because the shortcut forces the vehicle to spend ~60% of its time in the high-cost Deceleration and Recovery phases.

3. State-Space Expansion

Because the speed at a junction depends on the angle of the turn, the algorithm must know where the vehicle is coming from. TAD transforms a standard Point-Graph into a State-Graph:

Standard Node: Intersection_A

TAD State: (Intersection_A, Incoming_Heading_Vector)

This allows the algorithm to distinguish between a "Straight-Through" move (low penalty) and a "U-Turn" move (maximum penalty) at the exact same physical node.