Message Boards Message Boards

The puzzled ant and particle filter


The notion of particles filters

The idea I would like to share today is borrowed from a quiz question from Udacity's "Introduction to Computer Vision" course. Although the question is a simple one, the notion built around it highlights the importance of "particle filters". Particle filters - like Kalman filter - is a filtering technique that is utilized to better localize a signal using a prediction (from a model) and measured observation. However, in contrast to the Kalman filter, the solution is not acquired analytically/numerically but via the use of discrete particles. The signal can be N-Dimensional and the number of particles scale accordingly.

One use of particle filters can be to track objects. The usage of particles will assume a knowledge of a prior distribution (created from a model or hypothesis). The prediction is basically a vague but reasonable attempt to localize the object. A given number of particles are created and sampled from the prior distribution. Thereafter, a measured observation - a measure of how likely it is to get the measurement value given the object is at that point - is used to re-weight the particles. The time is advanced, particles displaced and the cycle continues.

Now about the puzzled ant

The question deals with an ant roaming on a rectangular grid of cell coloured either black or white. The ant knows the map, however, has lost track of its current location. We can create a very simple particle filter for such a case to narrow down the possible locations where the ant might be. The only information the ant has is an account of the directions it has turned so far and the colour observed along the way.

The iterative scheme - implemented using particle filters - to solve the problem is a simple one: 1. we start by assuming that the ant is everywhere, its location being tracked by individual particles distributed ubiquitously in the grid. 2. the ants motion displaces the particles along the direction of motion. 3. the particles which move outside the map or those that do not correspond to the observed colour after each motion step are discarded.

Information at hand

Below is the map over which the ant moves

enter image description here

Our ant being a computer science ant (as the authors state) can only moves up, down, right and left. The information the ant has about its motion is as follow:

moved "up" observed white tile

moved "left" observed black tile

moved "up" twice and each time observed a white tile

moved "right" observed a black tile

currently on a white tile

The code to solve the problem was implemented as follows:

antimage = Import[""]
matrix = Table[{i, j}, {i, 7}, {j, 7}];
indices = Flatten[matrix, 1];
matrix[[All, All]] = "Ant";
blackpos = {{1, 7}, ## & @@ Thread[{2, Range[2, 6, 2]}], {4, 2}, {4, 3}, {4, 5}, {4, 6},
## & @@ Thread[{6, Range[2, 6, 2]}], {7, 1}};
whitepos = Complement[indices, blackpos];
s = SparseArray[Join[Thread[whitepos -> 1], Thread[blackpos -> 0]]];

func[grid_, {obs_, move_}] := Module[{tempg, posAntOld, posAntNew},
  If[obs == 1, tempg = ReplacePart[grid, blackpos -> 0],
   tempg = ReplacePart[grid, whitepos -> 0]];
  posAntOld = Position[tempg, "Ant"];
  Switch[move, "up", tempg = Join[Rest@tempg, {ConstantArray[0, 7]}],
   tempg = Insert[tempg[[All, 2 ;;]] // Transpose, 
      ConstantArray[0, 7], -1] // Transpose,
   Insert[tempg[[All, ;; -2]] // Transpose, ConstantArray[0, 7], 1] //
   "down", tempg = Prepend[Most@tempg, {ConstantArray[0, 7]}],
   Null, tempg]

the function is called iteratively

sol = FoldList[func, matrix, Thread[{{1, 0, 1, 1, 0, 1}, {"up", "left", "up", "up", "right", Null}}]];
list = Map[Inset[antimage, # - 0.75, # + 0.75, 0.5] & /@ Position[#, "Ant"] &, sol];
seq = Rotate[ArrayPlot[Transpose@s, ColorRules -> {1 -> White, 0 -> Black}, Mesh -> All, Epilog -> #,
DataReversed -> {True, False}], -Pi/2] & /@ list;

GraphicsRow[seq, ImageSize -> Full]

the evolution of the system can be seen below: enter image description here

A zoomed in version of the initial and final state:

enter image description here

As is evident from the last grid on the right, we are left with just two possible tiles of which one is where the ant can possibly be. Both locations are equally valid. We can find out the paths that the ant could take from the start to reach either destinations.

backtrackRule = {"up" -> "down", "left" -> "right", "right" -> "left", "down" -> "up"};
backtrackValRule = Dispatch[{"down" -> {1, 0}, "up" -> {-1, 0}, "right" -> {0, 1}, "left" -> {0, -1}}];
backtrackpos = Reverse@{"up", "left", "up", "up", "right"} /. backtrackRule /. backtrackValRule;

backtracksol = FoldList[#1 + #2 &, #, backtrackpos] & /@ {{2, 5}, {4, 4}}; (*where the two pts are the possible destinations*)

Rotate[Show[ListPlot[indices, Axes -> False, PlotStyle -> Black, AspectRatio -> 1], Graphics[{{{Thick, Line@backtracksol[[1]]},
{Blue, Thick, Line@backtracksol[[2]]}}, {Darker@Green, PointSize[Large], Point[{{2, 5}, {4, 4}}]}, 
{Darker@Red, PointSize[Large], Point[Last[{##}] & @@@ backtracksol]}}]], -Pi/2]

possible paths:

enter image description here

In near future, I aspire to implement a probabilistic approach to track multiple fluorescent particles in cells - possibly a pseudocode by Godinez et al.

POSTED BY: Ali Hashmi
1 month ago

Thanks for sharing!

POSTED BY: Sander Huisman
1 month ago

Thanks Sander !

POSTED BY: Ali Hashmi
1 month ago

enter image description here - Congratulations! This post is now a Staff Pick! Thank you for your wonderful contributions. Please, keep them coming!

POSTED BY: Moderation Team
1 month ago

Group Abstract Group Abstract