Bank Robbery
Jul. 4th, 2021 07:27 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sassa_nfThe problem is here:
https://gist.github.com/mboes/040b60baa2b0e24ce668b6171db909c5
The discussion is here:
https://juan-gandhi.dreamwidth.org/5035606.html
Basically, we have a map of detectors, and need to find a path from the middle of the bottom to the middle of the top of the square with minimal probability of detection. Each detector's probability of detection along 1 metre of path is a function of distance:
exp(-(π * D / L)2)
It is a little unclear in the problem description what this means. Our discussion indicates it probably means that if you travel along an arc at the same distance D from the detector, the detector will detect with that probability.
The expression doesn't immediately look like Poisson distribution, so we make some assumptions about the meaning of the probability of detection. We can make some sense of it, if this is the probability of being detected at least once. But to solve the problem, we need the probability of non-detection, which we get like this:
From assumption that this is Poisson distribution, the probability of non-detection is:
exp(-lambda) = 1 - P(probability of detection at least once)
So we can compute: exp(-lambda) = 1 - exp(-(π * D / L)2)
Then the probability of non-detection along a small dx of the path is exp(-lambda * dx). If we choose dx to be very small, we can assume that we are moving along a small arc, and the D remains constant.
Then the probability of non-detection by any of the detectors is the product of such probabilities, and the probability of non-detection along the entire path is one more level of products. Instead of exponentiating and computing products, we can take a logarithm, and work with sums. The nice property is that for the entire space split into small cells of size dx, dx is going to be a common multiplier for all exponents, so to maximize non-detection we just maximize the sum.
...Well...The path for the example they gave in the task is (a thin blue line hugging the walls)
and the probability of non-detection along that path is a disappointing 2.0579149322612266e-10. That is, the probability of detection rounded to 3 decimal spaces is 1.
This is just a plain vanilla shortest path search, nothing special.
Let's try a different map, with a different granularity of field segmentation:
Ok, the probability of non-detection here is 0.0009705424368886009. At least we have something to round to 3 decimal places.
And some other example:
- the probability of non-detection is 2.183124560182765e-14
Unless I made some foolish mistake in the computation, the detectors in this problem are much more reliable than perhaps the others may think.
https://gist.github.com/mboes/040b60baa2b0e24ce668b6171db909c5
The discussion is here:
https://juan-gandhi.dreamwidth.org/5035606.html
Basically, we have a map of detectors, and need to find a path from the middle of the bottom to the middle of the top of the square with minimal probability of detection. Each detector's probability of detection along 1 metre of path is a function of distance:
exp(-(π * D / L)2)
It is a little unclear in the problem description what this means. Our discussion indicates it probably means that if you travel along an arc at the same distance D from the detector, the detector will detect with that probability.
The expression doesn't immediately look like Poisson distribution, so we make some assumptions about the meaning of the probability of detection. We can make some sense of it, if this is the probability of being detected at least once. But to solve the problem, we need the probability of non-detection, which we get like this:
From assumption that this is Poisson distribution, the probability of non-detection is:
exp(-lambda) = 1 - P(probability of detection at least once)
So we can compute: exp(-lambda) = 1 - exp(-(π * D / L)2)
Then the probability of non-detection along a small dx of the path is exp(-lambda * dx). If we choose dx to be very small, we can assume that we are moving along a small arc, and the D remains constant.
Then the probability of non-detection by any of the detectors is the product of such probabilities, and the probability of non-detection along the entire path is one more level of products. Instead of exponentiating and computing products, we can take a logarithm, and work with sums. The nice property is that for the entire space split into small cells of size dx, dx is going to be a common multiplier for all exponents, so to maximize non-detection we just maximize the sum.
...Well...The path for the example they gave in the task is (a thin blue line hugging the walls)
and the probability of non-detection along that path is a disappointing 2.0579149322612266e-10. That is, the probability of detection rounded to 3 decimal spaces is 1.
This is just a plain vanilla shortest path search, nothing special.
Let's try a different map, with a different granularity of field segmentation:
Ok, the probability of non-detection here is 0.0009705424368886009. At least we have something to round to 3 decimal places.
And some other example:
- the probability of non-detection is 2.183124560182765e-14
Unless I made some foolish mistake in the computation, the detectors in this problem are much more reliable than perhaps the others may think.
no subject
Date: 2021-07-05 06:41 am (UTC)Oh, you did it! I was too crazy busy with my categories, keeping this prob in the background - while you did not bother to even draw pictures! Thanks!
no subject
Date: 2021-07-06 12:46 pm (UTC)Я пытался эту задачку потыкать, но тоже уперся в то, что детекторы слишком мощные, надо очень далеко их обходить, столько места на карте нет.
no subject
Date: 2021-07-06 03:42 pm (UTC)I kind of blame them for not solving it correctly. :) There are ways to do it wrong, say, add probabilities ("detected on segment X" "or" "detected on segment Y"), or scale by dividing probabilities by size of segment instead of taking N-th root.