indoor positioning pseudo-range intersection

Hello,

I am currently working on an indoor positioning technique based on the
intersection of range circles/spheres.

It is well known in the GPS literature that clock jitter, estimation
errors etc. lead to imperfect range estimates (pseudo-ranges). The
spheres associated with these pseudo-ranges almost intersect at one
point (the GPS receiver being positioned). This point is determined
using the secondary intersection points which do occur between each
triplet of spheres.
It seems that this pseudo-range intersection method works well when
the range error is much smaller than the actual range.

However for indoor positioning systems the range error may actually be
comparable to the actual ranges. As a result the circles/spheres may
or may not intersect at all. As a result the GPS pseudo-range method
cannot be used all of the time.

Are there alternative pseudo-range intersection methods which can cope
with this problem?

Is the only reasonable answer to improve upon the range estimation
technique until the range errors are no longer comparable to the
actual ranges?


Tom

Thomas Melia wrote:
If the noise ( range error ) is bigger than the signal ( range ) you
will have problems with any method.

--
Regards,

Adrian Jansen adrianjansen at internode dot on dot net
Design Engineer J & K Micro Systems
Microcomputer solutions for industrial control
Note reply address is invalid, convert address above to machine form.

Agreed, the problem gets more difficult; I've been playing with the
stability of a similar algorithm for geolocation of an emitter using TOA
measurements from multiple synchronized (by GPS) receivers. I've found the
best results using a modified weighted Levenburg-Marquand (sp?) algorithm
(standard least squares cost function) with an added "outlier removal" step.
The key is to have enough redundant measurements that you can identify and
remove the outliers (Fault Detection and Exclusion). You generally start at
a trial point and see if things converge; if they don't you start over at a
new trial point and try again. Choice of trial point is an art; for
navigation you can use a previous fix or track extrapolation.

Collect a lot of raw data and then run through numerous algorithm in Matlab
or similar. Good Luck.

Dr. Marty Ryba
martin dot ryba (at) verizon dot net

wrote:

A bit tangential to the original discussion, but the algorithm is
Levenberg-Marquardt. See:

http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm

There are links to freeware implementations at the bottom of the
Wikipedia article.

The SIAM Review published a nice discussion of this method (aka Ridge
Regression) in 1989. See:

http://links.jstor.org/sici?sici=0036-1445 (198909)31%3A3%3C428%3ATEUOMD%3E2.0.CO%3B2-%23

Depending on employer or institution, it may be possible to download
this for free. Also available at SIAM for a fee.

A direct solution of the pseudorange equations might be useful.
Stephen Bancroft published an algebraic solution method in 1985. IEEE
hasn't gotten this one in electronic form yet. One that is available
on-line, and a very small file, is by Kleusberg:

http://www.uni-stuttgart.de/gi/research/schriftenreihe/quo_vadis/pdf/kleusberg.pdf

Some of the Galileo workers had settled on this method, though that
may be a moot point now.

Kleusberg lists the Bancroft paper in his references, as well as other
IEEE papers by Chaffee and Abel. Joseph Leva published a geometry-
based direct solution method that is unfortunately no longer available
on-line for free:

http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/7/11782/00543864.pdf

His method also considers the existence of a solution (as do Chaffee
and Abel and some others), which may be a very useful feature for
indoor nav.

Direct solution methods tend to be a bit throughput intensive,
relative to a linearized algorithm using pseudorange residuals. For
that reason, some systems have used direct methods to initialize the
solution, then use residuals in a linear algebra method for subsequent
fixes.

Good algorithms are useful, but you should also consider that indoors
you have plenty of possibility for multipath reflections off walls and
other objects. These will give you lots of problems, regardless of how
good the algorithms are.

--
Regards,

Adrian Jansen adrianjansen at internode dot on dot net
Design Engineer J & K Micro Systems
Microcomputer solutions for industrial control
Note reply address is invalid, convert address above to machine form.