Adapting Canonical Particle Swarm Optimization to a Swarm of Kilobots in Event Location Tasks

摘要

In nature, there are many species who are tiny and simple as individuals, but are very organized and effective as a group, for foraging, defense, and other tasks. This phenomenon has inspired the development of swarm robotics, which has been applied from simulating nano-particle based medication administering to controlling hundreds of UAVs in formation for ceremonial display and/or surveillance. This dissertation aims to explore the idea of swarm intelligence, in a search and rescue simulation scenario, to establish a test-bed and to make the idea practical for the control of a swarm of robots. In order to do this efficiently, the robots will have some swarm intelligence method to govern their behavior. One such swarm intelligence method is Particle Swarm Optimization (PSO), originally developed by Kennedy and Eberhart in 1995 as a way of modelling natural swarm behavior. However, canonical PSO presents a challenge in needing to be adapted to limitations of a physical robot swarm. There are several popular options of swarm robots from research groups and many are available for sale at K-team, Seeedstudios, etc. However, these robots are still too expensive to purchase in a large quantity. We chose Kilobot designed by Harvard Self-organizing system research group, the most cost efficient option, yet with a suite of functionality. The team at Western Carolina University has improved/updated the design while building a few dozen of these robots. Therefore, the experimenting agent is set to be Kilobot, and the practical constraints of Kilobots, such as communication range, movement mechanisms, are all taken into account when adapting the idea of PSO for swarm robotic control. To address the issues of limited communication range of Kilobot and measurement noises, we first proposed the Neighborhood PSO (NPSO) algorithm and examined it in the Matlab simulation environment. Three benchmark functions are used to simulate the measurements on the interest level at each location: when there is an emergency event like a fire, the fitness value at that location will be higher than that in its neighboring region (for calculation simplicity, though, the fitness is assumed to be the smaller the better, and the global minima is with a fitness value of 0.) Monte Carlo simulations are carried out given the random nature of the algorithms, and the results are reported in convergence speed, accuracy and consistency. Once NPSO was established as comparable to PSO in Matlab simulations, we adopted the NPSO idea into a more realistic Kilobot simulation environment, Kilombo, in Linux. Kilombo has incorporated many practical aspects of Kilobots, such as its physical size, its moving and turning speed, and its communication channel. The code developed in Kilombo should be portable to Kilobots. In Kilombo, the Kilobots' movements can be sped up saving simulation time. The Kilobots are given the tasks of locating the spot with the best fitness, simulating the search ofan event of interest. The fitness values are provided by the call-back functions when Kilobots inquire such values, simulating their measurements. We then propose a new motion mechanism, called pseudo-vector motion (PVM), inspired by our NPSO algorithm to control the swarm. We have proposed another three PVM-based algorithms subsequently to address the issues that are observed in the Kilombo simulation experiments.