Steering to Shrink the Uncertainty Set: Active Mapless Radio Localization of Moving Nodes

When radio signals bounce around walls or pass through them, a measured distance between two radios almost always comes out too long and almost never too short. A robot that measures its distance to an unknown radio tag in a cluttered, unmapped building therefore learns one thing it can rely on: the tag lies inside a ball of that radius around the robot. Each new measurement from a new vantage point adds another ball, and the tag must lie in their intersection. This note proposes to let the robot choose where to go next so that this intersection shrinks as fast as possible, while it still pays attention to distance traveled and to smooth motion. It also proposes to stop assuming the tag stays put: if the tag can move at some bounded speed, old balls are allowed to grow over time. The result is a planner that optimizes a guarantee (the tag is provably inside this region, under stated assumptions) instead of a statistical estimate that is only valid if the error model is right.

This matters because today's methods for handling these too-long "non-line-of-sight" (NLOS) measurements are passive. They take whatever path the robot or person happened to walk and try to salvage an estimate. Planners that do care about localization quality instead need a prebuilt map of the environment. In practice, the cheapest path, which is a straight line that hugs corners, is often the path that keeps the radio link blocked. A robot that can reason about its own uncertainty region without a map can buy accuracy with motion. Examples include finding a person's beacon in a smoke-filled building, localizing opportunistic radios in an unsurveyed facility, and tracking a walking tag.

Core Claim

The claim is that the bounded-error view of NLOS ranging is also a natural objective for planning. This view treats every measured range $\hat d_k$ as an upper bound on the true distance. Minimizing the predicted size of the resulting feasible set, traded against path length, yields trajectories that localize static and moving radio nodes faster and more reliably than two alternatives. The first is planners that maximize Gaussian information measures such as geometric dilution of precision. The second is simple heuristics that drive toward the current estimate. No map and no prior NLOS statistics are needed. Concretely, with agent position estimate $p_k$ at measurement time $t_k$, noise floor $\epsilon$, agent odometry-drift bound $\delta(t_k)$ and target speed bound $v_{\max}$, the set containing the target at time $t$ is

$$S_t = \{x : \|x - p_k\| \le \hat d_k + \epsilon + \delta(t_k) + v_{\max}(t - t_k) \ \ \forall k : t_k \le t\}.$$

The last two terms are what drop the static-topology assumption. The $\delta$ term covers the agent's own drift, since the agent is a moving anchor with imperfectly known position. The $v_{\max}$ term covers the target's motion. With $v_{\max}=0$ and $\delta=0$ this reduces to the static convex ball-intersection used in NLOS localization. The planner chooses a trajectory $u$ to trade the path cost $L(u)$ against the predicted Chebyshev radius $r_T(u)$ of $S_T$ at mission time $T$. The Chebyshev radius is the radius of the largest ball fitting inside the set, and it bounds worst-case error. The trade is posed as an $\epsilon$-constraint, minimize $L(u)$ subject to $r_T(u) \le r^\star$, and the constraint is swept to trace the Pareto front.

The distinctive, testable consequence concerns range. Under a Gaussian range model with constant noise, information depends only on bearing diversity. It is indifferent to how far the robot stands from the target. Under the upper-bound model, a ball only cuts the set if its radius is small relative to the set, so the objective rewards approaching the target from diverse directions. Approaching also tends to reduce the number of walls in between. The two objectives should therefore produce visibly different trajectories, and the difference should matter most exactly where NLOS is heavy.

Relation to Prior Work

Three works supply the estimation machinery, and all three are passive. Chen et al.'s SDP method relaxes NLOS ranges into convex upper-bound constraints solved by semidefinite programming. Ding and Qi's convex EDM embedding solves a related robust relaxation with a 3-block ADMM that scales to thousands of sensors. Shi et al. minimize worst-case error by computing the Chebyshev center of the bounded-error feasible set. We reuse the Chebyshev-radius view from Shi et al. as the planning target. All three assume static nodes and take measurement geometry as given. We make the geometry a decision variable and inflate constraints for motion. Shi et al. also constrain the design: they note that the Chebyshev center of a non-convex feasible set can fall outside the set. We keep the set convex by using only upper-bound balls. We add lower bounds only as an ablation.

