Research
It is said that a picture is worth a thousand words. Above, you can see a picture of words (not a thousand, though) that summarizes my current and past research interests. It was generated automatically by Jonathan Feinberg's wordle applet, which takes a body of text as input, and returns a cloud of words as output. Whether a word appears in the generated image or not, depends on the frequency with which that word appears in the input text. The higher the frequency of a word, the more likely it is that it appears in the generated image.
The image above is the result of counting the frequency of the words that appear in the titles and abstracts of my published papers (as of November 2012). This image beautifully summarizes my current and past research interests.
Swarm Intelligence
The intelligence sometimes exhibited by groups composed of many very simple agents is called swarm intelligence. The main goal of my research is to harness that swarm intelligence for solving practical problems. Meeting this goal is difficult because the collective-level behavior of a group of agents is the result of local interactions between agents and the environment. Thus, it is not possible to design a swarm intelligence system one agent at a time as it is done in traditional multi-agent systems engineering.
I have worked on some of the most popular swarm intelligence techniques: ant-based clustering, ant colony optimization, particle swarm optimization, and swarm robotics.
Ant-based clustering is inspired by the aggregation behaviors exhibited by some termite and ant species. In actual implementations of these algorithms, agents (simulating ants or termites) move over a toroidal square grid on which there are data objects. Agents pick up a data object with high probability if it is not surrounded by other similar data objects. By the same token, agents drop data objects on any free location surrounded by similar objects to the one they are carrying. For more information go to the publications section.
In this figure, you can observe the development of the clustering process as performed by simulated ants. In this example, there are three real clusters that can be identified by differences in color. It can be seen how ants are capable of identifying them correctly. It should be noted that ant-based clustering algorithms do not require the user to specify the number of clusters to retrieve. In some cases, ant based clustering algorithms are capable of identifying the correct number of clusters existing in a data set.
Ant Colony Optimization (ACO) is an optimization metaheuristic inspired by the foraging behavior of ants. It is based on stigmergy which is an indirect kind of communication that happens through the environment. Real ants communicate through chemicals laid on the ground to recruit other members of the colony to exploit a food source. Artificial ants in ACO bias the search of other ants through some kind of stigmergic communication in the search space. ACO has been shown to be a good optimization technique for hard combinatorial optimization problems. For more information go to Marco Dorigo's Ant Colony Optimization page.
Particle Swarm Optimization (PSO) is a continuous optimization technique inspired by social cognition theories and collective behaviors exhibited by some animals such as birds or fish. In PSO, each individual (called a particle) represents a solution to a continuous optimization problem. Associated with each particle, there is a velocity vector that changes according to its own best past performance and that of its neighbors. In this way, particles ``fly'' over a solution space resembling the movement of insects in a swarm. PSO has captured the interest of a growing research community apparently because it is conceptually simple, technically easy to implement, and has been successfully applied to many problems. For more information go to the publications section.
|
|
|
The figure above shows a swarm of 6 particles solving a two-dimensional displaced Rosenbrock's function. The swarm is using a fully connected topology (known as gbest) and the so-called constriction factor (= 0.729). The blue dots show where the particles' previous best positions are (called pbest). The black dots show the particles' current position. It is also shown where the true optimum is located.
Some introductory slides can be found here.
A swarm robotics system is a multi-robot system in which robots coordinate their actions using swarm intelligence principles. For more information go to the publications section.
This video shows the collective decision-making process that results from
the application of the majority-rule opinion dynamics model with differential
latency as described here.
The environment consists of two areas between which the robots must
transport objects collectively. These two areas are at the top and bottom parts
of a video frame. Connecting these two areas there are two corridors of
different length. Each team of robots must choose between these two corridors to
go to the target area. At each decision point, there is an LED that helps robots
know in which direction to turn. For simplcity, objects are removed from the
simulation as soon as they are transported to the target area. Something similar
happens with robots once they go back to the starting area.
In this
example, a population of 32 robots and 8 teams are used. Initially, 16 robots
prefer the left path and 16 robots prefer the right path. Every time a team is
formed (at random), the local majority determines which path the team will
follow. At the end of the simulation the population achieves consensus on the
left path. Note: The speed of the video is 4 times the normal speed of the
simulation.