TDOA, multilateration etc. on small uC

On 09.05.2016 1:18, Tim Wescott wrote:
> On Sun, 08 May 2016 14:16:54 -0700, Paul Rubin wrote:
>
>> rickman <gnuarm@gmail.com> writes:
>>>> A faster CPU would have no real difficulty
>>> Or maybe a CPU is not the right tool for the job.  An FPGA would have
>>> virtually no speed limitations
>>
>> Before we talk about how much speed is needed, it would help to know
>> what calculations have to be done.  I was hoping Tim might have
>> something to say about the math, but I can understand how since he's not
>> getting paid, he may have better things to do ;-).
>>
>> There's a famous math paper called "Can you hear the shape of a drum?"
>> (answer: no) but I don't think it applies here.
>
> Blorping this out as I think of it:
>
> You'd be solving for (essentially) the intersection of three spheres in 3-
> D space (x, y and time * speed).
>
> So, given t_1, t_2, and t_3, arriving at sensors located at (x_1, y_1),
> etc:
>
>          (x_n - x)^2   (y_2 - y)^2
> t_n^2 = ----------- + ----------- + time^2
>            speed^2       speed^2
>
> This gives you three equations in three unknowns, which will have no
> solutions, one solution, or two solutions.  I'm pretty sure that if the
> hardware isn't broken, and you haven't done something dumb like locating
> all of the sensors in a straight line, then you'll get exactly two
> solutions and one will be clearly nonsensical.
>
> What I don't know is if there's a formulaic solution, or if you have to
> solve by root-finding or some such each time.  I _do_ know that Maxima
> chokes on the system of equations -- at least, Maxima's been chewing on
> it for the last five minutes and it still hasn't coughed up an answer.
> That usually means that (a) there isn't an answer, and (b) Maxima isn't
> smart enough to figure that out.  Sometimes, though, it means that
> there's an answer, but it's your job to do the math.
>
> (That's one of the interesting things about symbolic solvers: they make
> it easy to do the moderately hard stuff, but when you throw something
> REALLY hard at it, then you're faced needing to do it yourself -- and
> you're out of practice, because the solver's been doing your work for you
> on the easy stuff.)
>
> Solved problems should be available in the literature -- the math to do
> this has been around since LORAN or even OMEGA.  They used to do it with
> grease pencils on charts, back before microprocessors started eating
> people's brains.
>

One approach to that problem is viewed in Kaplan's "Understanding GPS", 
pp. 54-58 (section 2.4.2 "Calculation of User Position"). If you don't 
own a copy, the third link in google is to the .pdf file with the book:

http://d1.amobbs.com/bbs_upload782111/files_33/ourdev_584835O21W59.pdf

Hope it helps.

Gene

On 09/05/16 08:19, Tim Wescott wrote:
> On Sun, 08 May 2016 13:34:39 +1000, Clifford Heath wrote:
>
>> On 07/05/16 08:57, asdf wrote:
>>> Scenario: a small solid plate of a material yet to decide with equally
>>> spaced vibration sensors along its outer sides.
>>> The plate is small, 1 meter or less, and can be made of wood, acrylic
>>> etc.
>>
>> The stiffer the material, the higher the speed of a surface wave, and
>> the faster your multi-lateration must be. Rubber over 1/8" plywood is
>> good; quiet enough, dense enough, and sufficiently lacking in stiffness
>> that the speed of surface waves is minimized.
>> Wood without rubber would be bad, and acrylic worse.
>
> How about rubber on acrylic?  Wouldn't wood change it's characteristics
> with moisture?

I'd be worried about a fast transverse wave through the acrylic
with a slower main wave following, all resulting from the very
different SoS in the acrylic vs rubber. Wood vs rubber is not
such a big difference - and less so in plywood than natural
timber (the reason ply-top guitars never sound as good).

On 09/05/16 08:19, Tim Wescott wrote:
> On Sun, 08 May 2016 13:34:39 +1000, Clifford Heath wrote:
>
>> On 07/05/16 08:57, asdf wrote:
>>> Scenario: a small solid plate of a material yet to decide with equally
>>> spaced vibration sensors along its outer sides.
>>> The plate is small, 1 meter or less, and can be made of wood, acrylic
>>> etc.
>>
>> The stiffer the material, the higher the speed of a surface wave, and
>> the faster your multi-lateration must be. Rubber over 1/8" plywood is
>> good; quiet enough, dense enough, and sufficiently lacking in stiffness
>> that the speed of surface waves is minimized.
>> Wood without rubber would be bad, and acrylic worse.
>
> How about rubber on acrylic?

Also, is acrylic tough enough?
Some drummers I've seen, you'd want 8mm at least,
and it would eventually fracture anyhow. Plus heavy,
expensive and high SoS (square of thickness, recall?)

I mounted my assembly on close-cell foam to absorb the
energy; no point just spreading it.

