Let's assume, hidden in a forest, there's a beacon. I walk in the forest and, at random intervals, ping the beacon. For each ping I get a lat/lng pair and the signal strength of the ping at that point (but no direction). At the end of the day I have n readings where n is a random number.
-
How would I compute the location (lat/lng) of the beacon?
-
If, at a later time, I would get another reading, how would I add this to my current estimate of the beacon's location?
Note: we do not know how the forest is affecting the signal strength, but we can assume the effect is uniform – the beacon could be in a clearing, or buried beneath a stone.
I am assuming that all my n readings can be drawn on a map as circles where the lat/lng is the center of the circle and the signal strength is the radius. If the readings are accurate then the beacon should be in that area where all the circles overlap. I have however no clue how to find the center of the overlapping areas of n circles. Can somebody help?
Edit: clarifications
1. Each reading indicates the position I am currently standing in (random location)
2. The signal strength is inversely proportional to the distance between the reading and the beacon although I do not know what is the coefficient. I do however know that this coefficient is the same for all the readings
3. While from a theoretical point of view only two readings are necessary I would like to be able to incorporate as many of the readings as possible in the calculation as all these readings might not be 100% accurate
Best Answer
How much computing power do you have available for the exercise? Some scattered ideas:
For each point on the map you can assume that this is the location of the transmitter, then compute the true distances top each of your sample point and do a least-squares estimation of the unknown proportionality constant. Given that estimate, you can predict what the signal strength at each of your points should have been in an ideal world, and then aggregate the deviations from that, e.g., as the sum of the squared differences.
You then want to find the point on the map that minimizes the error aggregate. Doing this symbolically would probably be complex and restrict your freedom to experiment with different error aggregate functions, so if you have ample computing power, I'd suggest doing it numerically. A brute-force strategy would be to compute the error aggregate for a coarse grid first, and then progress to finer grids in the area around the minimum of the coarse grid points until you reach your desired precision.
A cheaper method would be gradient descent, or start by guessing a point and then iteratively move it in the direction of those sample points where you measured more signal than predicted and away from those where you measured less signal than predicted. This latter idea probably works only when you have the true location well surrounded by samples.
Some thought will need to be given to making sure that the error aggregate is comparable between different guesses even if they have different estimates for the proportionality constant. One way to do this would be to aggregate logarithmic errors instead of absolute ones. Ideally, the choice of error aggregate function should be done based on actual experimental data, as it is difficult to predict by pure reasoning which kind of noise you will face in the real application (and hence which technique for overcoming it will be most effective).
It is probably a good idea to use weighted averages in the calculations such that samples with large signal strength have greater weight than samples with low signal, because these are the ones you need to narrow in on the precise location, and are likely less affected by topographical obstacles.