My current class assignment is to program a robot through a course that includes two moving obstacles – other robots moving at constant speed around a region the one robot must get to. Since the other robots are moving at a constant pace alongside a predictable path, my robot can just stop at the border of the region, wait until the others pass by and then proceed. The robot can use a 2D laser range scanner to sense its surroundings.

Given these restrictions, what is the simplest object tracking algorithm I could use? I am thinking of something along these lines:

  1. Collect two laser readings (2D point clouds) A and B with a suitable time gap between them;
  2. Apply DBSCAN to A and B, producing the cluster lists A' and B';
  3. Generate a list P of pair-wise matches of the clusters in A' and B', maybe using the Hungarian algorithm;
  4. Discard from P any pairings whose difference falls within a threshold;
  5. Calculate direction and magnitude of movements from the distance between the centers of mass of each cluster pair.

The reason for choosing DBSCAN and the Hungarian algorithm is that I already have both implemented and in use elsewhere; and the difference between clusters could be measured as the distance between their centers of mass.

Do you think this solution would work for my problem? Do you have any suggestions on better and/or simpler ways to solve it?

  • $\begingroup$ I just realized I don't need calculate the difference lists, but can instead create the pair-wise matches directly from A' and B', and then discard any matches whose displacement falls below a threshold. $\endgroup$
    – xperroni
    May 2, 2014 at 8:29
  • $\begingroup$ The differences between your clusters can be useful for an estimate of the velocity of your clusters (which represent the other robots, if I understand correctly). I would use this together with the cluster's position as states for a Kalman filter to track the other robots. $\endgroup$ May 3, 2014 at 9:43