On Fri, 6 May 2016 22:57:18 +0000 (UTC), asdf <asdf@nospam.com> wrote:

>So the question is: could such a beast be implemented using
>low cost microcontrollers?

I tinkered with a similar project a few years ago. Mine was an
electronic target for guns.

There are two main tasks to this problem. The first is to detect the
actual time difference between the signals arriving at the sensors. As
an approximation, we can assume that there is only one signal that
looks identical on each sensor, except for the time difference. Given
that assumption, one way to find the time differences is to use
autocorrelation. Wikipedia has an article which goes into some math:
https://en.wikipedia.org/wiki/Autocorrelation

In my case, I found that the sound wave from the passing bullet was so
sharp and so loud (even for subsonic bullets) that it might be
possible to pass it to a digital timer with only slight amplification.
I never got it working properly, though.

The other task you need to solve, is the TDOA math. I spent quite a
bit of time researching this, and my conclusion was that no one had
ever succeeded in solving the equations algebraically. I decided to
try numerical solutions. On a 100x100 grid, I could solve the
equations numerically in a couple of seconds on a Pentium 4 programmed
in Visual Basic 6. Wikipedia has an article on multilateration and
TDOA here: https://en.wikipedia.org/wiki/Multilateration. Is seems to
have been updated quite a bit since I looked at it last. There is now
a section on how to turn the equations into a system of linear
equations in order to reduce computation time. I may have to look into
that some time.
-- 
RoRo

On Wed, 11 May 2016 00:58:09 +0000, Przemek Klosowski wrote:

> On Sun, 08 May 2016 17:18:13 -0500, Tim Wescott wrote:
> 
>> So, given t_1, t_2, and t_3, arriving at sensors located at (x_1, y_1),
>> etc:
>> 
>>         (x_n - x)^2   (y_2 - y)^2
>> t_n^2 = ----------- + ----------- + time^2
>>           speed^2       speed^2
> 
> Wait, t_n-time is the Time Of Flight, so (t_n-time)*speed is equal to
> sqrt((x_n-x)^2+(y_n-y)^2), or
>> 
>>             (x_n - x)^2   (y_2 - y)^2
>> (t_n-t)^2 = ----------- + -----------
>>               speed^2       speed^2
> 
> which differs from your expression.

Well, mebbe.  I'm pretty sure that mine is correct, with the t_n being 
measured times and "time" being the actual time (by the processor's 
clock) of the impact.

> BTW, Maxima can actually solve your expression: it doesn't like to give
> answers that include roots, so you just introduce a variable tsquared,
> and solve for it.

That's handy.

>> (That's one of the interesting things about symbolic solvers: they make
>> it easy to do the moderately hard stuff, but when you throw something
>> REALLY hard at it, then you're faced needing to do it yourself -- and
>> you're out of practice, because the solver's been doing your work for
>> you on the easy stuff.)
> 
> Hard stuff tends to require knowledge of tips and tricks; for instance,
> there's a better Maxima solver package to_poly_solve. You just have to
> know about it.

Know any good Maxima tips & tricks page, or forum?  Generally I push it 
as far as it'll go, then push it a bit farther by checking my work with

<original> - <my candidate>;

(which usually evaluates to zero if my candidate matches the original).

After that I just grumble and do the work myself.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I'm looking for work -- see my website!

On Wed, 11 May 2016 11:23:44 -0500, Tim Wescott wrote:

>>> So, given t_1, t_2, and t_3, arriving at sensors located at (x_1,
>>> y_1),
>>> etc:
>>> 
>>>         (x_n - x)^2   (y_2 - y)^2
>>> t_n^2 = ----------- + ----------- + time^2
>>>           speed^2       speed^2
>> 
>> Wait, t_n-time is the Time Of Flight, so (t_n-time)*speed is equal to
>> sqrt((x_n-x)^2+(y_n-y)^2), or
>>> 
>>>             (x_n - x)^2   (y_2 - y)^2
>>> (t_n-t)^2 = ----------- + -----------
>>>               speed^2       speed^2
>> 
>> which differs from your expression.
> 
> Well, mebbe.  I'm pretty sure that mine is correct, with the t_n being
> measured times and "time" being the actual time (by the processor's
> clock)of the impact.

Your expression can't be right, because it's not invariant wrt. the 
measurement start time t0: let's say you do two measurements, one 
starting at t0 (measuring t_n and calculating 'time'), and another one at 
t0-dt (measuring t_n+dt, and calculating 'time+dt'). x/x_n/y/y_n is the 
same in each case, of course, i.e. the term C=((xn-x)/s)^2+((yn-y)/s)^2 
is constant---but your equation doesn't hold:

(t_n+dt)^2 = C + (time+dt)^2

cancels out most terms but leaves  2 t_n dt = 2 time dt, which is clearly 
wrong.