Four works show that mobile, mapless ranging is feasible but leave motion exogenous. PEOPLEx jointly estimates a walking user's path and unknown UWB anchor positions in a factor graph. Armani and Holz track moving UWB/IMU nodes without any anchors, using EKFs refreshed by multidimensional scaling. Xu et al.'s double EKF adapts noise covariances from residuals to survive NLOS with fixed anchors. None of these chooses where to move, and the double EKF is purely reactive to residuals. BALLAST and LASER supply the motivating lesson that sensing decisions in non-stationary settings must look ahead rather than react. But both assume sensor positions are known exactly and ignore NLOS ranging.

The closest active work is GFM-Planner. It plans paths that trade path energy against a LiDAR scan-matching quality metric, but it precomputes that metric from a prebuilt map. Zhu et al. route UAV anchors to localize moving ground users and stop at the edge of an accuracy region. Their "edge access" idea is close in spirit to our $r^\star$ constraint, but they use a log-normal received-signal-strength model that has no notion of one-sided NLOS bias. We differ from both by planning on a map-free, one-sided bounded-error set. For the optimizer we borrow the trust-region sequential convex programming of Chen et al.'s TR-SCO, which linearizes non-convex constraints inside a trust region.

Research Program

The work has four parts.

The first is a cheap, differentiable surrogate for $r_T(u)$. Exact ball intersections grow with the number of measurements, so we maintain an outer ellipsoid of $S_t$ using ellipsoidal set-membership updates. Growth from $v_{\max}$ and $\delta$ becomes a Minkowski inflation. Each hypothetical future measurement from a candidate waypoint becomes an ellipsoid-ball intersection whose outer volume is smooth in the waypoint. The exact Chebyshev center is recomputed by a small second-order cone program only when reporting estimates, which keeps the reported guarantee exact.

The second part addresses the missing prior on NLOS error, which is what makes the problem genuinely mapless. The planner must predict how long future ranges will be. We use the slack of past constraints, meaning how far each measured radius exceeded the set's far boundary, as an online empirical sample of bias. The planner predicts future ranges as true distance plus a chosen quantile of that sample. This needs no floor plan and no offline statistics. It adapts as the robot learns how cluttered the building is.

The third part is the optimizer. Receding-horizon trust-region sequential convex programming minimizes path length and a jerk penalty, subject to the predicted radius constraint and to obstacle clearance taken only from onboard short-range proximity sensing. There is deliberately no global map.

The fourth part scales the approach to several seekers. A team of robots shares ball constraints. The joint objective then also rewards angular separation between the robots, which connects to the geometric-rank conditions that Fang et al. show are necessary for distributed localization.

Baselines

The naive reference point is a fixed coverage path: a lawnmower sweep of the area, with the same bounded-error estimator run on the collected ranges. It measures what passive estimation gets for free.

A second simple baseline is greedy approach. The robot repeatedly drives toward the current Chebyshev center, with the same estimator and obstacle handling. It is simple and dangerous to dismiss, because approaching the target is also what our objective rewards.

The strongest competitor for the planning question is information-driven active localization. It uses the same receding-horizon TR-SCO optimizer, but the objective is the Fisher-information determinant (equivalently, low geometric dilution of precision) under a Gaussian range model. The estimator is a robust EKF with chi-square gating and residual-based covariance adaptation in the style of Xu et al.. This is the natural combination a practitioner would build, and it isolates exactly one change: the objective. It is our reconstruction; we are not aware of a published version for mapless NLOS ranging.

For the passive-estimation question, the strongest reported systems are the following. Armani and Holz report 10.2 cm tracking RMSE for three RC cars with wooden NLOS obstacles in a 3 m × 5 m area. Xu et al. report NLOS tracking within 10 cm in a 46 m² office with metal-plate obstacles and four fixed anchors. Both use far denser or fixed infrastructure than our single-seeker setting, so they serve as reference points rather than direct opponents. For the active mapless NLOS setting itself, no reported result was found on Lacuna.

