I'm using this post to share some Processing code I wrote a while ago. I was asked by David Glowacki of the Danceroom Spectroscopy project if I knew of an algorithm to determine the centre of a group of electronic handheld devices without using an external infrastructure. I wrote a decentralised algorithm inspired by the Kalman filter but it fell short against other alternatives for the project. I think the algorithm is interesting though, so here it is, and I'll try to explain it. I've not checked if a similar algorithm already exists, so I'd welcome any commentary. If you're really interested, you can play with the processing sketch, code at the end, or via GitHub.
ContextWe were interested in whether a handheld device could know if it was at the centre of a group without being told it was. Therefore, there would be no overhead tracking equipment and no big computer to dictate where the centre of a group is. For matters of cost and an unknown environment, I decided that sensor devices like GPS, LIDAR, depth cameras, etc. were out of the question, and instead the devices should only talk to each other handheld devices using some kind of short range infra-red or radio. As a general rule, computing is cheap, software is cheap, but useful sensors are quite expensive.
In my experience, communication devices make for poor proximity or location sensors. However, we can extract some other useful data from them. Namely, how many connections (or messages) are made within a given time frame. If a device is receiving lots of messages, we could guess that it is within the centre of the group. Importantly, we are not necessarily interested in where the devices are within a space, but in relation to each other. The important trick here is to make sure that that the devices can only communicate within a limited range. If all devices can communicate with each other all the time, then there would be no way to tell which devices is connected to which, and where the inside and outside of the group is. This idea of short range communication is one of the foundations of swarm robotics and self-organising biology.
The AlgorithmAt the time I was also watching some tutorial videos on the Kalman filter, this one in particular, which formed the basis of my approach:
At about 7m52s Student Dave boils the Kalman filter down to a simple equation:
Estimated State = Predicted State + difference between Actual Measurement and the Predicted Measurement
This formula gives us four components which we can rename to our communication based centroid problem. Since we are using how many messages are received within a time frame as our measurement, so we will call this data the message frequency:
- Estimated State : Centroid Probability: At any point in time, we want a device to work out if it is at the centroid of the group and do something (change shape, change colour, make noises, tell the human, ...). This is the result of our equation. Keep in mind that it is derived from the various message frequencies below, so is itself an indication of message frequency.
- Predicted State : Predicted Message Frequency (PrMF): Our device can record previous values to generate a history, and use this to form a prediction of the future state. To make a prediction, there must be a record of previous states. In code, PrMF is created by using a windowed average, meaning that a limited number of recent values are kept to create an average, and older values are eventually discarded.
- Actual Measurement: Actual Message Frequency (AcMF): At any time, a device can count how many messages it has just received, giving an 'actual' reading of how connected it is to other devices.
- Predicted Measurement: Received Message Frequency (ReMF): This forth value is needed as a comparison (the difference in Student Dave's equation). Since we are communicating with other devices at short range, we might as well communicate something useful, and so receive their own readings of message frequency, and use these values as a 'predicted' value to balance our own. To create this value in code, we receive messages from neighbours and average the value. I've coded the simulation so that each device has a maximum number of messages it can receive within one time step.
This means we can re-write the equation to:
Centroid Probability = PrMF + K*( AcMF - ReMF )
Hopefully you spotted the 'K' in there. Student Dave calls this the gain, and sometimes the idea of gain can seem arbitrary. The equation above is essentially a feedback equation, where the difference in message frequency between one device (AcMF) and it's neighbours message frequencies ( ReMF) is being used to adjust a prediction (PrMF). 'K' is therefore a number used to scale, or change the influence, of the difference applied to the prediction.
If 'K' equals zero, then whatever the value of the difference, multiply it by 0 and it equals 0, and will not change the prediction. If 'K' is a positive value, it amplifies the prediction (PrMF) by adding to it, whilst if it is a negative value it dampens the prediction (PrMF) by subtracting from it. So in our case, 'K' will alter the influence of receiving neighbouring devices message frequency values, and so changes how much the handheld devices can inform each other.
Why would we use gain? Gain is used when the performance of a system can vary. In our case, the handheld devices could move around quickly, meaning that they would change their neighbours often and also change their position within the group. The devices might be trapped within a small space and always encounter other devices, or move within a big space and only encounter other devices occasionally. The gain allows for some calibration.
So what?It is quite easy to play with the simulation and find a calibration that seems reasonably good at finding the centroid. The devices move around randomly, trapped within the window. How the devices would actually move under human control is unknown, and probably depends a lot on what the devices do to influence the human. In simulation, the 'a' and 'z' keys can be used to increase or decrease the number of devices. The 's' and 'x' key can be used to change the range at which the devices can communicate. The 'd' and 'c' keys can be used to increase or decrease the gain 'k_influence'.
At any point, a device an be clicked to highlight it in white and a graph will appear to show the history of Centroid Probability for that device.
To make things more interesting, the 'e' key can be used to enable or disable an extra behaviour, which links the speed of movement of the devices to their predicted centroid value, such that they slow down if they believe they are more centroid. The 'r' key can be used to reset the simulation. Using the movement speed helps to discover the effect of changing the gain 'k'.
With the movement speed enabled, a positive 'k' value seems to act like glue, so that the devices will clump up into groups and remain so.
With the movement speed enabled and a negative 'k' value, the devices reduce movement in sweeping and periodic oscillations, clumping up and breaking free:
There are lots of variables to play with, such as the window size (amount of space), the number of devices (the density, related to the amount of space), as well the communication range, movement characteristics and algorithm gain.