Tutorial Program
Monday, 4th September 2006
08:30-19:00 Registration09:30-11:00 Ant Colony Optimization: An Introduction (Room A)
Marco Dorigo
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
Telecommunications networks are becoming increasingly complex, dynamic, and heterogeneous in terms of used technologies, connectivity, offered services, traffic patterns, etc. Therefore there is an urgent quest for new control and management algorithms which are adaptive to changes and robust to failures and perturbations, work in a self-organized and decentralized way, and are able to cope with heterogeneous large-scale systems. These algorithms are expected to continually learn about network and user context, adapt their decision policies, and even self-tune their internal parameters. In this tutorial I will show that Ant Colony Optimization (ACO) offers a framework to design novel routing algorithms which can "naturally" match most of these requirements and deliver at the same time superior performance. I will start by providing an introduction to the ACO metaheuristic pointing out those aspects that make it suitable for general dynamic distributed problems, and, more specifically, for adaptive routing in networks. After this rather general discussion, I will focus on the discussion of specific applications of ACO to design of routing algorithms for wired, mesh, and mobile ad hoc networks.
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)
Alcherio Martinoli
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.
Slides from the tutorial13: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)
Thomas Stützle
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)
Michael Sampels
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 2006
09:00-10:30 Natural Protocol Engineering (Room A)Muddassar Farooq
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.