Monday, 4th September 200608:30-19:00 Registration
09:30-11:00 Ant Colony Optimization: An Introduction (Room A)
This tutorial will cover the basics of ant colony optimization: from the biological inspiration to the full-fledged metaheuristic. This is an introductory tutorial intended for newcomers to the field.
09:30-11:00 Ant Colony Optimization and its application to adaptive routing in telecommunication networks (Room B)
Gianni Di Caro
11:00-11:30 Coffee Break
11:30-13:00 Introduction to Particle Swarm Optimization (Room A)
Riccardo Poli and William B. Langdon
In this tutorial we will first introduce the basic models of particle swarm optimisation (PSO) and some more avanced variants. We will then look at efforts to extend PSOs. For example, we will show how it is possible to automatically discover new PSOs that best fit specific application domains. In addition, in the tutorial we attempt to explain how and why PSOs work, by using VRML visualisation tools, simplified communication models, and Markov chain theory. Finally, we will show how it is possible to automatically identify problems where PSOs work better than other competing algorithms (including hill climbers, evolutionary strategies, and differential evolution) and problems where the reverse is true, thereby making it possible start understanding how to match algorithms to problems.
11:30-13:00 An Introduction to Swarm Robotics (Room B)
In this tutorial, I will first situate Swarm Robotics within the Swarm Intelligence and Robotics field and introduce my own definition of Swarm Robotics based on recent shared consensus in the community. I will then survey and classify current methods for the forwards (i.e., from individual nodes to the swarm) and reverse (i.e., from the swarm to the individual nodes) engineering problems. I will support this survey with concrete case studies drawn from the literature, including work performed in my group. In particular, I will show how the application of swarm-intelligent algorithms to multi-robot systems requires extremely careful considerations about real-world and technological constraints in order to lead to self-organized, fully distributed, and scalable collective control while maintaining individual simplicity and autonomy. Finally, I will conclude my tutorial with some speculative thoughts about the future of Swarm Robotics and possible synergies with neighboring areas.
13:00-15:00 Free time for lunch
(Lunch is up to the attendees. A list of restaurants and cafeterias in the neighborhood will be provided.)
15:00-16:30 An overview of the swarm-bot and other self-assembling robotic systems (Room A)
Marco Dorigo and Roderich Groß
This talk will be organized in two parts. First, we will report on work we carried out within the SWARM-BOTS project, a project funded by the Future and Emerging Technologies program of the European Commission. This work is directly inspired by the collective behavior of social insects colonies and other animal societies. In particular, it focuses on the study of the mechanisms which govern the processes of self-organisation and self-assembling in artificial autonomous agents. In order to pursue these objectives, a new type of robot, called s-bot, has been developed. The s-bots are mobile robots with the ability to self-assemble, that is, to connect to and disconnect from each other. A swarm-bot is defined as an artifact composed of a swarm of assembled s-bots and is capable of solving problems that a single s-bot cannot solve. We will describe the hardware and control algorithms that we developed, and many recent results concerning coordinated movement, path formation, and group transport. In the second part, we overview other existing self-assembling robotic systems. We will focus on those systems for which self-assembly of two or more components has been demonstrated. We present a comparison of the different systems, and conclude the tutorial by discussing potential directions for future research.
15:00-16:30 Introduction to Stochastic Local Search (Room B)
Stochastic local search (SLS) algorithms are among the most prominent
and successful techniques for solving computationally hard problems in
many areas of Operations Research, Artificial Intelligence, or
Engineering. SLS techniques include constructive heuristics, iterative
improvement algorithms and general-purpose SLS methods, which are also
known as metaheuristics.
In this tutorial we will give an introduction to the SLS framework and give an overview of the most important SLS techniques. In a next step, we discuss the most important issues that arise in the implementation of SLS algorithms and we present an overview of a methodology for the empirical analysis of SLS algorithms.
16:30-17:00 Coffee Break
17:00-18:30 Applying ACO to real-world problems: the AntOptima experience (Room A)
Luca Maria Gambardella
Most problems faced by logistics operators have been known for centuries, think of the Chinese postman problem, first formulated by Euler in 1736. These problems have the ugly characteristic of being combinatorial, that is, all the possible combinations of the decisions and variables must be explored to find a solution of the problem. The downside of this situation is that as the number of decisions and variables increase (and in real world problems is quite easy to find problems with hundreds of variables) the time required to find a solution becomes rapidly unaffordable. Heuristics methods have been devised to rapidly explore only parts of the search space, concentrating in those parts that appear to promise a probable improvement of the solutions, thus reducing the time required to obtain a solution, which is often sub-optimal, but already a good improvement from the starting situation. A heuristic makes use of peculiar characteristics of a problem and exploits them to find a solution. Other empirical methods do not exploit only the problem characteristics but especially the analogy with other optimization methods found in Nature. One of the most recent and powerful heuristic is Ant-Colony Optimization (ACO). ACO is based on the observation that real ants find the optimal path between a food source and their nest food by depositing chemical traces (pheromones) on the floor. A computer analogy has been implemented where a large number of simple artificial ants are able to build good solutions to rich VRP problems via low-level based communications based on artificial pheromone. We present and we review the most recent on running industrial applications mainly in the field of advanced routing systems.
17:00-18:30 An Introduction to Patent Examination at the European Patent Office (Room B)
A patent is a legal title granting its holder the exclusive right to
make use of an invention for a limited set of countries and a
limited time by preventing others from making, using or selling it
without authorisation. A European patent can be obtained by filing a
single application in a unitary procedure before the European Patent
Office (EPO) and is valid in as many of the contracting states as
the applicant wishes to designate.
In the tutorial, the working method of the EPO in the patent grant procedure is presented from the filing of a patent application to the grant. The single steps search, examination, opposition, appeal are explained in detail, and also corresponding fees and costs are mentioned. The transparency of the procedure - the public has an essential role in regard to the European Patent Convention - is clarified using examples of possibilities for intervention.
Wednesday, 6th September 200609:00-10:30 Natural Protocol Engineering (Room A)
Nature inspired routing protocols are becoming an active area of research
because they do not require an a priori global system model of the network
rather they utilize a local system model as observed by the agents. The
agents gather the network state in a decentralized fashion and leave the
corresponding information on visited nodes. This information enables them
to make routing decisions in a decentralized fashion without the need
of having access to complete network topology. The algorithms can
adapt autonomously to changes in the network, or in traffic patterns.
The tutorial will start with a comprehensive survey of state-of-the-art Nature-inspired routing protocols discussing their relevant features and providing a critical review about each of them. We then introduce an engineering approach that could help in realizing a routing protocol in the network stack of Linux operating system, a real world router. The tutorial will also introduce a comprehensive performance evaluation framework.