Optimization techniques are search methods, where the goal is to find a solution to an optimization problem, such that a given quantity is optimized, possibly subject to a set of constraints. Modern optimization techniques start to demonstrate their power in dealing with hard optimization problems inrobotics and automation such as manufacturing cells formation, robot motion planning, job scheduling, cell assignment, vehicle routing problem, assembly line balancing, shortest sequence planning, sensor placement, unmanned-aerial vehicles (UAV) communication relaying and multirobot coordination to name just a few. These novel techniques are nature-inspired stochastic optimization methods that iteratively use random elements to transfer one candidate solution into a new, hopefully better, solution with regard to a given measure of quality. Using a multi-disciplinary perspective and reviewing fundamental theories, this course provides a comprehensive introduction to metaheuristic or stochastic optimization and highlights the power of these computational techniques in solving complex problems in robotics and automation. The course starts by introducing optimization theory and illustrates how the concepts of complex decentralized optimization are manifested in nature and how such models are inspiring new types of solutions methods. Topics to be covered include: tabu search, simulated annealing, evolutionary computing methods, computational swarm intelligence, ant-colony algorithms and particle swarm optimization. Different in-depth case studies will be provided to learn how to use these techniques in solving continuous and discrete problems that arise in robotics and automation applications.

Course Objectives:

• To provide methodological fundamentals for stochastic optimization.
• To understand non-biological system-based and biological system-based metaheuristic optimization techniques such as tabu search, simulated annealing, genetic algorithms, ant colony optimization and particle swarm optimization.
• To introduce students the applications of these techniques in robotics and automation.

Course Topics:

Metaheuristic algorithms can be classified into trajectory-based and population-based algorithms. A trajectory-based metaheuristic optimization algorithm such as simulated annealing use a single agent or solution which moves through the design space or search space in a piecewise style. A better move or solution is always accepted, while a not-so-good move can be accepted with certain probability. The steps or moves trace a trajectory in the search space, with a non-zero probability that this trajectory can reach the global optimum. On the other hand, population-based algorithms such as genetic algorithms, ant colony optimization and particle swarm optimization use multiple agents to search for an optimal or near-optimal solution.

The course is divided into two seminars that cover different metaheuristic optimization techniques and their applications in robotics and automation.

Seminar I: Trajectory-based Metaheuristic Optimization

Introduction Optimization Theory Tree-search Algorithms Tabu Search Simulated Annealing

Seminar II: Population-based Metaheuristic Optimization

Nature-inspired Metaheuristic Optimization Evolutionary Computation Genetic Algorithms Swarm Intelligence Particle Swarm Optimization Ant Colony Optimization

Course Instructor: Dr. Alaa Khamis
Email: a[dot]khamis[at]pami[dot]uwaterloo[dot]ca
Office: 1.3B12
Office hours: Thursdays 1:00-2:00PM

Textbooks:
- A. Engelbrecht. Fundamentals of Computational Swarm Intelligence. Wiley, 2005.
- Xin-SheYang. Engineering Optimization: An Introduction with Metaheuristic Applications. A JOHN WILEY & SONS, INC., 2010.
- Singiresu S. Rao. Engineering Optimization: Theory and Practice. A JOHN WILEY & SONS, INC., 2009.
- K. Doerner, M. Gendreau, P. Greistorfer, W. Gautjahr, R. Hartl and M. Reimann (Eds.). Meteheuristics: Progress in Complex Systems Optimization. Springer, 2007" K. Doerner, M. Gendreau, P. Greistorfer, W. Gautjahr, R. Hartl and M. Reimann (Eds.). Meteheuristics: Progress in Complex Systems Optimization. Springer, 2007.