PaperlayerView exact revision on arXiv

Source-linked AI summary

Monte Carlo-Based Indoor UAV Localization in Dynamic Environments Using Only Four Onboard Range Sensors

Mohammad Reza Ranjbar Divkoti, A. Pedro Aguiar

arXiv:2610.32645v1cs.RO

TL;DR

Indoor UAV localization with sparse onboard sensing must handle unknown dynamic obstacles, while existing approaches trade sensing and computational complexity for accuracy. AF-MCL filters inconsistent ranges and adaptively injects particles; experiments report centimeter-scale mean errors in simulation and real-world flights using four range sensors and measured heading.

  • Problem

    Reliable indoor localization with only four single-point range measurements and heading remains a challenge when unknown moving obstacles can corrupt individual measurements.

    Source: §I · p. 1

  • Method

    AF-MCL rejects ranges inconsistent with the static map before particle weighting and adaptively injects particles when divergence is detected.

    Source: §I · p. 1

  • Results

    Mean errors are 4.5–5.2 cm in simulations and 6.4–7.7 cm in real-world experiments, with AF-MCL outperforming standard MCL under dynamic obstacles.

    Source: §V · p. 7

  • Takeaways & Limitations

    The results show that indoor UAV localization under dynamic obstacles is achievable using only four single-point range measurements and measured heading.

    Source: §V · p. 7

    Rejecting beams can leave retained measurements poorly conditioned or rank deficient, increasing their sensitivity to measurement perturbations.

    Source: C. Conditioning and Local Measurement… · p. 4, §V · p. 7

Abstract

from arXiv · show

Indoor UAV localization with minimal onboard sensing remains challenging, particularly in dynamic environments. We propose augmented filtered Monte Carlo localization (AF-MCL) for 2D localization using only four single-point range sensors and measured heading. AF-MCL rejects range measurements inconsistent with the known static map and adaptively injects particles to recover from localization divergence and kidnapping. Beam classification is performed only at the previous position estimate, making its ray-casting cost independent of the particle count. The particle distribution additionally provides an online measure of localization uncertainty. Real-world experiments in a 2.10x1.63 m environment yield mean position errors of 6.4-7.7 cm under static and dynamic conditions. Simulations in 6x6 m and 10x10 m environments yield 4.5-5.2 cm mean errors; under dynamic obstacles, standard MCL reaches 12.3 cm and reliable MCL 7.7 cm. The results show that robust indoor localization under dynamic obstacles is achievable with only four single-point range measurements and heading.

I. INTRODUCTION

The paper asks whether indoor UAV localization can remain reliable with only four single-point ranges and heading, including when unknown moving obstacles corrupt measurements. It introduces AF-MCL alongside a Monte Carlo localization framework for estimating position in a known map.

I. INTRODUCTION

  • AF-MCL rejects ranges inconsistent with the static map before particle weighting and adaptively injects particles when divergence is detected.Beam classification is performed at the previous position estimate, independently of particle count.Source: §I · p. 1
  • Simulations yield 4.5–5.2 cm mean errors, and real-world flights yield 6.4–7.7 cm mean errors using four single-point ranges and measured heading.The evaluated real-world environment is 2.10 × 1.63 m; simulations use 6 × 6 m and 10 × 10 m environments.Source: §I · p. 1

A. Monte Carlo Localization for Static Indoor Environments

  • MCL represents UAV position with weighted particles, propagates them using body-frame velocities and measured yaw, and weights them using range likelihoods from the map.Yaw is measured rather than estimated, and the particle set is initialized around the known initial position.Source: A. Monte Carlo Localization for Static… · p. 2

B. Augmented Filtered Monte Carlo Localization (AF-MCL) for Dynamic Indoor Environments

AF-MCL filters dynamic-obstacle measurements using the static map, then uses retained beams to update particles. It also monitors divergence for recovery and derives an online uncertainty measure from the particle set.

Static-beam classification

  • Each beam is classified by comparing its measured range with the map-predicted range at the previous position estimate; inconsistent beams are excluded from weighting.This avoids particle-wise ray casting, and classification ray-casting overhead is O(1) per beam.Source: B. Augmented Filtered Monte Carlo… · p. 3

Divergence detection and augmented resampling

  • When divergence is detected, AF-MCL injects recovery particles sampled uniformly across unoccupied map space alongside resampled particles.The injection probability is dynamically determined from fast and slow running likelihood averages and is capped by ν.Source: B. Augmented Filtered Monte Carlo… · p. 3

Online localization uncertainty

  • The final particle set supplies an online uncertainty measure, and injected recovery particles increase that uncertainty when the estimate is less trustworthy.The particle spread is an uncertainty indicator, not a guaranteed error bound.Source: B. Augmented Filtered Monte Carlo… · p. 3

