Fallback Routing Architectures for Indoor Navigation

Fallback routing architectures are deterministic degradation pathways that keep navigation continuous when a primary indoor routing graph fragments, sensor drift exceeds tolerance, or a dynamic closure invalidates a cached topology. This guide sits inside the Indoor Mapping Architecture & Standards framework, where routing resilience is treated as a first-class system requirement alongside ingestion and rendering — the delivery layer of that architecture is exactly where graceful degradation has to live.

The Problem: Routing That Fails Mid-Navigation #

A single shortest_path call is the most common failure point in a production indoor navigation stack. The graph that validated cleanly in CI is not the graph the engine queries at 14:30 on a Tuesday: an elevator has gone into fire mode, a contractor has cordoned off a corridor, and a Bluetooth/Wi-Fi RTLS anchor has drifted 4 metres so the user’s reported origin no longer snaps to any node. The symptoms are predictable and user-visible: the SDK returns NetworkXNoPath, the kiosk shows a spinner, or — worse — the engine returns a geometrically valid path that routes a wheelchair user up a flight of stairs because the only “shortest” edge happened to be a stairwell.

The fix is to stop treating routing as one algorithmic call and model it as a stateful pipeline that degrades through explicit, ordered tiers. Each tier accepts a stricter set of inputs and a looser correctness guarantee than the one above it: high-fidelity sensor-fused routing first, then topology-constrained routing on snapped coordinates, then a vertical-transition workaround, and finally human-readable semantic wayfinding. No tier may drop the user session, and no tier may emit an invalid path silently.

Prerequisites & Dependencies #

This technique assumes the upstream pipeline has already produced a validated, routable graph. Before any fallback logic is meaningful you need:

• A connected routing graph built from topology that passed validation — networkx>=3.0 for in-process graphs, with node IDs and a numeric weight on every edge. Horizontal edges depend on door and threshold detection from Wall & Door Detection Algorithms; vertical edges depend on Level Mapping & Z-Axis Logic.
• A consistent metric coordinate framework. Origin/destination coordinates and node coordinates must share one metric, orthogonal datum — every snapping tolerance below is expressed in metres, which only means anything under a well-defined Indoor Coordinate Reference System. Mixed units (mm node coords vs. m origins) is the single most common cause of a snap that never finds a node.
• A POI index keyed for semantic recovery. The deepest tier needs landmark metadata sourced from your POI Taxonomy & Classification layer — at minimum name, category, and a coordinate per entry.
• Live edge-state feeds. Real-time elevator/escalator availability from a Building Management System (BMS), plus closure events, so edge weights reflect the building’s current state and not last night’s export.
• scipy>=1.10 (optional but recommended) for cKDTree nearest-node indexing once a graph exceeds a few thousand nodes.

How the Degradation Pipeline Works #

The pipeline is a finite state machine. Routing enters at PRIMARY and advances to the next tier only when the current tier returns no path; it terminates the moment any tier produces a navigable result, and reaches SEMANTIC_POI only when geometric routing is impossible. Every transition is logged so a post-mortem can reconstruct exactly which tier served a given session.

1. Primary graph evaluation — A* or Dijkstra traversal over the canonical graph, with edge weights carrying real-time occupancy, HVAC zone restrictions, and temporary closures. Disconnected components, a missing vertical transition, or weight overflow drops to tier 2.
2. Coordinate & topology reconciliation — drifted anchors or a misaligned floor plan break connectivity at the endpoints, not in the middle. Snap origin and destination to the nearest valid node within tolerance, then retry the search over the corrected topology.
3. Z-axis & vertical-transition fallback — when elevators, escalators, or stairwells are flagged unavailable, reweight vertical edges (block the offline ones, bias against detours) and re-solve so the path uses a still-available vertical connector.
4. Semantic & POI-driven routing — when fragmentation defeats geometric recovery, abandon precise coordinates and emit turn-by-turn instructions anchored to high-visibility landmarks and emergency exits.

Step-by-Step Implementation #

The reference implementation below is a typed, production-ready pipeline built on networkx for graph operations and dataclasses for state. It is intended for an indoor navigation microservice or an edge wayfinding kiosk. Build it up in four steps.

Step 1 — Model routing state explicitly #

State the tiers as an Enum and carry per-session context (including the metric tolerance_m used for snapping) in a single dataclass, so every handoff between tiers serializes cleanly.

import logging
from dataclasses import dataclass, field
from enum import Enum
from typing import Any, Dict, List, Optional, Tuple

logging.basicConfig(
    level=logging.INFO,
    format="%(asctime)s | %(levelname)s | %(name)s | %(message)s",
)

class RoutingState(Enum):
    PRIMARY = "primary"
    TOPOLOGY_RECONCILED = "topology_reconciled"
    VERTICAL_FALLBACK = "vertical_fallback"
    SEMANTIC_POI = "semantic_poi"
    FAILED = "failed"

