Reliable Routing from Sparse Observations

Abstract

Sparse observations can make a reliable route difficult to certify even when a feasible path exists. We study routing with
unknown link-disruption probabilities and bounded spatial variation. A multiscale estimator pools observations, corrects for
between-link bias, and produces simultaneous upper confidence bounds. An exact constrained search then minimizes distance
subject to a route-failure limit. The coverage statement permits both pooling radii and routes to be selected after observing
the data. We evaluate the method on a directed street network using three synthetic hazard fields, three observation patterns,
24 trip pairs, and four data budgets. Comparisons include direct confidence bounds, a single-observation-source transfer
envelope, pooled point estimates, a bias ablation, and a true-model oracle. Spatial pooling substantially increased acceptance
in a smooth field, while concentrated hazards reduced its advantage through larger bias allowances. The confidence-based
routes produced no observed risk violations; point estimates and omitted bias corrections sometimes exceeded the prescribed
risk. These results identify when spatial information helps reliable routing and when incomplete sensing or sharp hazard
variation remains limiting.