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.

• Lecture notes Week 1 (slides)
• Papers
  • Social integration of robots into groups of cockroaches to control self-organized choices J Halloy, G Sempo, G Caprari, C Rivault, M Asadpour, F Tâche, I Said, … Science 318 (5853), 1155-1158, 2007.
  • Beni, Gerardo, and Jing Wang. “Swarm intelligence in cellular robotic systems.” In Robots and Biological Systems: Towards a New Bionics?, pp. 703-712. Springer Berlin Heidelberg, 1993.
• Books
  • Swarm Intelligence: From natural to artificial systems. E. Bonabeau, G. Theraulaz, and M. Dorigo, 1999.
  • Self-Organization in Biological Systems, Camazine, Deneubourg, Franks, Sneyd, Theraulaz, Bonabeau, 2003.
• Homework (due on Thursday, January 14)

Part I – Computational Swarm Intelligence

Week 2

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

• Lecture notes Week 2 (slides)
• Papers
  • Erik Eakins: Ant colony optimization M Dorigo, M Birattari, T Stützle – … Intelligence Magazine, IEEE, 2006
  • Amber Womack: Dorigo, Marco, and Christian Blum. “Ant colony optimization theory: A survey.” Theoretical computer science 344.2 (2005): 243-278.
• Books
  • Ant Colony Optimization. Dorigo and Stuetzle, MIT Press, 2004.

Lecture on Tuesday, paper presentations on Thursday.

Week 3

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

• Lecture notes (slides)
•  Papers
  • Irene Beckman: Particle swarm optimization R Poli, J Kennedy, T Blackwell – Swarm intelligence, 2007.
  • Reed Anderson: Pant, Millie, Radha Thangaraj, and Ajith Abraham. “Particle swarm optimization: performance tuning and empirical analysis.” In Foundations of Computational Intelligence Volume 3, pp. 101-128. Springer Berlin Heidelberg, 2009.
• Books
  • Swarm Intelligence, Eberhardt, Shi and Kennedy, 2001.

Lecture on Tuesday, paper presentations on Thursday.

Week 4

• Tuesday: Campus closure due to snow
• Thursday: The gathering swarms (PBS)

Week 5

Genetic algorithms.

• Lecture notes (slides)
•  Papers
  • Darrell Whitley:  “A genetic algorithm tutorial.” Statistics and computing 4.2 (1994): 65-85.
  • Yang Li: Floreano, Dario, and Francesco Mondada. “Automatic creation of an autonomous agent: Genetic evolution of a neural network driven robot.” Proceedings of the third international conference on Simulation of adaptive behavior: From Animals to Animats 3. No. LIS-CONF-1994-003. MIT Press, 1994.
• Books
  • Floreano, Dario, and Claudio Mattiussi. Bio-inspired artificial intelligence: theories, methods, and technologies. MIT press, 2008.

Lecture on Tuesday, paper presentations on Thursday.

Week 6

Neural networks (10 minutes presentation, 5 minutes discussion)

• Lecture notes (slides)
•  Papers
  • Bo Cao: Wythoff, Barry J. “Backpropagation neural networks: a tutorial.” Chemometrics and Intelligent Laboratory Systems 18.2 (1993): 115-155.
  • David Johnson: Hughes, Dana, et al. “Detecting and identifying tactile gestures using deep autoencoders, geometric moments and gesture level features.” Proceedings of the 2015 ACM on International Conference on Multimodal Interaction. ACM, 2015.
•  Books
  • Floreano, Dario, and Claudio Mattiussi. Bio-inspired artificial intelligence: theories, methods, and technologies. MIT press, 2008.

Lecture on Tuesday, paper presentations on Thursday.

Part II – Embodied Swarm Intelligence

Week 7

Amorphous Computing, Spatial Computing, and Programmable Matter.

• Lecture notes (slides)
• Papers
  • Berlin, Andrew, and Kaigham J. Gabriel. “Distributed MEMS: New challenges for computation.” Computational Science & Engineering, IEEE 4.1 (1997): 12-16.
  • Amorphous Computing, Abelson et al., 1999.
  • Programmable matter: concepts and realization T Toffoli, N Margolus – Physica D: Nonlinear Phenomena, 1991
  • Beal, Jacob, and Richard Schantz. “A spatial computing approach to distributed algorithms.” 45th Asilomar Conference on Signals, Systems, and Computers. 2010.
• Miniprojects: Using ACO to solve the TSP
  • Erik Eakins and Amber Womack
  • Daniel Zurawski and Yang Li
  • David Bittle and Samuel Horton

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