@dataclass
class RoutingContext:
    origin: Tuple[float, float, float]       # (x, y, z) in metres
    destination: Tuple[float, float, float]
    current_state: RoutingState = RoutingState.PRIMARY
    path: List[str] = field(default_factory=list)
    instructions: List[str] = field(default_factory=list)
    tolerance_m: float = 2.5
    metadata: Dict[str, Any] = field(default_factory=dict)

Step 2 — Drive the state machine from a single entry point #

execute advances through the tiers in order and returns as soon as one yields a path. Note that the only public method handles state transitions; each tier is a private helper with a typed signature.

import networkx as nx

class FallbackRoutingPipeline:
    """Deterministic fallback pipeline for indoor routing graphs."""

    def __init__(self, graph: nx.Graph, poi_index: Dict[str, Dict[str, Any]]) -> None:
        self.graph = graph
        self.poi_index = poi_index
        self.logger = logging.getLogger(self.__class__.__name__)

    def execute(self, ctx: RoutingContext) -> RoutingContext:
        """Run the four-tier fallback pipeline, returning the first navigable result."""
        path = self._attempt_primary(ctx)
        if path:
            return self._finalize(ctx, path, RoutingState.PRIMARY, "primary routing")

        ctx.current_state = RoutingState.TOPOLOGY_RECONCILED
        path = self._reconcile_topology(ctx)
        if path:
            return self._finalize(ctx, path, RoutingState.TOPOLOGY_RECONCILED, "topology reconciliation")

        ctx.current_state = RoutingState.VERTICAL_FALLBACK
        path = self._vertical_fallback(ctx)
        if path:
            return self._finalize(ctx, path, RoutingState.VERTICAL_FALLBACK, "vertical fallback")

        ctx.current_state = RoutingState.SEMANTIC_POI
        ctx.instructions = self._semantic_fallback(ctx)
        self.logger.info("Degraded to semantic POI routing.")
        return ctx

    def _finalize(self, ctx: RoutingContext, path: List[str],
                  state: RoutingState, label: str) -> RoutingContext:
        ctx.current_state = state
        ctx.path = path
        ctx.instructions = self._generate_turn_by_turn(path)
        self.logger.info("%s succeeded (%d nodes).", label, len(path))
        return ctx

Step 3 — Implement the geometric tiers (primary, snap, vertical) #

The primary tier is a plain shortest-path call guarded against the two exceptions that actually fire in production — NetworkXNoPath (disconnected) and NodeNotFound (endpoint not in the graph). Reconciliation snaps endpoints to the nearest node; vertical fallback re-solves on a copy of the graph with mechanical edges blocked.

    def _attempt_primary(self, ctx: RoutingContext) -> Optional[List[str]]:
        try:
            return nx.shortest_path(
                self.graph, source=ctx.origin, target=ctx.destination, weight="weight"
            )
        except (nx.NetworkXNoPath, nx.NodeNotFound):
            self.logger.warning("Primary routing failed: disconnected or missing endpoint.")
            return None

    def _snap_to_nearest_node(self, coord: Tuple[float, float, float],
                              tolerance: float) -> Optional[str]:
        """Snap a coordinate to the nearest graph node within a metric tolerance."""
        min_dist, nearest = float("inf"), None
        for node, data in self.graph.nodes(data=True):
            node_coord = (data.get("x"), data.get("y"), data.get("z"))
            dist = sum((a - b) ** 2 for a, b in zip(coord, node_coord)) ** 0.5
            if dist < min_dist:
                min_dist, nearest = dist, node
        return nearest if min_dist <= tolerance else None

    def _reconcile_topology(self, ctx: RoutingContext) -> Optional[List[str]]:
        src = self._snap_to_nearest_node(ctx.origin, ctx.tolerance_m)
        dst = self._snap_to_nearest_node(ctx.destination, ctx.tolerance_m)
        if not (src and dst):
            self.logger.warning("Reconciliation failed: no node within %.1fm.", ctx.tolerance_m)
            return None
        try:
            return nx.shortest_path(self.graph, source=src, target=dst, weight="weight")
        except (nx.NetworkXNoPath, nx.NodeNotFound):
            return None

    def _vertical_fallback(self, ctx: RoutingContext) -> Optional[List[str]]:
        """Route around degraded mechanical transport.

        Used when elevators/escalators are unavailable (maintenance, fire mode,
        power loss): block those edges entirely and bias against stair detours so
        the solver still prefers the most direct stair route. For accessibility
        routing, invert this — keep elevators, penalise stairs prohibitively.
        """
        g = self.graph.copy()
        for _u, _v, data in g.edges(data=True):
            if data.get("type") in ("elevator", "escalator"):
                data["weight"] = float("inf")     # block mechanical vertical transport
            elif data.get("type") == "stair":
                data["weight"] *= 1.5              # bias against stair detours
        src = self._snap_to_nearest_node(ctx.origin, ctx.tolerance_m)
        dst = self._snap_to_nearest_node(ctx.destination, ctx.tolerance_m)
        if not (src and dst):
            return None
        try:
            return nx.shortest_path(g, source=src, target=dst, weight="weight")
        except (nx.NetworkXNoPath, nx.NodeNotFound):
            return None

Step 4 — Implement the semantic tier and instruction synthesis #

