Automatic Mutual Localization of Swarm Robot Using a Particle Filter
 Author: Lee YangWeon
 Organization: Lee YangWeon
 Publish: Journal of information and communication convergence engineering Volume 10, Issue4, p390~395, 31 Dec 2012

ABSTRACT
This paper describes an implementation of automatic mutual localization of swarm robots using a particle filter. Each robot determines the location of the other robots using wireless sensors. The measured data will be used for determination of the movement method of the robot itself. It also affects the other robots’ selfarrangement into formations such as circles and lines. We discuss the problem of a circle formation enclosing a target that moves. This method is the solution for enclosing an invader in a circle formation based on mutual localization of the multirobot without infrastructure. We use trilateration, which does require knowing the value of the coordinates of the reference points. Therefore, specifying the enclosure point based on the number of robots and their relative positions in the coordinate system. A particle filter is used to improve the accuracy of the robot’s location. The particle filter is operates better for mutual location of robots than any other estimation algorithms. Through the experiments, we show that the proposed scheme is stable and works well in real environments.

KEYWORD
Particle filter , Swarm robot , Tracking

I. INTRODUCTION
Swarm robotics is an approach to robotics that emphasizes the use of many simple robots instead of a single complex robot. A robot swarm has much in common with an ant colony or swarm of bees. No individual in the group is very intelligent or complex, but combined, they can perform difficult tasks. Swarm robotics has been an experimental field, but many practical applications have been proposed. A traditional robot often needs complex components and significant computer processing power to accomplish its assigned tasks. In swarm robotics, each robot is relatively simple and inexpensive. As a group, these simple machines cooperate to perform advanced tasks that otherwise would require a more powerful, more expensive robot. Using many simple robots has other advantages as well. Robot swarms have high fault tolerance, meaning that they still will perform well if some of the individual units malfunction or are destroyed. Swarms also are scalable, so the size of the swarm can be increased or decreased as needed.
Before a project using multiple robots is begun, the types of robots that will be used should be identified and classified because this will affect numerous elements such as the control algorithm, obstacle avoidance, communication. To accomplish given specific tasks, the system is concerned with the ability to cooperate, as shown in Fig. 1.
Mobile robot localization is a problem of determining the posture of a robot relative to a given map of an environment, and establishing correspondence between the map coordinate system and the robot’s local coordinate system.
A Bayesian filter is a general method applicable to this problem that recursively estimates the robot’s belief about its current position. An extended Kalman Filter [1], an estimation algorithm adopting the Bayesian filter as its foundation, provides an efficient method for representing the positional belief of a robot with a Gaussian distribution. Many robotic applications require that robots work in collaboration [2] in order to perform a certain task [3].
In this paper, we present a particle filter localization system for multiple cooperative robots in an environment where they can move automatically as a group and extract position information in a given map of the environment from stationary landmarks. For assessment of the system, we consider a scenario where some robots cannot detect landmarks. In this case, uncertainty in position estimates for all robots is expected to increase. We suppose that each mobile robot in the environment not only can detect and calculate the distance to the other robots, but also can share its position information with the other robots. Consequently, each mobile robot acts as an additional mobile landmark. However, this can introduce some degree of error to the position information from stationary landmarks, and localization could become unstable. Still, we desire selflocalization performed by each robot to be improved by extra position information from the other robots. For example, in Fig. 2, the localization error will be high when a robot cannot detect landmarks. However, if a robot can detect other robots as new landmarks and utilize their position information, the robot may see increased opportunities for better localization. When a robot determines the location of another robot relative to its own, both robots refine their internal beliefs based on the other robot’s estimate, hence improving selflocalization accuracy on both sides [4]. In our research, each robot used an omnidirectional camera as a range finder sensor to detect other robots and landmarks. The sensor can measure the range, bearing, and signature of a landmark relative to the robot local coordinate.
As a characteristic of the omnidirectional camera, objects are displayed radially in its image; a neartofar layout in real space is transformed into a center layout in the camera image space.
Fig. 2 shows an example omnidirectional image. This characteristic constrains the analytical ability of the camera because the noise distribution in the camera image space distance is transformed nonlinearly and variably from the real space distance. In order to investigate the noise distribution of the omnidirectional camera, we assume the input noise distribution is a Gaussian distribution and try to obtain the output noise distribution according to the geometry of hyperboloid projection.
II. LOCALIZATION ALGORITHM
Localization is the process of finding both position and orientation of a vehicle in a given referential system [57]. Navigation of mobile robots indoors usually requires accurate and reliable methods of localization. Many transportation systems now using wireguided automated vehicles may benefit from the increased layout design flexibility provided by a wirefree localization method such as triangulation with active beacons.
> A. Triangulation
Triangulation is based on the measurement of the bearings of the robot relative to beacons placed in known positions. It differs from trilateration, which is based on the measurement of the distances between the robot and the beacons. These beacons are also called landmarks by some authors. According to [8], the term beacon is more appropriate for triangulation methods. When navigating on a plane, three distinguishable beacons (at least) are required for the robot to localize itself (Fig. 3). λ_{12} is the oriented angle “seen” by the robot between beacons 1 and 2.
It defines an arc between these beacons, which is a set of possible positions of the robot. An additional arc between beacons 1 and 3 is defined by λ_{31}. The robot is in the intersection of the two arcs. Usually, the use of more than three beacons results in redundancy.
> B. Trilateration
Trilateration is a method to determine the position of an object based on simultaneous range measurements from three stations located at known sites. This is a common operation not only in robot localization [9], but also in kinematics, aeronautics, crystallography, and computer graphics. It can be trivially expressed as the problem of finding the intersection of three spheres, that is, finding the solutions to the following system of quadratic equations:
where,
x _{1},x _{2},x _{3} are the coordinates of the station,i andl_{i} is the range measurement associated with it.In Fig. 4, thick segments between stations define the base plane, and thin ones, those connecting the moving object and the stations, correspond to the range measurements.
> C. Bounding Box
The bounding box method uses a simple boxshaped ranging area, as shown in Fig. 3, which can be specified by the extreme lower left coordinates, (x^{l}, y^{l}), and extreme upper right coordinates, (x^{u}, y^{u}). Fig. 5 shows an example where node
i is bounded by the ranging area of its neighbors, nodes 1, 2, and 3. Thus, the bounding area for nodei can be specified as follows:The bounding box method can be implemented as a distributed algorithm; Simic and Sastry [10] suggest that anchors broadcast their respective position estimates periodically, and nodes broadcast any changes in their estimates
upon reception of any broadcast.
III. TRACKING ALGORITHM
> A. Particle Filter Algorithms
The particle filter approach to track motion, also known as the condensation algorithm [11] and Monte Carlo localization, uses a large number of particles to ‘explore’ the state space. Each particle represents a hypothesized target location in state space. Initially, the particles are uniformly randomly distributed across the state space, and for each subsequent frame, the algorithm cycles through the steps illustrated in Fig. 6:
1. Deterministic drift: particles are moved according to a deterministic motion model (a damped constant velocity motion model was used).
2. Update probability density function (PDF): determine the probability for every new particle location.
3. Resample particles: 90% of the particles are resampled with replacement, such that the probability of choosing a particular sample is equal to the PDF at that point; the remaining 10% of particles are distributed randomly throughout the state space.
4. Diffuse particles: particles are moved a small distance in state space under Brownian motion.
This results in particles congregating in regions of high probability and dispersing from other regions; thus the particle density indicates the most likely target states. See [2] for a comprehensive discussion of this method. The key strengths of the particle filter approach to localization and tracking are its scalability (the computational requirement varies linearly with the number of particles), and its ability to deal with multiple hypotheses (and thus more readily recover from tracking errors). However, the particle filter was applied here for several additional reasons:
？ It provides an efficient means of searching for a target in a multidimensional state space.
？ It reduces the search problem to a verification problem, i.e., is a given hypothesis facelike according to the sensor information?
？ It allows the fusion of cues running at different frequencies.
> B. Application of Particle Filter for MultiRobots
In order to apply the particle filter algorithm to hand motion recognition, we extend the methods described by Huang [5]. Specifically, a state at time t is described as a parameter vector: s^{t} = (μ, ？^{i}, α^{i}, ρ^{i}) where μ is the integer index of the predictive model, ？^{i} indicates the current position in the model, α^{i} refers to an amplitude scaling factor and ρ^{i} is a scale factor in the time dimension.
1) Initialization
The sample set is initialized with N samples distributed over possible starting states and each assigned a weight of
Specifically, the initial parameters are picked uniformly according to:
2) Prediction
In the prediction step, each parameter of a randomly sampled s_{t} is used with s_{t+1} determined based on the parameters of that particular st . Each old state, s_{t}, is randomly chosen from the sample set, based on the weight of each sample. That is, the weight of each sample determines the probability of its being chosen. This is done efficiently by creating a cumulative probability table, choosing a uniform random number on [0,1], and then using binary search to pull out a sample [12]. The following equations are used to choose the new state:
where
N (σ_{*}) refers to a number chosen randomly according to the normal distribution with standard deviation σ_{*}. This adds an element of uncertainty to each prediction, which keeps the sample set diffuse enough to deal with noisy data. For a given drawn sample, predictions are generated until all of the parameters are within the accepted range. If, after, a set number of attempts it is still impossible to generate a valid prediction, a new sample is created according to the initialization procedure above.3) Updating
After the prediction step above, there exists a new set of N predicted samples that need to be assigned weights. The weight of each sample is a measure of its likelihood given the observed data Z_{t} = (z_{t}, z_{t,1},…). We define Z_{t,i} =(z_{t,i}, z_{(ti)},_{i},…) as a sequence of observations for the
i ^{th} coefficient over time; specifically, let Z_{(t,1)}, Z_{(t,2)}, Z_{(t,3)}, Z_{(t,4)} be the sequence of observations of the horizontal velocity of the left robot, the vertical velocity of the left robot, the horizontal velocity of the right robot, and the vertical velocity of the right robot, respectively. Extending Black and Jepson, we then calculate the weight by the following equation:where ω is the size of a temporal window that spans back in time. Note that
Φ ^{*},α ^{*} andρ ^{*} refer to the appropriate parameters of the model for the group of robots in question and thatrefers to the value given to the
i ^{th} coefficient of the model μ interpolated at timeΦ ^{*} ？ρ ^{*}j and scaled byα ^{*}.IV. EXPERIMENTAL RESULTS
To test the proposed particle filter scheme, we used MATLAB (MathWorks, Natick, MA, USA) and Visual Studio (Micosoft, Redmond, WA, USA). MATLAB was used for simulation of the particle filter and Visual Studio was used to calculate the mutual localization of the intruder and robot. Through the experiment, we confirmed that the accuracy of robot localization using the particle filter is greater than localization using only sensor information. Therefore, it is necessary to use the particle filter to localize the robot when there is no information except triangular measurement data. This is shown in Figs. 7 and 8.
Also, we evaluate the algorithm of intruder enclosure formation using trilateration. First of all, we assume that initially there are 6 robots and repeat the experiment while swapping each robot’s position with that of the intruder. Figs. 9 and 10 show the robots making a circle formation to enclose the intruder.
> V. CONSLUSIONS
In this paper, we have developed the particle filter for swarm robot localization and circle formation enclosing a target that moves. This method encloses the invader in a circle formation based on mutual localization of the swarm robots without infrastructure. Therefore, we use trilateration, which does not require knowing the value of the coordinates of the reference points. We specify the enclosure point for the number of robots based on the relative positions of the robots in the coordinate system.
This scheme is important in providing a computationally feasible alternative for classifying the robot motion in a real system. We have proven that given an environment, a particle filter scheme classifies the robot location in real time.

[Fig. 1 .] Taxonomy of multirobot system.

[Fig. 2.] Robots and landmarks.

[Fig. 3.] Threeobject triangulation.

[Fig. 4.] Threeobject triangulation.

[Fig. 5.] Bounding box.

[Fig. 6.] Process of particle filter calculation.

[Fig. 7.] Result 1 of experiment by particle filter.

[Fig. 8.] Result 2 of experiment by particle filter.

[Fig. 9.] Initial position of robot and intruder.

[Fig. 10.] Result of intruder enclosing experiment.