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.

We address a challenging problem in motion planning where robots must navigate through narrow passages in their configuration space. Our novel approach leverages optimization techniques to facilitate sliding and rolling movements across critical regions, which represent semi-free configurations, where the robot and the obstacles are in contact. Our algorithm seamlessly traverses widely free regions, follows semi-free paths in narrow passages, and smoothly transitions between the two types. We specifically focus on scenarios resembling 3D puzzles, intentionally designed to be complex for humans by requiring intricate simultaneous translations and rotations. Remarkably, these complexities also present computational challenges. Our contributions are threefold: First, we solve previously unsolved problems; second, we outperform state-of-the-art algorithms on certain problem types; and third, we present a rigorous analysis supporting the consistency of the algorithm. In the Supplementary Material we provide theoretical foundations for our approach. The Supplementary Material and our open source software are available at https://github.com/TAU-CGL/tr-rrt-public. This research sheds light on effective approaches to address motion planning difficulties in intricate 3D puzzle-like scenarios.

We present a general approach for determining the unknown (or uncertain) position and orientation of a sensor mounted on a robot in a known environment, using only a few distance measurements (between 2 to 6 typically), which is advantageous, among others, in sensor cost, and storage and information-communication resources. In-between the measurements, the robot can perform predetermined local motions in its workspace, which are useful for narrowing down the candidate poses of the sensor. We demonstrate our approach for planar workspaces, and show that, under mild transversality assumptions, already two measurements are sufficient to reduce the set of possible poses to a set of curves (one-dimensional objects) in the three-dimensional configuration space of the sensor$\mathbb{R}^{2}\times \mathbb{S}^{1},$and three or more measurements reduce the set of possible poses to a finite collection of points. However, analytically computing these potential poses for non-trivial intermediate motions between measurements raises substantial hardships and thus we resort to numerical approximation. We reduce the localization problem to a carefully tailored procedure of intersecting two or more implicitly defined two-manifolds, which we carry out to any desired accuracy, proving guarantees on the quality of the approximation. We demonstrate the real-time effectiveness of our method even at high accuracy on various scenarios and different allowable intermediate motions. We also present experiments with a physical robot. Our open-source software and supplementary materials are available at https://bitbucket.org/taucgl/vb-fdml-public.