Contact: Michalina Pacholska
Synopsis:
Compare the performance of different algorithms on the task of localisation from distances of a device moving on a smooth trajectory.
Level:
The project can be adapted to Bachelor or Master Students.
Description:
The raise of self-navigating devices (be it cars or drones) requires reliable localisation methods. Simplest localisation method is triangulation (or multi-lateration), where the device position is calculated form distances to three (or in 3D, four) known points. This method can be applied to various types of measurements, where the distance can be measured using sound, Bluetooth, wifi or many others.
The problem with this method is that it’s too simple: requires three measurements at each point and does not leverage information about the movement of the device. One way to improve is to assume a trajectory model on the device movement like in [1] or [2]. Then one can optimise trajectory to fit the distance measurements. This optimisation is not convex, and therefore can be challenging.
Both [1] and [2] design specific algorithms for trajectory recovery.
The advantage of those algorithms is that they leverage the knowledge about the problem and that they come with problem-specific performance guarantees. The advantage using optimisation packages like scipy.optimize [3] instead would be that such packages are optimised in terms in terms of performance and provide a variety of very good general solvers/optimisers, like ‘BFGS’ solver [4].
The goal of this project is to compare hand-crafted and general non-convex optimisation methods. Both [1] and [2] provide the implementation of their methods. It is a good exercise in applying optimisation to concrete problems and can hopefully provide both us and the student with new intuitions regarding algorithm selection or design.
Deliverables:
A comparison between task-specific algorithms (in particular 1 and 2), and generic algorithms like ‘L-BFGS’ (potentially chosen by the student), including python implementation and visualisations.
For Master students, additionally one of:
- proposed new algorithm having advantages of both worlds
- analysis of the limits when the algorithms break
- optimisation of the speed of the hand-crafted algorithms
- comparison with learned methods
- student’s idea
References:
[1] Pacholska, M., Dümbgen, F., & Scholefield, A. (2020). “Relax and recover: Guaranteed range-only continuous localization.” IEEE Robotics and Automation Letters, 5(2), 2248-2255.
[2] Tabaghi, P., Dokmanić, I., & Vetterli, M. (2019). “Kinetic euclidean
distance matrices.” IEEE Transactions on Signal Processing, 68, 452-465.
[3] Scipy
[4] BFGS
Prerequisites:
Basics of:
- geometry and linear algebra
- data analysis/visualisations
- Python
- git
- non-convex optimisation (or willingness to learn the topic)
Type of work:
50% development, 50% (data/results) analysis (or 25% analysis, 25% algorithm design, if interested)