Empty beam set

  • If every beam is rejected, the update becomes motion-only and no recovery particles are injected, which can delay recovery from a large localization error.The authors report that this case occurred rarely in their experiments.Source: B. Augmented Filtered Monte Carlo… · p. 3

III. THEORETICAL ANALYSIS

The theoretical analysis considers AF-MCL’s computational cost and the local geometry of retained measurements. It explicitly treats the geometry analysis as distinct from a particle-filter convergence analysis.

III. THEORETICAL ANALYSIS

  • The analysis examines how classifying beams at the previous estimate affects computational complexity and the geometry retained after inconsistent beams are rejected.It focuses on rank and conditioning, not particle-filter convergence.Source: §III · p. 4
  • The analysis treats the retained beam set as a subset of M sensors and assumes distance-transform lookups and single-beam likelihood evaluations have bounded cost independent of particle count.It denotes particle count by N and ray-cast cost by C_ray.Source: §III · p. 4
  • The retained-measurement geometry analysis is local and does not establish convergence of the particle filter.Source: §III · p. 4

A. Computational Complexity

AF-MCL performs beam classification once per sensor at the previous estimate, while particle weighting remains dependent on the number of retained beams. This makes classification ray-casting cost independent of particle count.

A. Computational Complexity

B. First-Order Geometry of the Retained Beams

The section characterizes when retained range beams locally identify UAV position: their range gradients must provide two independent geometric constraints. The analysis applies locally where each retained beam continues to intersect the same map boundary.

B. First-Order Geometry of the Retained Beams

  • The analysis applies locally where the map boundary intersected by each retained beam remains unchanged and the range functions are continuously differentiable.Source: B. First-Order Geometry of the… · p. 4
  • Two retained beams with non-collinear range gradients provide first-order geometric identifiability of the 2D position.Equivalently, the retained measurement Jacobian must have rank 2 and a trivial null space.Source: B. First-Order Geometry of the… · p. 4
  • Retaining front and back beams can leave the position rank deficient because their gradients may be anti-parallel.In that case, rank HQt = 1 and one position direction remains unresolved to first order.Source: B. First-Order Geometry of the… · p. 4

C. Conditioning and Local Measurement Sensitivity

The smallest singular value of the retained-beam Jacobian measures the weakest local geometric constraint and therefore the sensitivity of position to measurement perturbations. This is a statement about instantaneous measurement geometry, not the full filter error.

C. Conditioning and Local Measurement Sensitivity

IV. RESULTS AND DISCUSSION

The evaluation compares five localization algorithms in simulation and further validates AF-MCL in real-world experiments. The simulation setup and scene are documented through a parameter table and a Webots environment figure.

IV. RESULTS AND DISCUSSION

  • The study evaluates MCL, A-MCL, F-MCL, R-MCL, and AF-MCL in simulation, and validates AF-MCL in real-world experiments.The UAV follows nonlinear dynamics under low-level PID control with constant altitude, forward velocity, zero lateral velocity, and angular-velocity references.Source: §IV · p. 4
  • Table I is identified as the listing of simulation parameters.Source: Table I · p. 5
  • The Webots simulation scene shows the Crazyflie UAV, static walls, and dynamic obstacles used to test localization robustness.Source: Figure 2 · p. 5

A. Simulation Setup

The simulations use a Crazyflie 2.1 model with a 10 Hz filter and a 2 cm occupancy grid. Heading is noise-free in simulation, while range readings include Gaussian noise and invalid measurements are discarded.

A. Simulation Setup

  • The filter runs at 10 Hz on a 2 cm occupancy grid, with the distance transform truncated at the 10 m sensor range limit.The simulated UAV flies at 0.3 m altitude, with linear and angular velocities of 0.3 m/s and 0.4 rad/s.Source: A. Simulation Setup · p. 5
  • Four range sensors are mounted at the UAV center in front, left, back, and right orientations, and simulator heading is noise-free.Source: A. Simulation Setup · p. 5
  • Range readings receive 2 cm-standard-deviation Gaussian noise, while missing, non-finite, non-positive, or out-of-range measurements are discarded before weighting.Source: A. Simulation Setup · p. 5
  • The decay rates satisfy αslow ≪ αfast, σobs exceeds sensor noise, and ν caps particle injection so most particles remain importance-resampled.Parameters were empirically determined by manual tuning.Source: A. Simulation Setup · p. 5

B. Ablation and Comparative Study

The dynamic-obstacle ablation compares MCL variants across two map sizes and trajectory shapes. Filtering supports accuracy, while augmentation mainly addresses recovery rather than routine accuracy.

