We present a deterministic approach for the localization of
an Unmanned Aerial Vehicle (UAV) in a known indoor
environment by using only a few downward distance
measurements and the corresponding odometries between
measurements.
For each distance measurement and odometry, we look at the
preimage of that distance measurement under the downwards
distance function combined with the corresponding odometry
where the motion between every two measurements has four
degrees of freedom: three of translation and one of azimuth
change. The intersection of these preimages yields the set
of all possible locations for the UAV.
In this work, we present an efficient method for
approximating that intersection of preimages. We perform a
spatial subdivision search, which splits only voxels
containing that intersection. We present a novel technique,
based on geometric insights, for correctly evaluating
whether a voxel indeed contains a true localization. This
technique is also robust under different kinds of errors
that might occur. Our method is guaranteed to contain the
ground truth location, and its runtime complexity is output
sensitive, in the Hausdorff dimension and measure of the
resulting intersection of preimages. We demonstrate the
effectiveness of this method in various indoor scenarios,
showing that it can be used to significantly decrease the
uncertainty of localization when solving the kidnapped
robot problem in simulation and on a physical drone. Our
method can be performed in real-time. Furthermore, our
method requires only a map of the environment, odometry and
ToF sensors, which is advantageous in terms of cost,
privacy and transmission bandwidth.
Our open-source software and supplementary materials are
available at https://github.com/TAU-CGL/uav-fdml-public.