The deepest tier never touches the graph. It finds the nearest landmark to each endpoint and synthesises relative wayfinding cues, falling back to corridor-junction language when no POI is close enough.

    def _semantic_fallback(self, ctx: RoutingContext) -> List[str]:
        """Generate landmark-based instructions when geometric routing fails."""
        instructions: List[str] = []
        origin_poi = self._find_nearest_poi(ctx.origin)
        dest_poi = self._find_nearest_poi(ctx.destination)

        if origin_poi:
            instructions.append(f"Start at {origin_poi['name']} ({origin_poi.get('category', 'landmark')}).")
        else:
            instructions.append("Proceed to the nearest visible corridor junction.")
        instructions.append("Follow directional signage toward the destination zone.")
        instructions.append(
            f"Arrive at {dest_poi['name']}." if dest_poi
            else "Arrive at destination coordinates; verify with facility staff if needed."
        )
        return instructions

    def _find_nearest_poi(self, coord: Tuple[float, float, float]) -> Optional[Dict[str, Any]]:
        min_dist, nearest = float("inf"), None
        for _poi_id, poi in self.poi_index.items():
            poi_coord = (poi.get("x"), poi.get("y"), poi.get("z"))
            dist = sum((a - b) ** 2 for a, b in zip(coord, poi_coord)) ** 0.5
            if dist < min_dist:
                min_dist, nearest = dist, poi
        return nearest if min_dist <= 15.0 else None

    def _generate_turn_by_turn(self, path: List[str]) -> List[str]:
        """Convert a node sequence into basic turn-by-turn instructions."""
        steps: List[str] = []
        for i in range(len(path) - 1):
            edge = self.graph[path[i]][path[i + 1]]
            direction = edge.get("direction", "continue")
            steps.append(f"{direction.capitalize()} for {edge.get('weight', 0):.1f}m.")
        return steps

Edge Cases & Gotchas #

Validation Output #

Assert on the tier that served the request, not just on the presence of a path — a path produced by the semantic tier when topology reconciliation should have succeeded is a regression even though it “works”.

def test_drifted_origin_recovers_via_reconciliation() -> None:
    ctx = RoutingContext(origin=(10.4, 5.1, 0.0), destination=(48.0, 22.0, 0.0))
    result = pipeline.execute(ctx)
    assert result.current_state is RoutingState.TOPOLOGY_RECONCILED  # not SEMANTIC_POI
    assert result.path[0] == "node_A12" and result.path[-1] == "node_D03"
    assert result.instructions, "served path must carry turn-by-turn instructions"

Correct output for a recovered path keeps the user on a geometric route:

INFO | FallbackRoutingPipeline | topology reconciliation succeeded (7 nodes).
['node_A12', 'node_A13', 'node_C01', 'node_C04', 'node_D01', 'node_D02', 'node_D03']

Incorrect output — silent collapse to the deepest tier when a node was within tolerance all along — looks navigable but has lost coordinate fidelity, and is the failure your tests must catch:

INFO | FallbackRoutingPipeline | Degraded to semantic POI routing.
['Start at Main Atrium Fountain (landmark).', 'Follow directional signage toward the destination zone.', 'Arrive at destination coordinates; verify with facility staff if needed.']

Performance & Scale Notes #

The linear _snap_to_nearest_node scan is O(n) per endpoint and dominates latency once a campus graph passes a few thousand nodes. Replace it with a scipy.spatial.cKDTree built once per graph version for O(log n) lookups; rebuild the index only when the topology_hash changes so it stays consistent with the published map. Dijkstra over a single building (a few thousand nodes) resolves in low single-digit milliseconds; A* with a Euclidean heuristic pulls ahead only on large multi-building campuses, but disable it the moment any edge weight is inf because an infinite-weight heuristic poisons the priority queue.

The self.graph.copy() in the vertical tier is the most expensive single operation — it is O(V + E) and allocates a full graph clone per request. For high query volume, precompute one “mechanical-blocked” graph variant per BMS state change and cache it keyed by the set of offline connectors, rather than copying on every call. Cache POI metadata locally on edge kiosks so the semantic tier survives a network partition, and standardise every time-bound trigger to UTC with timezone-aware scheduling (zoneinfo) so global deployments do not raise false outage flags during legitimate off-hours maintenance. Because the routing service is the failure boundary for the whole stack, its degraded responses must respect the staleness bounds defined in Cache Invalidation Strategies, and a tier that begins serving consistently degraded paths should trip the alarms wired up by Rollback Triggers & Versioning.

Frequently Asked Questions #

Related #

• Indoor Coordinate Reference Systems — the metric, orthogonal datum every snapping tolerance here depends on.
• Level Mapping & Z-Axis Logic — modelling the vertical connectors the Z-axis tier reweights.
• POI Taxonomy & Classification — the landmark metadata that powers semantic recovery.
• Cache Invalidation Strategies — staleness bounds for degraded, cached routing responses.

This page is part of the Indoor Mapping Architecture & Standards section — return there for the end-to-end pipeline this fallback layer protects.