【正文】 ecialize in different cleaning tasks, restocking shelves, and even leading customers around the store. One of the hurdles to implementing this kind of robotic team is the problem of localization, which is a key part of any mobile robotic network. Localization is the process of determining the location of nodes within the network as accurately as possible. In this article, we’ll present a ZigBeebased localization solution for estimating a robot’s position.SYSTEM OVERVIEW The ZigBee wireless standard is a pelling platform for implementing an elegant localization method. In addition to being inexpensive and low power, it allows for enough bandwidth for other types of munication, such as mands and tasks for robots within the network. We used a ZigBee evaluation kit from Freescale Semiconductor to implement a proofofconcept network for a WowWee Robosapien , which is a humanoid robot. We implemented the prototype using the kit’s three ZigBee nodes to simultaneously localize the robot with signal strength measurements while controlling it with a minimal mand set. Our localization and control system features a Freescale MC13192 evaluation board with three accelerometers (MMA6261Q for the x and yaxes and MMA126OD for the zaxis) mounted on the Robosapien robot (see Photo 1). The system also includes an MC13192 SARD board connected to a PC via an RS232 serial connector and another MC13192 evaluation board in the environment. Photo 1—Check out the Robosapien . We attached a Freescale ZigBee node to its back so we could control it. Figure 1 shows the nodes attached to the Robosapien. The munications model we used is based on a broadcast model in which the senders and receivers aren’t addressed specifically, but the packets incorporate a basic header describing the kind of data they contain.Figure 1—The ZigBee nodes are labeled R, T, and C. The arrows represent sent packets.LOCALIZATION The localization process is fairly straightforward. The Robosapien node (R) frequently sends out packets containing accelerometer data. Both the puter node (C) and the third node (T) receive the packets. (The accelerometer data isn’t used in this implementation, but we’ll explain it later when we describe some possible improvements to the system.) After a packet is successfully received, a signal strength reading is taken by calling the PLME_link_quality method, which is found in the simple_phy class of the Freescale support code. After the third node has acplished this, it constructs a packet containing the resulting signal strength measurement and sends it to the puter node. At that point, C, which has both the signal strength reading from R/T and R/C, poses a packet with these measurements to be sent via the serial port to the puter. When the puter receives both signal strength measurements, it can begin hypothesizing about the robot’s location. However, this can’t be done with a straightforward geometric calculation because of the uncertainty associated with noisy data and the signal strength’s nonlinearity. This noise is such that if simple distance calculations were applied at each time step, the puter might find that the robot’s location would vary on the order of meters when it is standing still. To deal with this large degree of uncertainty in our data, we used a probabilistic Monte Carlo localization technique to implement a particle filter to localize the robot. Let’s take a look at how the particle filter reduces the uncertainty of the robot’s location.SOFTWARE We wrote software for the PC in Java to receive signal strength measurements from the puter’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.Figure 2—The left graph shows the normalized probability versus robot locations 1 to 10, shown on the xaxis. By randomly sampling the cumulative sum graph (shown in the middle), we puted where the particles should be located given the latest signal strength measurement. The histogram shows that the particles will be relocated mostly in the proximity of locations 5 and 9. The particles are concentrated around the robot’s most likely position. 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 realworld conditions. In our project, the localization software reevaluates each particle’s position and probability when the PC receives the signal strength measurements from the puter node. It first performs a simple geometrical putation 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