Overview

Swarm Intelligence is a fundamental guiding principle of many natural systems. While it is most apparent in social insects such as ants, bees and termites, the underlying phenomenon of self-organization is scale-free, governing multi-body systems ranging from atoms to galaxies. This class will provide an overview over both computational swarm intelligence, classes of algorithms and meta-heuristics that are inspired by biological systems and can provide competitive solutions to a number of hard optimization problems, and embedded swarm intelligence, including swarm robotics and robotic materials.

The class consists of lectures every Tuesday to introduce this week’s topic and literature reviews presented by the students on Thursdays, a mini project and a final group project. The mini project consists of implementing a computational swarm intelligence algorithm of the student’s choice and presenting its results to class. The project will explore a novel direction, either by deriving a novel algorithm, combining existing ones, or identifying a novel application.

Prerequisites: Discrete Algorithms

Meetings

We will be meeting Tuesdays and Thursdays from 9.30 till 10.45 in MUEN E064.

Textbook

Lecture notes will be provided. A large subset of the class is covered by Swarm Intelligence: From natural to artificial systems. E. Bonabeau, G. Theraulaz, and M. Dorigo, 1999 and students are encouraged to obtain a copy.

Syllabus

Week 1

What is Swarm Intelligence? Examples from nature, computational principles and artificial swarms including robotic materials.

Part I – Computational Swarm Intelligence

Week 2

Ant Colony Optimziation, a meta-heuristic for routing, clustering and quadratic assignment optimization problems.

Lecture on Tuesday, paper presentations on Thursday.

Week 3

Particle Swarm Optimization, a meta-heuristic for non-convex optimization problems.

Lecture on Tuesday, paper presentations on Thursday.

Week 4

Week 5

Genetic algorithms.

Lecture on Tuesday, paper presentations on Thursday.

Week 6

Neural networks (10 minutes presentation, 5 minutes discussion)

Lecture on Tuesday, paper presentations on Thursday.

Part II – Embodied Swarm Intelligence

Week 7

Amorphous Computing, Spatial Computing, and Programmable Matter.

Lecture on Tuesday, miniprojects on Ant Colony Optimization on Thursday.

Week 8

Algorithms on planar graphs.

Lecture on Tuesday, miniprojects on Ant Colony Optimization on Thursday.

Week 9

Project brainstorming.

  • Slides
  • Miniprojects: Function Optimization using PSO
    • Andy McEvoy and Reed Anderson
    • Ryan Bohannon and Jack Skinner
    • John Lammie and Darren Guinness

Lecture on Tuesday, miniprojects on Particle Swarm Optimization on Thursday.

Week 10

Threshold-based and market-based task allocation. Hardware: the Droplets.

Lecture on Tuesday, miniprojects on Genetic Algorithms on Thursday.

Week 11

Spring break

Part III – Applications and Tools

Week 12

Applications. Distributed optimization for shape change, distributed classification for gesture recognition, feedback control and high-bandwidth signal processing.

Week 13

Synchronization and Consensus.

Week 14

 

Week 15

Project.

Week 16

Project presentations.

  • Tuesday:
    • Inverse Kinematics using Particle Swarm Optimization
    • Deep Learning on “Risk” using MCTS
    • Evolve Neural Network Controlled Robots using GA
    • A distributed Histogram implementation for spatial computers
  • Thursday:
    • Cooperation Among Agents in a Partially Observable Environment using Deep Distributed Recurrent Q-Networks
    • Multi-modal Synchronization in a robot swarm
    • Hub formation in Penguins
    • Nested PSO: Finding better tuning parameters.

Mini project

The mini project consists of an implementation and benchmark of a computational swarm intelligence algorithm of your choice applied to an existing data set

or data from your research. Please self-organize into teams using the following slide deck.

Project ideas

  • A distributed Voronoi partitioning algorithm for spatial computers
  • A distributed Histogram implementation for spatial computers
  • Turing patterns for active camouflage
  • Synchronization using multi-modal messaging
  • Algorithms for hub formation in Penguins
  • Algorithms for information exchange in bat vortices
  • Evolving a robot controller on Sparki

Previous iterations

This class is a continuation of

 

 

 

 

Comments are closed.

Set your Twitter account name in your settings to use the TwitterBar Section.