SOFTWARE

We wrote software for the PC in Java to receive signal strength measurements from the computer’s serial port and incorporate the data into the current localization model. Our localization model is a probabilistic technique known as a particle filter, which is described in Sebastian Thrun et al.’s Probabilistic Robotics. Particle filters work by first distributing random samples called particles over the space being observed. Each particle represents a possible physical location in the environment. A probability value is assigned to each particle. This probability represents the likelihood that the robot is at the location specified by the particle.

At each time step, each particle is reevaluated and its probability value is updated according to the ZigBee signal strength measurements. Less likely particles are then redistributed around more likely particles. This is done by building a cumulative sum graph of the normalized probabilities of each particle (see Figure 2). This graph is then randomly sampled to create a histogram that dictates where the particles should be distributed at the next time step. The particles concentrate around locations that have a higher probability of being the robot’s location.

Finally, after the particles have their new coordinates, a small amount of random noise is added to each particle’s location so that they’re distributed around likely locations instead of concentrating at a single point. This helps maintain a small degree of uncertainty in our model and better reflects real-world conditions.

In our project, the localization software reevaluates each particle’s position and probability when the PC receives the signal strength measurements from the computer node. It first performs a simple geometrical computation to convert the measurements into a coordinate pair (xDATA, yDATA) representing the approximate robot location. Because we only had the three ZigBee nodes that came with the Freescale kit to work with, we were not able to perform true triangulation, which requires at least three nodes to triangulate a forth node. Instead, we assumed that the T and C nodes were placed on a wall that the R node couldn’t pass through.

If you were to assume that the signal strength measurements were 100% accurate, the location of the robot would reside at the intersection of two imaginary spheres centered at each of the sensing nodes, with radii proportional to the signal strength. The intersection of these two spheres is a circle that resides in a plane perpendicular to the line connecting the two sensors. If you use the plane of the floor as a constraint, you know that robot must be at one of two points on that circle. Finally, you can eliminate one of these points by putting the two sensors on the same wall and guaranteeing that the robot will always be on the same side of that wall.

On the computer, the coordinate pair (xDATA, yDATA) was averaged over 10 data-consecutive data points before being fed to the particle filter. Averaging helped reduce some of the noise in the data. The particle filter then used 1,000 particles to localize the robot. The probability value for a single particle was determined by plugging the particle’s coordinates (xSAMPLE, ySAMPLE) into a standard Gaussian function based on the xDATA, yDATA point determined by the signal strength measurements. To guess at the robot’s location, we simply took the weighted average of the 1,000 samples.

Photo 2 shows the particle filter running for three consecutive time steps. You can see the rapid convergence of the particles to the area of the robot marked in blue in the center of each picture. As the robot moves in the environment, the signal strength measurements are frequently updated, and the particle filter is updated in real time.