SR-RCD

Proof-of-concept implementation of Refining-Cover-by-Defect algorithm to solve Sound Ranging problem in quasi-metric spaces.

Part of "Decaennead: ruminations about sound ranging in abstract space(time)s and related themes" project.

Sound ranging

There is an unknown point s, source, which at unknown instant t0 of time emits the sound. The sound wave propagates through space and reaches known points ri, sensors, at known instants ti. The sound ranging (SR) problem, also called source localization or time-difference-of-arrival (TDOA) problem, is to determine s and t0 from {ri, ti}.

Quick start

```rust extern crate sr_rcd;

use sr_rcd::{
Point, QMSpace, rcd, RMP, Sensor };

fn main() { let space = RMP::new(2, 3.14, 1e-4, &Point::new(vec![0.2, -0.15]));

let sensorium = vec![
    Sensor::make(&Point::new(vec![7.404, -15.194]), 38.866),
    Sensor::make(&Point::new(vec![43.341, 25.427]), 64.142),
    Sensor::make(&Point::new(vec![-26.462, -39.81]), 52.927),
    Sensor::make(&Point::new(vec![-30.801, 10.53]), 9.186),
    Sensor::make(&Point::new(vec![47.429, 2.364]), 67.277),
    Sensor::make(&Point::new(vec![-46.583, 15.65]), 23.557),
    Sensor::make(&Point::new(vec![8.321, 17.004]), 34.69),
    Sensor::make(&Point::new(vec![8.553, 36.044]), 37.817),
];

let approx_source = rcd(&sensorium, &space, &Point::new_default(space.dim()), 100.0, 0.1)
    .unwrap();
println!("RCD-approximated source: {:.4?}", &approx_source);

} ```

The execution result looks like

text Iteration 1: 9 coverands, d = 310.4301 Iteration 2: 51 coverands, d = 220.3226 Iteration 3: 86 coverands, d = 191.6949 Iteration 4: 38 coverands, d = 19.0015 Iteration 5: 38 coverands, d = 3.1250 Iteration 6: 76 coverands, d = 4.5670 Iteration 7: 152 coverands, d = 2.2835 Iteration 8: 456 coverands, d = 1.1876 Iteration 9: 912 coverands, d = 0.5709 Iteration 10: 1824 coverands, d = 0.2854 Iteration 11: 3648 coverands, d = 0.1427 Iteration 12: 7296 coverands, d = 0.0714 Time: 2.019 sec RCD-approximated source: [-29.9551, 17.8138]

Hint: release profile should be faster.

See bin/random.rs and bin/manual.rs.

RCD

The algorithm is considered in accompanying PDF preprint; see also doi:10.12697/ACUTM.2020.24.14 for a slightly simpler version in proper metric spaces. Basically, part of space is covered by balls, then the cover is iteratively refined by replacing each ball with its cover by balls of halved radius and discarding the ones such that certain "spread of pasts" at their centers is larger than their doubled radius, until the cover becomes small enough. It is a particular case of the so-called "exclude & enclose" approach.

The algorithm itself is in rcd.rs. Note that tau() (τ) is a duration in time, not a distance in space.

Custom spaces

In principle, the algorithm can work in any quasi-metric space under some assumptions, here there is only a normed space Rmp with constant wind, — see rmp.rs. As soon as QMSpace trait is implemented for AnotherSpace, RCD can work with SR problem in AnotherSpace.

(Im)practicality

This implementation seems to be impractical in 3D (moreover 4D etc.) Euclidean space on general purpose computers of nowadays due to exponential growth of the number of coverands and corresponding time/memory requirements. Also, there are robustness issues.

So, this is mostly in theoretical realm for now...