It might seem strange to write about probabilities on a blog about programming but bear with me; it will all make sense soon.
We use probabilities a lot in our daily lives without realising it, to the point where they can seem fairly intuitive. This is not the case, probabilities can be very counter-intuitive. A classic example of this would be the Money Hall Problem (you can look that up yourselves). People also tend to feel that if there is a 1-in-10 chance of something happening, then it should happen at some point in the first 10 tries.
This is a misunderstanding of the fact they are independent events. Each time the event occurs, it has a 1-in-10 chance regardless of what has come before. If you roll a regular die, there is a 1-in-6 chance of rolling a 6, what has happened in the past is irrelevant, if you roll 5 times and don’t get a 6, the sixth roll still has a 1-in-6 chance of rolling a 6. There are occasions though, where events are not independent and this is what I’m going to write about.
An example of a dependent event would be during a lottery draw (note, separate draws are independent as the machine is reset each week, you are no more likely to win each week, here I am talking about the balls drawn in a single draw). There are 49 balls in the machine and you have 6 numbers on your ticket. The odds of getting the first number are 1/(49/6) or about 12%. Now however, the odds change for the second number. There are now only 48 balls in the machine and 5 left on your ticket. These are the dependant events. The odds of getting the second number are 1/(48/5). This continues over the whole ticket. To get the odds of winning the jackpot, we must multiple all these odds together. 1/ (49/6*48/5*47/4*46/3*45/2*44) or 1/13,983,816.
To bring this back on topic, it could seem strange to use probabilities in software since software is generally thought of to be deterministic. If you provide identical input, it will produce identical output. The idea of using probabilities might seem to contradict that, however there are cases where trying to calculate something precisely is impossible or at least computationally inefficient.
The specific case we will look at is that of sensor analysis. Previously I have written about path finding algorithms. These assume that you have a map of the world already. What if you want to build that map? You need some sort of sensor that can see the world. Typically, a sonar sensor can be used to detect walls and obstacles. Ultrasonic sound waves are bounced off the target and timed how long they take to return to calculate the distance to the target. Distance = (time * speed of sound) / 2.
There are problems with sonar analysis though, it will have a margin for error and the sound travels in a cone, the response could come from anywhere in that cone.
Here, R represents the maximum range of the sensor and theta is the field of view. To compensate for this, we must first split our environment into nodes. Just like in the path finding problem, a square grid is simplest. We must then assume that any node intersecting the cone could be the target the sonar has detected. It is mostly like however, that the response is directly in front of the sensor and closer to the sensor rather than further away. It is worth noting some sensors have a minimum distance they can detect.
To handle this cone, we must analyse all of the nodes that are within it. We need to calculate a probability of the sensor’s accuracy, given that the node is occupied, P(s|O). We don’t know if it is occupied at the moment but that doesn’t matter for now.
Where R is the maximum range of the sensor and Beta is the field of view of the sensor. For every node we can calculate the vector to from the sensors position and using the dot product we can calculate the angle between the sensor and the node. By taking the ratio of the node’s distance and angle to the maximum of the sensor we can calculate a value between 0 and 1 in order to determine a probability for the sensors accuracy of detecting the occupancy of a given node.
Stage 1 of the included code demonstrates this part of the calculation.
In this image, the shading of the squares represents the P(s|O) with white being 1.0 and black being 0.0.
Now that we can handle the accuracy of the sensor, we need a model for how we are going to interpret the results. The response we get will be a scalar value representing the distance to the obstacle.
From this we can calculate the region that the response could have come from. This is Region I in the diagram. This region is centred on the reading from the sensor and extends by the error margin in either direction. Region II represents the area closer than the reading. If this region were occupied, we would have gotten a response from there instead so we can assume that it is clear and update the nodes in this region accordingly. We cannot just set these nodes to 0.0, we use the function for P(s|O) from the previous section as the probability it is empty rather than occupied, P(s|E), then P(s|O) = 1.0 – P(s|E). Region III is further away than the obstacle so we cannot see it. As such, we should not update these nodes at all.
Finally, we need to bring it all together. We can use Baye’s Theorem of conditional probabilities to calculate P(O|s) for each node. We can also use a variant of this to aggregate multiple readings of the same node and further improve the accuracy of the map. The final formula we use is:
This allows us to aggregate previous readings with P(O|sn-1). We just need an initial value for this before the first reading. We can just set this to 0.5.
With this model we will never get probabilities of 1.0 and 0.0 for a node, so thresholds would need to be defined to determine if a node should be considered empty or occupied.
Stage 2 of the attached code attempts to model this; however I wasn’t going to try to simulate an ultrasonic sensor so you can just type in values for the sensor. I’m sure you can easily mess it up with contradictory readings but if you are fairly consistent, it should show it working quite well.
The code can be found at https://github.com/a-jackson/bayesian-sensor-analysis. It is by no means perfect, especially in stage 2, but I think it gets the point across.