Week 8

Algorithms on planar graphs.

• Lecture notes (slides)
•  Papers
  • Correll, Nikolaus, Nicholas Farrow, and Shang Ma. “HoneyComb: a platform for computational robotic materials.” Proceedings of the 7th International Conference on Tangible, Embedded and Embodied Interaction. ACM, 2013.
•  Books
  • Decentralized Spatial Computing, M. Duckham, Springer, 2013
• Miniprojects: Using ACO for quadratic assignment and clustering
  • Lauren Mitchell and Davis Yoshida
  • Alex Cordero
  • Nika Shafranov and Noah Dillon
  • Tyler Bussell

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.

• Slides (lecture notes)
•  Papers
  • Kanakia, Anshul, John Klingner, and Nikolaus Correll. “A Response Threshold Sigmoid Function Model for Swarm Robot Collaboration.” In Proc. of Int. Symp. on Distributed Autonomous Robotic Systems (DARS), Springer Tracts on Advanced Robotics, Daejeon, Korea. 2014.
  • Amstutz, Patrick, Nikolaus Correll, and Alcherio Martinoli. “Distributed boundary coverage with a team of networked miniature robots using a robust market-based algorithm.” Annals of Mathematics and Artificial Intelligence 52.2-4 (2008): 307-333.
  • Lagoudakis, M.G., Markakis, E., Kempe, D., Keskinocak, P., Kleywegt, A.J., Koenig, S., Tovey, C.A., Meyerson, A. and Jain, S., 2005, June. Auction-Based Multi-Robot Routing. In Robotics: Science and Systems (Vol. 5, p. 98).
• Miniprojects: GA for optimization
  • Team T.J. Romanowski and Michael Muehlbradt
  • Falcon Taylor-Carter and Nick Smith
  • Branden Romero (TSP)

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.

• Hughes, Dana, and Nikolaus Correll. “Texture recognition and localization in amorphous robotic skin.” Bioinspiration & biomimetics 10.5 (2015): 055002.
• McEvoy, M. Andy, and Nikolaus Correll. “Thermoplastic variable stiffness composites with embedded, networked sensing, actuation, and control.” Journal of Composite Materials (2014): 0021998314525982.
• HOSSEINMARDI, HOMA, et al. “Distributed Spatio-Temporal Gesture Recognition in Sensor Arrays.”
• Farrow, Nicholas, and Nikolaus Correll. “A soft pneumatic actuator that can sense grasp and touch.” Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on. IEEE, 2015.

Week 13

Synchronization and Consensus.

• Slides (lecture notes)
• Papers
  • Lucarelli, D. and Wang, I.J., 2004, November. Decentralized synchronization protocols with nearest neighbor communication. In Proceedings of the 2nd international conference on Embedded networked sensor systems (pp. 62-68). ACM.
  • Werner-Allen, G., Tewari, G., Patel, A., Welsh, M. and Nagpal, R., 2005, November. Firefly-inspired sensor network synchronicity with realistic radio effects. In Proceedings of the 3rd international conference on Embedded networked sensor systems (pp. 142-153). ACM.
• Miniprojects: Neural Networks
  • David Johnson and Irene Beckman
  • Bo (Bryan) Cao and Anders Soong
  • Joe Jackson and Mario Alanis

Week 14

 

• Simulating large-scale distributed systems and multi-level modeling.
  • Papers
    • Correll, Nikolaus, and Heiko Hamann. “Probabilistic Modeling of Swarming Systems.” Springer Handbook of Computational Intelligence. Springer Berlin Heidelberg, 2015. 1423-1432.
    • Gillespie, Daniel T. “An exact method for numerically simulating the stochastic coalescence process in a cloud.” Journal of the Atmospheric Sciences 32.10 (1975): 1977-1989.
    • Rutishauser, Samuel, Nikolaus Correll, and Alcherio Martinoli. “Collaborative coverage using a swarm of networked miniature robots.” Robotics and Autonomous Systems 57.5 (2009): 517-525.
    • Modeling and designing self-organized aggregation in a swarm of miniature robots N Correll, A Martinoli The International Journal of Robotics Research 30 (5), 615-626, 2012.
• Paper presentations (Auction-based task allocation)
  • John Lammie
  • Joe Jackson

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

• Clustering, classification and regression (UCI)
• Traveling Salesman Problem (Waterloo)
• Quadratic Assignment Problem
• PSO Benchmark functions

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

• CSCI 7000: Robotic Materials, Fall 2014
• Swarm Intelligence and Self-Assembly, Fall 2011