Using Springs as a Positioning Technique

2006

The Problem

Imagine you are lost in the wilderness. Even though you have a map, you don't know your exact position on it. You can see a mountain far to the North and a radio tower to the West, both of which are located on the map. Using these landmarks as a guide, how do you determine where you are?

The answer lies in determining your distance from the landmarks, and then finding the spot on your map that is the correct distance away from each.

Or you could pull out a GPS device instead!

GPS works almost exactly the same way as the map method above, except that instead of mountains and radio towers, it uses satellites. Each satellite has a known position, and the GPS device basically uses its distance from each satellite to locate itself.

How it works

There are different algorithms for finding your position, but they all need the following information:

• the object we want to position (You)
• a set of landmarks with known locations
• the distance from the object to each landmark

The simplest method is known as trilateration. For each landmark, draw a circle with a radius equal to the distance from the landmark to the object. The object is located at the intersection of the circles.

Trilateration is easy to visualize, but it gets complicated to determine the intersection as you add more circles. This is unfortunate because if you have more landmarks you should be able to determine your location with greater accuracy. To fix this we need a method of solving over-constrained systems.

Given an error function, Least Squares will adjust your variable until it finds the answer with the lowest error. It does this by making an initial guess and then refining it iteratively.

Unfortunately, this is typically calculated by stuffing the error measurements into a matrix, multipying it by other matrices, and performing a matrix inversion. Personally, I hate matrices. I consider them unintuitive relics of a time before computers. Unfortunately, computers are filled with matrix computation now, but I much prefer objects.

My Method

The whole point of Least Squares is to find the least squared error. A real world device that does that is a spring. Everything moves to the point of least energy: balls roll down hills, apples fall on Newton's head, etc. Springs will settle to their rest length. Interestingly enough, the energy function of a spring is determined by the error between its rest length and its actual length, squared. A spring will settle to the point with the least squared error. Nice!

In these diagrams, the black bar represents the rest length of the spring, the blue ball is the fixed point and the red ball is the free point.

So now let's do the calculation:

1. Place fixed points to represent location of each landmark.
2. Place a free point mass at the your estimated position.
3. Attach springs between the point mass and fixed points
4. Adjust the rest length of each spring to be measure distance between you and the corresponding landmark.

The springs will begin to push and pull on the point mass, each trying to reach their rest lengths.

The mass will move until it reaches the point of lowest energy, which is also the correct distance from each landmark. You are here.