B. Ablation and Comparative Study

  • The comparison evaluates standard MCL, A-MCL, F-MCL, AF-MCL, and R-MCL across square and S-shaped trajectories in 6 × 6 m and 10 × 10 m environments.The study uses a 4-range LiDAR setup under dynamic obstacles.Source: B. Ablation and Comparative Study · p. 5
  • AF-MCL and F-MCL achieve the lowest errors in both map sizes, with their errors differing by no more than 0.005 m.Augmentation alone is harmful in this regime: dynamic-obstacle readings can trigger false divergence recovery and scatter particles.Source: B. Ablation and Comparative Study · p. 5, Figure 3 · p. 5, Table II · p. 5
  • A-MCL’s standalone augmentation is harmful under dynamic obstacles because corrupted readings can trigger false recovery and scatter particles.Filtering removes those readings, so particle injection is triggered mainly by genuine divergence and serves as a recovery mechanism rather than an accuracy source during normal operation.Source: B. Ablation and Comparative Study · p. 5

C. Kidnapping Recovery

The section evaluates AF-MCL’s recovery after kidnapping, its runtime as particle count varies, and the geometry of retained measurements. AF-MCL recovers faster than MCL in the kidnapping test, while runtime and geometric results reveal computational and information trade-offs.

C. Kidnapping Recovery

  • AF-MCL recovers from kidnapping in 2.9 s versus 16.9 s for MCL; mean trajectory error is 0.191 m versus 0.701 m.The test displaces the UAV after 2 s and ends the kidnapping at 12 s; recovery time is measured from the start of the kidnapping.Source: C. Kidnapping Recovery · p. 6

D. Runtime vs. Number of Particles

  • A 16× increase in particle count raises total update time by about 65%, while classification remains within 1.8–2.1 ms across tested counts.Classification is the largest single cost at every tested count, but its share falls from about 61% at N = 25 to 41% at N = 400; position error shows no meaningful dependence on N in this range, so N = 25–100 gives sufficient accuracy at lower cost in this setup.Source: D. Runtime vs. Number of Particles · p. 6

E. Validation of the Geometric Analysis

  • When only the front and back sensors remain, their anti-parallel range gradients produce rank HQt = 1 and σmin(HQt) = 0; the largest error increase, to approximately 0.19 m, coincides with one such interval.Not every instantaneous rank loss produces a large error, because AF-MCL also carries information from the prior belief and motion model; the experiment illustrates measurement conditioning, not a direct error relation.Source: E. Validation of the Geometric Analysis · p. 6, Figure 5 · p. 6

F. Real-World Experimental Results

AF-MCL was evaluated in real-world UAV trials and simulations, with low reported position errors across static and dynamic obstacle conditions. The experiments also examine runtime, uncertainty estimates, and limits on interpreting measured accuracy.

F. Real-World Experimental Results

  • Six scenarios in a 1.63 × 2.10 m² environment covered S-shaped and square trajectories with no obstacles, static obstacles, or static and dynamic obstacles.The trials used a Crazyflie 2.1 with four-directional ranging and Qualisys cameras for ground truth; localization ran on a host PC.Source: F. Real-World Experimental Results · pp. 6–7
  • Mean error stayed within a narrow range across scenarios, while mean runtime remained below the 100 ms command interval on the host computer.The particle-spread uncertainty was lower than error in five of six scenarios; reported errors also include map and ground-truth uncertainty, each bounded at approximately ±2 cm.Source: F. Real-World Experimental Results · p. 7
  • The runtime result supports real-time operation on the host PC but does not establish execution on the Crazyflie flight controller.Source: F. Real-World Experimental Results · p. 7
  • In open-loop replay of logged flights, standard MCL reached 0.096 m mean error on the square trajectory with static and dynamic obstacles, versus 0.074 m for F-MCL and AF-MCL.Beam filtering reduced error by about 23%; the logged flights had been run with AF-MCL.Source: F. Real-World Experimental Results · p. 7

V. CONCLUSION

  • Real-world mean errors were 6.4–7.7 cm, while simulations in 6 × 6 m and 10 × 10 m environments yielded 4.5–5.2 cm mean errors.Source: §V · p. 7
  • Beam rejection can leave retained measurements poorly conditioned or rank deficient, increasing sensitivity to measurement perturbations.The conclusion identifies geometry-aware filtering and uncertainty adaptation, and localization without a prior map, as future work.Source: §V · p. 7

F. Real-World Experimental Results

  • Real-world position errors were 0.061 m, 0.059 m, 0.065 m, and 0.076 m across four obstacle-containing trajectory scenarios.The corresponding plots show low, stable errors without visible divergence or drift, including near obstacles.Source: F. Real-World Experimental Results · p. 7, Figure 8 · p. 8
Loading 2610.32645v1…