VehicleMapping HD AV Spatial Data

Prefetching and Evicting Map Tiles Onboard

The onboard tile cache is where the distribution design either holds or quietly fails. Every other stage of map tile serving and distribution can be correct and the vehicle can still stall at a tile boundary, or grow its resident set until the process is killed, because the cache is answering the wrong question: not what did I use recently but what will I need next.

This task builds the policy that answers the second question — rank candidates by distance from the predicted trajectory, schedule fetches by time-to-need, admit under a ceiling expressed in tiles, and pin the tiles the vehicle cannot lose.

The three tile populations the policy has to keep apart:

Pinned, Prefetch and Evictable Tiles Around a Predicted Trajectory A three-by-four tile grid with a curving predicted trajectory, tiles shaded by their policy class, and the resident ceiling stated. ego pinned pinned prefetch · t+21 s prefetch · t+48 s prefetch · t+34 s evict first evict evict evict evict evict evict just left — LRU would keep it resident ceiling: 9 tiles, counted not measured pinned tiles are excluded from the ceiling's eviction search, never from the count

Prerequisites #

  • Python 3.10+, NumPy 1.24+, shapely 2.0+ for the trajectory distance query.
  • Input: a predicted trajectory over the planning horizon, the current pose, and the quadkey grid from tiling HD maps with quadkeys and H3.
  • Upstream stage: the streaming transport, which delivers verified tiles for admission.
  • Output: a bounded resident tile set and an ordered prefetch queue.

Step-by-Step #

1. Rank candidates by distance from the predicted trajectory #

Rank is a distance, so it is comparable across pinned, prefetch and evictable tiles without a separate policy per class.

python
import numpy as np
from shapely.geometry import LineString, box

def rank_tiles(traj: LineString, candidates: dict[str, tuple]) -> dict[str, float]:
    """Metres from the predicted trajectory to each candidate tile's footprint."""
    return {qk: traj.distance(box(*bounds)) for qk, bounds in candidates.items()}

A tile the trajectory crosses scores 0; a tile one cell off the route scores its edge distance. Expected output: a dict of quadkey to metres, ready to sort in either direction — ascending to prefetch, descending to evict.

2. Schedule prefetches by time-to-need, not by distance #

Two tiles the same distance away are not equally urgent if the vehicle reaches one in eight seconds and the other in fifty. Convert distance along the trajectory to time using the planned speed profile.

python
def time_to_need(traj: LineString, speeds_m_s: np.ndarray,
                 candidates: dict[str, tuple]) -> dict[str, float]:
    """Seconds until the vehicle reaches each candidate tile."""
    stations = np.linspace(0.0, traj.length, len(speeds_m_s))
    dt = np.diff(stations, prepend=0.0) / np.maximum(speeds_m_s, 0.5)
    cumulative = np.cumsum(dt)

    out = {}
    for qk, bounds in candidates.items():
        entry_s = traj.project(box(*bounds).centroid)
        out[qk] = float(np.interp(entry_s, stations, cumulative))
    return out

Key parameter: clamping speed at 0.5 m/s keeps a stationary vehicle from producing infinite times, which would otherwise sort every candidate identically. Fetch in ascending time-to-need and stop when the queue depth reaches the prefetch budget.

Why the two orderings disagree, and why time-to-need is the one to fetch on:

Distance Order against Time-to-Need Order on a Mixed Route A route split into a slow and a fast section, with two candidate tiles whose distance ordering and arrival-time ordering are opposite, and the fetch outcome under each. congested · 5 m/s · 400 m open · 20 m/s · 900 m ego tile B 400 m · reached at t+80 s tile C 1300 m · reached at t+125 s distance order: B, then C on a route that turns off before B, C is never fetched time order: B at 80 s, C at 125 s both scheduled with margin, in arrival order the orderings coincide at constant speed, which is why this bug survives motorway testing and appears in the city

3. Admit under a hard ceiling, and refuse rather than displace #

Admission and eviction are one decision. The cache never grows past the ceiling, and it never evicts something better than what is arriving.

python
def admit(cache: dict, quadkey: str, payload: bytes, rank: dict[str, float],
          pinned: set[str], max_tiles: int = 9) -> bool:
    if quadkey in cache:
        cache[quadkey] = payload
        return True
    while len(cache) >= max_tiles:
        evictable = {k: r for k, r in rank.items() if k in cache and k not in pinned}
        if not evictable:
            return False                       # everything resident is pinned
        victim = max(evictable, key=evictable.get)
        if evictable[victim] <= rank.get(quadkey, float("inf")):
            return False                       # the arrival is worse than the worst resident
        del cache[victim]
    cache[quadkey] = payload
    return True