Every planner gets the same robot, radio schedule, time budget, onboard obstacle sensing, and a fixed hyperparameter search of equal size. Beating the strongest baseline means two things together. The first is reaching a fixed certified radius $r^\star$ with at least 20% less path length on the median trial in heavy-NLOS scenes. The second is Chebyshev-center error that is no worse. Both must hold while the containment rate stays at or above the nominal level.

Three ablations isolate the key ingredients. The first sets $v_{\max}=0$ and $\delta=0$, restoring the static assumption, and measures containment violations on moving targets. The second replaces the online bias quantile with zero bias. The third keeps our objective but swaps the estimator for the gated EKF, which separates the planning gain from the estimation gain.

Why not just…?

Why not just maximize Fisher information or minimize dilution of precision, which is the standard active-localization objective? This is the real threat. In mostly line-of-sight scenes it may match us, because ranges are then nearly unbiased and bearing diversity is what matters. Our argument is that the Gaussian model ignores the one-sided bias and is blind to distance. It will happily circle a target from far away through walls. The experiments settle this by sweeping the NLOS fraction. If the information-based planner matches us even at high NLOS fractions, the claim fails, and the contribution reduces to the certified set estimate.

Why not just drive toward the current estimate? Greedy approach captures much of our objective's pull toward the target. It fails in two predicted cases. The first is when the straight approach runs through an obstruction, where it keeps collecting biased ranges from one bearing and the set stays elongated. The second is when the target moves, where chasing a stale center oscillates. If greedy approach is within noise of our planner across our scenes, we will report that. We would then restrict the claim to the multi-seeker and moving-target regimes.

Why not just build a map first with LiDAR or visual SLAM and ray-trace the NLOS links? Mapping costs time and sensors that the target applications lack. Zhu et al. frame post-disaster search as time-critical. PEOPLEx reaches meter-level accuracy on phone radios with no floor plan. Ray-tracing a geometric map also does not predict signal penetration through materials. We include a map-given oracle planner in simulation as an upper bound, to quantify how much of the gap mapless planning closes.

Why not just a weighted-sum scalarization instead of an $\epsilon$-constraint front? For a single seeker, a weighted sum swept densely may recover most of the front. The $\epsilon$-constraint form is chosen because the certified radius is a mission requirement: stop when the tag is known to within $r^\star$. Xiao et al. also show that obstacle-rich 3-D planning yields non-convex fronts that fixed weights miss. We will report both and compare front coverage.

Proposed Experiments

The simulation uses 2-D and 3-D indoor scenes with UWB ranging. Positive NLOS bias is generated by ray tracing through walls with material-dependent excess delay, in the uniform positive-bias spirit of Chen et al.'s benchmark, and the agent never sees the geometry. The Motorola facility measurements used by Ding and Qi, where their EDM method reports 1.38 m RMSD against 1.54 m for SDP, calibrate realistic bias magnitudes. Targets are static, walking at up to 1.5 m/s (matching Zhu et al.), or adversarially evasive. Scenes vary NLOS fraction from roughly 10% to over 90%, the range over which Ding and Qi report passive convex methods still function.

The hardware replicates the Armani and Holz setup: RC-car seekers and a tag with single-antenna UWB and IMU, motion-capture ground truth, and wooden and metal obstacles. The tag is either static or carried on a moving car.

The metrics are four. Path length and time to reach certified radius $r^\star$ measure efficiency. Chebyshev-center RMSE measures accuracy. The containment rate, meaning the fraction of timesteps where the true tag lies in $S_t$, tests whether the guarantee holds. Pareto hypervolume in (path length, final radius) measures the quality of the trade-off.

Three checks are decisive. The first is whether the gap between our planner and the Fisher-information planner grows with NLOS fraction, as the one-sided-bias argument predicts. If it does not grow, the central claim is wrong. The second is whether removing the motion inflation produces containment violations on moving targets while leaving static-target results unchanged. This directly shows the cost of the static assumption. The third is whether online bias quantiles hold containment near nominal without any prior statistics.