Scenario Setting<\/h1>\n\n\n\n
Assume we are agents of the avengers<\/a> located in ‘chessboard’ country (that is because the map of this country is like a chessboard \ud83d\ude42 ). One day Thanos came to this country and said he steal our magic stone and then he just left away and hid somewhere in our city.<\/p>\n\n\n\n Our aim: we are told to trace him before the avengers came.<\/strong> <\/p>\n\n\n\n Luckily, we have three clever dogs named ‘particle A’, ‘particle B’, and ‘particle C’. They have already remembered the smell of Thanos! And we are also clever enough to communicate with them. <\/p>\n\n\n\n Every 10 minutes, they could go head 1 grid in the map based on their own ideas. And then our dogs have to report their location and how likely Thanos come across these areas. <\/p>\n\n\n\n At the beginning, particle B said it is 90% sure there is Thanos’scent. So we think at the beginning Thanos are more likely to go across the middle way. <\/p>\n\n\n\n After 10 minutes, our dog moved to new locations and reported their location and their findings. Thanos seems go up from the middle way. as Particle A was 60% sure. <\/p>\n\n\n\n At T=70, we report the most likely route to the avengers (blue line in the figure) based on our three dogs findings. We traced Thanos very well at the beginning. But after T=40, we are far away from his real trace! Finally, our task failed, the avengers could not find him, and he destroyed our world at the end! <\/p>\n\n\n\n Why are we failed? Our dogs are clever, and we are clever. Wait! We track his route very well initially, but after time = 40, particle B and particle C always explore the bottom area. Particle B and particle C said they are not sure Thanos came here, but particle A always said he smelled Thanos’ scent. So we could only rely on Particle A. That’s why we sure Thanos go as particle A’s route.<\/p>\n<\/div>\n<\/div>\n\n\n\n Particle filter without resampling<\/p>The example above illustrates the principle of particle filter without resampling. Each time step, several particles will move follows the transition distribution (like our dogs follow their mind to go head). And based on the evidence (scent of Thanos in our case), we could get the possible location at each time step. Along the time, we could get a trace. However, particle filter without resampling always fails in the long run due to weight degeneracy that the trace is concluded from few particles (In our example, this means we only rely on Particle A after T=40). <\/cite><\/blockquote>\n\n\n\n Okay, so now the avengers make the time back and we could search again. Particle B and Particle C always explore the locations in the right-bottom corner where Thanos obviously not been there. So let them find those locations is a waste. <\/p>\n\n\n\n New rule: If one of the dogs found Thanos most likely came across their area, we introduce a new dog in this area to pinpoint search. Additionally, if a dog has the least amount of certainty, we remove this dog.<\/strong><\/p>\n\n\n\n Particle B is 90% sure while Particle C is only 2% sure. So we move particle C and give one more dog on the area where Particle B is. <\/p>\n\n\n\n Next, our particles remove follow their mind. Since Particle A is 60% sure it smelled Thanos, we introduce a new dog in its area. Since Particle C in the bottom grid only 5% sure it smelled Thanos, we discard it and let it go back home.<\/p>\n\n\n\n As we see, at time 70 we successfully trace Thanos, and we save the world!<\/p>\n\n\n\n Particle filter with resampling<\/p>Due to the limitation of particle filter without sampling, we introduce the resampling scheme in the process. It is easy to understand as we duplicate particles when they have a high probability of getting the right path (like introducing a new dog in that area). In addition, we discard those particles with less probability to find the true path.<\/cite><\/blockquote>\n\n\n\n This is the intuitive idea behind particle filter! Now you could understand the whole process of particle filter! <\/p>\n\n\n\n For more reading:<\/p>\n\n\n\n![\"The](\"https:\/\/sm.mashable.com\/t\/mashable_sea\/feature\/t\/the-thanos\/the-thanos-snap-for-real-lets-remove-humans-from-half-of-ear_bq2q.h720.jpg\")
How to find him?<\/h1>\n\n\n\n
Time=0 minutes<\/h3>\n\n\n\n
![\"\"](\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/ziyang-yang\/wp-content\/uploads\/sites\/18\/2021\/04\/image-14.png\")
<\/figure><\/div>\n\n\n\nTime=10 minutes<\/h2>\n\n\n\n
![\"\"](\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/ziyang-yang\/wp-content\/uploads\/sites\/18\/2021\/04\/image-8.png\")
<\/figure><\/div>\n\n\n\nTime=70 minutes<\/h2>\n\n\n\n
![\"\"](\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/ziyang-yang\/wp-content\/uploads\/sites\/18\/2021\/04\/image-9.png\")
![\"\"](\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/ziyang-yang\/wp-content\/uploads\/sites\/18\/2021\/04\/sfsfsfsfsfsf.gif\")
<\/figure>\n<\/div>\n\n\n\nTime goes back<\/h2>\n\n\n\n
Time = 0 minutes<\/h2>\n\n\n\n
![\"\"](\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/ziyang-yang\/wp-content\/uploads\/sites\/18\/2021\/04\/image-13.png\")
<\/figure><\/div>\n\n\n\nTime = 10 minutes<\/h2>\n\n\n\n
![\"\"](\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/ziyang-yang\/wp-content\/uploads\/sites\/18\/2021\/04\/image-11.png\")
<\/figure><\/div>\n\n\n\nTime = 70 minutes<\/h2>\n\n\n\n
![\"\"](\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/ziyang-yang\/wp-content\/uploads\/sites\/18\/2021\/04\/image-10.png\")
<\/figure><\/div>\n\n\n\n![\"14](\"https:\/\/images2.minutemediacdn.com\/image\/upload\/c_fill,g_auto,h_1248,w_2220\/v1555921064\/shape\/mentalfloss\/spongebob_0_0.jpg?itok=FF47w3bl\")
<\/figure><\/div>\n\n\n\n