Computer Science 154
Short assignment 7
Due Monday., Apr. 21 in class

Name(s)  _____________________________________

Reading for this assignment, linked here:
Monte Carlo Localization for Mobile Robots
by Dellaert, Fox, Burgard, and Thrun.

1.    Reminder: The final write-up for the final Lab Project is due on Monday, April 28.
   
   
   
2.    Also: Some of Wednesday, April 30 will be used to demo each groups' robotic systems to the class.
   
   
   
3.    Due Monday, April 21 Monte Carlo Localization (MCL)    50 points

   For a robust and widely-used robot algorithm, MCL is one of the easiest to implement. However, that is not to say that there aren't pitfalls and insight to be gained from trying out this probabilistic approach to global robot localization. This assignment asks you to do just that using the Nomad simulator.

   The Task Starting with the files in /cs/cs154/as/mcl, implement a Monte Carlo Localization algorithm for the Nomad robot. There are a number of simplifying assumptions you may make:
   
   

   • The robot's sensors will never rotate. Note that the robot can rotate, but leave its sensors in place because the turret and the synchrodrive's wheels turn independently.
     
     This is important, because it means that the configuration space of the robot is two-dimensional, instead of 3d.
   
   
   
   • The obstacles in the environment will always be rectangular and will always have walls parallel to either the x- or y-axes in which the robot's location is specified.
     
     This is helpful, because it simplifies reasoning about those obstacles. So does the next simplification:
   
   
   
   • The only sensor readings that you need to incorporate are the four values of the sonars pointing in the x and y directions (there are 4 because they point in both positive and negative directions along the x and y axes).
   
   
   

   The starting files The initial files offer some code to help get you started with programming MCL. You may remove or replace anything you like, but if you choose to use the code there, it provides
   
   

   • Particle and Wall classes useful for representing possible robot locations and the environment, respectively.
   
   
   
   • There are also a number of (global) functions:
     
     
     • loadMap which reads in a map file created in the Nomad simulator and stores the walls in a vector of Wall objects.
     • drawParticles for displaying a vector of particles (position hypotheses) in the simulator
     • moveParticles which moves each particle according to some delta_x and delta_y values specified
     • gaussianPDF which determines how likely it is that a particular (sensed) value would come from a normal distribution with a particular mean and standard deviation.
     • gaussrand a generator of normally-distributed random numbers
     • clearance, whichdetermines the distance from a particle to a wall
   
   
   
   • There are several constants that are read in from the parameters file:
     
     
     • PARTICLE_RADIUS, which is used in drawing each particle
     • NPART, the number of particles used
     • NOISE, which is the actual added sensor noise (one standard deviation)
     • NOISE_MODEL, which is the estimated sensor noise (one standard deviation)
     • POS_STDEV_FRAC, which is the fraction of the robot's motion that constitutes one standard deviation of the gaussian noise assumed in the encoderses
     
     
     
   • The classes Timing and KbdInput are also present, as they were for the previous (control) Nomad assignment.
   
   
   

   Suggested functions: You may want to create some or all of these four functions in implementing MCL:

   • initialParticles, which could handle a variety of particle- initialization strategies. In particular, I would suggest (1) first testing with a set of particles just around the robot's initial location, then (2) creating a uniform distribution of particles through the available environment.
   • particleCheck, which would see if a particle passed through an obstacle, when moved according to the robot's perceived motion
   • normalize, which would ensure the weights given to each particle sum to 1 after they're updated according to sensor agreement
   • resample, which would create a new set of particles, equally weighted, from a nonuniform distribution that had just been normalized...
   
   
   
   

   To hand in Hand in the your either via email or by creating a web page with at least three screen shots of your particle-filter localizer in action, both in the simple rectangular environment (mclmap1) and in the maze (maze1). Include a paragraph or two with

   • any difficulties you encountered
   • any drawbacks you found in the MCL algorithm
   • the effect of changing the noise in the sensors/encoders/model
   • how much noise is required to foil your MCL implementation
   • how much noise is needed for MCL to work at all