The professor or TA can chime in if this technique is flawed.The major efficiency bottleneck in my code (and presumably in most people's code) is doing the raytracing needed to find P(observation|pose, map). It sure would be nice if that value could be precomputed, so that I could just look up in the map the probability of seeing an obstacle at a given location, without raytracing to find the obstacle each time. While studying for the last "quiz" I realized that this is similar to the concept of "configuration space".
The idea is that for each occupied point in the map, determine how likely that point is to be seen at every other point on the map. Since the sensor model is a normal distribution, this just means placing a gaussian bump on the map centered on each occupied cell (for a probabilistic map, scale the gaussian by the probability that the cell is occupied). Since gaussians approach zero pretty quickly, only the cells near the obstacle will actually be significantly affected. Then for each cell in the map, sum the individual contributions from all the (nearby) obstacles, and renormalize. In mathematical terminology, I think what I'm describing is called a convolution of the map with the sensor model. As it turns out, convolving an image with a gaussian is a well-known operation -- it's how you blur an image (The Gimp has a built-in Gaussian Blur filter, for instance).
So what I tried doing is creating a blurred copy of a map (in the Gimp), loading that blurred png into my grid map, and then for each sample's simulated laser beams, I just look into the blurred map to find the probability of seeing an an obstacle at the point where the laser beam stops. No Bresenham's or raytracing is involved!
In my limited testing, this method seemed to work at least as well as the original, and it definitely sped up my program quite a bit (maybe an order of magnitude or more), which meant I could use more samples, and thus be more likely to converge to the correct spot. It was also a lot faster to implement (~1 hour, including the time to blur the image and run a couple tests, compared to the better part of a day spent debugging a faulty Bresenham's algorithm).I only wish I had thought of this before I submitted!
Caveat: This won't perform exactly the same as the raytracing model. Raytracing only considers obstacles on the exact same line as the laser beam. This method considers all the obstacles around the laser beam's end point, including those off to the side. I think this is actually a benefit, because it helps out in the case where a sample pose might be close to the real robot's position but have a slightly different orientation, which might, for example, make it's simulated laser beam shoot past a corner that the robot actually saw.
This method doesn't take into account any obstacles in the map that are between the sample position and the laser beam's end point. Maybe raytracing is needed after all.