The second return False is the important one: a prefetch for a route the vehicle has already diverged from must not displace a tile on the route it actually took. Refusing is a correct outcome, not an error — the tile simply is not needed.

4. Pin what the vehicle cannot lose #

The active tile and the tiles its immediate successors occupy are excluded from the eviction search entirely, so no ranking mistake can drop the ground under the planner.

python
def pinned_set(active: str, successors: list[str], horizon_tiles: list[str],
               depth: int = 2) -> set[str]:
    """Tiles that may never be evicted: the active tile and the next `depth` ahead."""
    return {active, *successors[:depth], *horizon_tiles[:depth]}

Keep the pinned set small — two tiles ahead is enough — because every pinned tile is one the ceiling cannot reclaim, and a large pinned set turns the ceiling into a suggestion.

Verification & Acceptance Criteria #

Drive the policy with a recorded route rather than a synthetic one; the failures live in detours and U-turns.

python
def assert_cache_policy(sim, route, max_tiles=9) -> None:
    peak = 0
    for pose in sim.replay(route):
        state = sim.step(pose)
        peak = max(peak, len(state.resident))
        assert state.active in state.resident, "the active tile was evicted"
        assert state.stall_ms == 0, f"planner stalled waiting for {state.waiting_on}"
    assert peak <= max_tiles, f"ceiling breached: {peak} tiles resident"
    print(f"peak resident {peak}/{max_tiles}, no stalls over {route.length_m:.0f} m")

Acceptance gate: peak resident count ≤ the ceiling across the whole replay, including three induced detours; zero planner stalls waiting on a tile; the active tile always resident; and prefetch hit rate above 95%, measured as the fraction of tile entries that found the tile already present.

The measurement that says whether the policy is working, and the two ways it can look fine and not be:

Three Cache Health Signals Across One Route Three traces across a route with detour markers, plus the two diagnostic readings that a single hit-rate number would hide. detour detour prefetch hit rate — above 95% ceiling · 9 tiles resident count — touches the ceiling, never breaches it planner stall — zero a high hit rate with non-zero stall means tiles were resident but not yet decoded a hit rate that does not dip at a detour means the prefetch set is not following the trajectory at all

Common Errors & Fixes #

The planner stalls entering a new tile. Prefetch is ordered by distance rather than time-to-need, so a nearby slow-to-reach tile is starving a distant fast-to-reach one. Switch the ordering as in step 2.

Resident count creeps past the ceiling. The pinned set is growing — usually because successors are being pinned to the full horizon rather than two deep. Cap the pin depth.

A detour causes a burst of refetches. Expected and correct: the trajectory changed, so the ranking changed. What is not correct is the burst evicting the active tile, which the pin prevents.

Memory grows even though the tile count is stable. The ceiling is on the resident dict but staged transfers are unbounded. Bound the staging buffer separately, as the streaming guide does.

Hit rate is high and the vehicle still stalls. The prefetch completed but the decode had not, so the tile was resident and unusable. Count a tile as present only once decoded, not once received.

FAQ #

Why not use an LRU cache for map tiles? #

Least-recently-used ranks by the past and a vehicle's needs are entirely in the future. The tile the vehicle has just left is the most recently used one, and it is also the one least likely to be needed again; the tile it will enter in eight seconds has never been used at all. On a U-turn or a roundabout the two orderings are exactly inverted. Ranking by distance from the predicted trajectory asks the question that matters — what will I need — instead of the one that is easy to measure.

Should the cache ceiling be in tiles or in megabytes? #

In tiles. The vehicle's requirement is expressed in geography — the active tile plus a ring plus the horizon — and that is a tile count. A byte ceiling makes the resident geography depend on lane density, so the same policy holds nine tiles in a suburb and three downtown, which is backwards: dense areas need more coverage, not less. Convert the tile ceiling to a byte budget once, when sizing the device, and enforce the tile count at run time.

How far ahead should the vehicle prefetch? #

Far enough that the fetch completes before the vehicle arrives, with margin for a slow link. Time-to-need is the right unit: at 15 metres per second, one 800 metre tile is about 53 seconds away, and a fetch with a 200 millisecond budget and a few retries needs a couple of seconds. Prefetching more than about two tiles ahead of the horizon wastes bandwidth on routes the vehicle will not take, because route uncertainty grows faster than the fetch cost falls.

Up one level: Map Tile Serving & Distribution — the distribution stage whose onboard half this policy is.