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.
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}.
Let X be a non-empty set and τ be a nonnegative function defined on X×X that satisfies the following axioms:
1) τ(x, y) = 0 if and only if x = y,
2) for any x, y, z in X: τ(x, y) ≤ τ(x, z) + τ(z, y).
Then (X, τ) is called a quasi-metric space.
If τ satisfies the symmetry axiom: for any x, y in X τ(x, y) = τ(y, x), then (X, τ) is a usual metric space.
In SR context, τ(x, y) can be interpreted as the time needed for the sound wave emitted in x to propagate to y.
```rust extern crate sr_rcd;
use std::time::Instant;
use sr_rcd::{
Point,
QMSpace,
rcd,
RMP,
Sensor
};
fn main() { let space = RMP::new(3, 3.14, 1e-4, &Point::new(vec![0.2, -0.15, 0.1]));
let sensorium = vec![
Sensor::make(&Point::new(vec![29.464, 35.926, -32.120]), 75.067),
Sensor::make(&Point::new(vec![9.205, 9.954, 41.401]), 84.306),
Sensor::make(&Point::new(vec![-47.487, 37.405, -24.523]), 60.308),
Sensor::make(&Point::new(vec![-10.429, 47.093, -41.501]), 71.273),
Sensor::make(&Point::new(vec![22.795, -13.970, -36.481]), 59.170),
Sensor::make(&Point::new(vec![-36.803, 15.293, 31.151]), 74.354),
Sensor::make(&Point::new(vec![6.767, -0.990, -10.691]), 48.790),
Sensor::make(&Point::new(vec![31.171, 3.146, -39.320]), 66.633),
Sensor::make(&Point::new(vec![-39.639, 23.027, 42.803]), 86.287),
Sensor::make(&Point::new(vec![-40.483, -29.603, -38.656]), 26.054),
Sensor::make(&Point::new(vec![-40.956, 10.373, -30.528]), 28.183),
Sensor::make(&Point::new(vec![47.117, -43.200, 26.687]), 89.026)
];
let start = Instant::now();
match rcd(&sensorium, &space, &Point::new_default(space.dim()), 100.0, 0.1, 0.001, false) {
Ok(z) => {
println!("Time: {:.3} sec", start.elapsed().as_secs_f64());
println!("RCD-approximated source: {:.4?}", &z);
},
Err(s) => println!("ERROR: {}", s)
}
} ```
The execution result looks like
text
Iteration 1: 39 coverands, d = 279.0151
Iteration 2: 125 coverands, d = 209.7288
Iteration 3: 118 coverands, d = 179.6471
Iteration 4: 9 coverands, d = 26.3082
Iteration 5: 11 coverands, d = 13.1541
Iteration 6: 8 coverands, d = 4.5250
Iteration 7: 11 coverands, d = 2.9208
Iteration 8: 12 coverands, d = 1.5345
Iteration 9: 8 coverands, d = 0.7770
Iteration 10: 9 coverands, d = 0.4110
Iteration 11: 7 coverands, d = 0.1414
Iteration 12: 7 coverands, d = 0.0707
Time: 2.017 sec
RCD-approximated source: [-40.1291, -7.4380, -40.8489]
Hint: release profile should be faster.
See bin/random.rs and bin/manual.rs.
The algorithm is considered in PDF preprint; see also doi:10.12697/ACUTM.2020.24.14 for a slightly simpler and less optimized 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.
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.
In 4D (moreover 5D etc.) the process almost always stucks for a long, on a general purpose computer of nowadays, time at 2nd iteration, with the number of coverands after 1st iteration in hundreds. Extensively, this can be circumvented by using a fast enough computer, but there may be other optimizations.
So, for higher dimensions this is mostly in theoretical realm for now...