15-382 - Spring 2019

Collective Intelligence:

From Multi-Agent Systems to Swarms



Key Information

Sunday, Tuesdays, 3:00pm - 4:20pm, Room 2051

(Recitations) Thursdays, 4:30pm - 5:20pm, Room 2051

9.0

20% Final summary homework, 15% Midterm exam, 55% Homework

15-122 + general background in CS, calculus, and probability theory


Overview

This course is about modeling and control of systems involving a large number of autonomous components that interact with each other, dynamically adapting to their changing environment as a result of mutual, possibly non-linear, interactions.

Examples of such components include ants foraging for food, cars in city traffic, pedestrians moving in crowds, birds flocking, firms competing in a market, robots in a swarm or multi-robot system.

Under certain conditions, such systems can produce useful system-level behaviors, display self-organized spatial-temporal patterns, effectively perform computations, information dissemination, and decision-making. Loosely speaking, when this happens we can say that the system is displaying a form of collective intelligence.

During the course we will study a number of such systems with different characteristics in terms of complexity and capabilities of the individual components, interaction modes, goals. In particular, Collective intelligence will expose students to relevant mathematical and computational models from following domains:

  • Complex systems
  • Continuous-time Dynamical systems
  • Discrete-time Dynamical systems
  • Lattice models: Cellular Automata
  • Social choice
  • Game theory
  • Distributed consensus
  • Task allocation
  • Swarm intelligence
  • Social networks
  • Pattern formation
  • Neural models
  • Self-organizing maps

For each system, we will present the general model and study general properties in terms of self-organization and emergence, predictability of system’s evolution (direct problem), design of local interaction rules with the aim of attaining a specific task or behavior (inverse problem).


Objectives

Students who successfully complete the course will have acquired general knowledge of multi-component complex adaptive systems in terms of: (i) the challenges related to modeling, prediction, and control aspects, (ii) the practice of effectively implementing such systems.

Moreover, by studying systems related to different domains (biology, economy, robotics, operations research) the student will be exposed to a truly interdisciplinary background of mathematical models and application problems.


Prerequisites

The only strict pre-requisite is 15-122 (Principles of imperative programming). However, since the course will cover a number of different topics, students should have previous (and solid) programming experience as well as a solid background in general CS, calculus, and basics of probability theory.

Talk to the instructor if you are unsure whether your background is suitable or not for the course. /


Course Layout

The course will be based on lectures. Recitations will be used to work out examples and cover aspects that may not be in the students' background. Students are expected to attend all classes and to actively participate with questions.

For each one of the different topics, the course will present relevant techniques, discuss formal results, and show the application to problems of practical and theoretical interest.

Homework will include papers to read and review, questions to be answered and programming assignments. Written questions will involve working through different algorithms, deriving and proving mathematical results, and critically analyzing the material presented in class. Programming assignments will mainly involve writing code to implement and test algorithms in relevant scenarios. A strong emphasis will be given on ``learning by doing'', therefore the programming part will play a prominent role.

Grading: policies and schedules

Grading is based on the following distribution: 55% homework, 30% final project, 15% midterm exam.

The final project will focus on at least two of the topics discussed during the course and will consist of: select and read a few related papers, work out and implement the main ideas but in a (slightly) different scenario, add something new either in the "mechanisms" and/or in the analysis, perform experiments. At the end, write a final report on the work done starting from analyzing in a critical way the work reported in the selected papers from the literature.

During the last week, the student will make a presentation describing the work done and showing the achieved results.

Final projects can be done in group(s). However, each student will have to compile his/her own individual report, and the presentation will have to be organized in some "collective" way (i.e., each participant has to present a substantial part of the work).

The midterm exam will include theory, concepts, and math, and is set for set for ... During the exam students are allowed to consult 1-page cheatsheet (written in any desired format).


Readings

In addition to the slides, during the course additional material will be provided by the instructor to cover specific parts of the course.

Schedule (Subject to change)

Dates Topic Slides References
1/13 Introduction: General notions on complex systems; examples of collective intelligence from biology, physics, social, and robotic sciences; emergence and self-organization; course road map pdf Interesting, useful, or just enjoyable readings:
  • L. Fisher, The perfect swarm - The science of complexity in everyday life, Basic Books, 2011
  • T. Malone, M. Bernstein (eds.), Handbook of collective intelligence, MIT Press, 2015
  • M. Mitchell, Complexity a guided tour, Oxford University Press, 2011
  • M. Crichton, Prey, Harper, 2002
1/15 Continuous-time dynamical systems 1: Time, entropy, and self-organization; examples from physics and chemistry; modeling complex systems; introduction to dynamical systems (ODEs) pdf
1/17 Continuous-time dynamical systems 2: General formal definition of dynamical systems; vector fields, flows, and orbits; recurrence equations and iterated maps; continous-time dynamical systems; separation of variables; population growth models and solutions pdf A (relatively old) survey on population growth
1/20 Continuous-time dynamical systems 3: More on growth models; flows and divergence; dissipative and conservative systems; regular vs. chaotic scenarios; first notions on attractors. pdf The part on logistic growth is in the slides of previous lecture
A classic textbook on ODEs, check chapter 10 (but also 2 and 4): W. Trench, Elementary differential equations with boundary problems, 2013
1/22 Continuous-time dynamical systems 4: Divergence theorem for flow contraction; fixed points; stability concepts; Lyapunov stability and structural stability; attractors; regular vs. strange attractors; fundamental theorems on the solutions of linear ODEs; linear independence and use of Wronskian pdf
1/24 Continuous-time dynamical systems 5: Eigenvalues, eigenvectors and determinants in linear systems; solution of linear systems using eigenvalues and eigenvectors; introduction to the study and classification of equilibrium points pdf
1/27 Continuous-time dynamical systems 6: Analysis of stability in linear systems; phase portraits vs. cases for eigenvalues and eigenvectors; classification of equilibrium points; pdf
1/29 Continuous-time dynamical systems 7: Structural stability in linear systems; analysis of solutions and stability in non-linear systems; stability of perturbation of the vector field near equlibrium points; linearization techniques; derivatives and Jacobian matrix pdf
1/31 Discussion of next homework
2/3 Continuous-time dynamical systems 8: Analysis of linearized systems and stability in the original non-linear system; damped pendulum case study; eigenvalues and stability; separatrices and basin of attraction; nullclines; python software for the analysis of dynamical systems pdf
2/5 Continuous-time dynamical systems 9: Global stability notions; basin of attraction; Lyapunov functions; geometry of equilibria and attractors in the phase space pdf
2/7 Continuous-time dynamical systems 10: Limit cycles; Van der Pol oscillator; conditions of existence of limit cycles; Poincare'-Bendixson theorem; no chaos in 2D pdf
2/10 Continuous-time dynamical systems 11: Attractors; strange attractors; Lorenz non-linear system; divergence and volume contraction in the phase space; bifurcations (saddle, transcritical, pitchfork, super- and sub-critical, Hopf); route to chaos; characterization of deterministic chaos pdf
2/12 National sports day
2/14 Discussion of next homework
2/17 Discrete-time dynamical systems 1: Maps vs. flows; discrete-time dynamic systems; equilibrium points and stability; logistic map; analysis of the transition from order to chaos; sensitivity to initial conditions pdf
2/19 Discrete-time dynamical systems 2: Bifurcations and period doubling phenomena in logistic map; orbit diagrams; study of the occurrence of periodic windows; self-similarity; different types of bifurcations pdf
2/21 Discrete-time dynamical systems 3: Analysis of period doubling in logistic map; transition to chaos; sensitivity to initial conditions; Lyapunov exponents: definition and construction; Henon map and multi-dimensional maps; hyperbolic points and analysis of stability in flows and maps; concepts for Hartman-Grobman theorem: metric vs. topological spaces, neighborhoods and continuity in topological spaces, homeomorphisms and conjugate maps; Hartman-Grobman theorem for flows and maps; global stability and basin of attraction: Lyapunov functions for flows and maps (note: useful extra material has been added to the slides) pdf Review paper on methods for constructing Lyapunov functions (check sections 1, 2, 2.1, 2.7, 3.2)
2/24 Cellular Automata 1 / Discrete-time dynamical systems 4: Review of the concepts related to metric and topological spaces, conjugate maps, Hartman-Grobman theorem, and Lyapunov functions from the previous lecture (see the slides of 2/21 lecture);
from n-dimensional maps to Cellular Automata; spatially bounded lattice models; CA as lattice models; structure and parameters of a CA; formal definition; common lattices and boundaries; updating schemes; historical notes on CAs
pdf S. Wolfram, A new kind of science, 2002. THE book on Cellular Automata and way much more, a (maybe controversial but anyway original) phylosophical view on the computational universe, freely available after the 15th anniversary
2/26 Cellular Automata 2 / Discrete-time dynamical systems 5: Elementary CA; Wolfram code; direct and inverse problems; stability and Lyapunov exponents; diversity of behaviors; Wolfram's classification of Cellular Automata; dependence on initial conditions; propagation of information; importance of the neighborhood; direct vs. inverse problem; a few remarkable rules: 110, 30, 184 pdf
2/28 Cellular Automata 3 / Discrete-time dynamical systems 5: Application of Cellular Automata for modeling complex dynamical systems; Conway's Game of Life: rules, life forms, properties, propagation of information; forest fire model; prey-predator model; bacterial diffusion model, quorum sensing: rock-paper-scissors CA; simple fluid simulation; generative music approaches pdf Check the videos' links included in the slides!
Scientific articles on specific CA models:
3/10 Cellular Automata 4 / Discrete-time dynamical systems 6: Application case study: CAs as simulation models of car traffic; rule 184; density-dependent behavior and phase transitions; Nagel-Schreckenberg one-dimensional model; boundary conditions; Velocity-Dependent Randomization (VDR) model; metastability and lifetime of traffic jams; effect of traffic lights; Rickert-Nagel-Schreckenberg two-dimensional model with lane changes pdf
3/12 Swarm Intelligence 1 / PSO 1: Limitations of the Cellular Automata model; from CA to a more general agent-based modeling; basic notions on optimization problems; mathematical programming and black-box optimization; general structure of Particle Swarm Optimization (PSO); swarm intelligence: a definition and general concepts; swarm intelligence frameworks vs. communication and agent types; Reynold's boids; NetLogo; Particle Swarm Optimization (PSO): general pseudo-code; interpretation of the different components; exploration-exploitation dilemma pdf A. Engelbrecht, Computational Intelligence, ch. 16, Particle Swarm Optimization
3/14 Swarm Intelligence 2 / PSO 2: Reynold's boids; NetLogo; Particle Swarm Optimization (PSO): general pseudo-code; interpretation of the different components; exploration-exploitation dilemma; properties of different neighborhoods; properties of acceleration coefficients; constriction coefficient; fully-informed PSO; variance of performance; theoretical properties pdf
3/17 Swarm Intelligence 3 / Classical Optimization: Single agent PSO; properties of directional derivatives and gradient vectors; algorithm of gradient descent / ascent; effect of constant step-size; application example to the minimization of the loss fucntion in supervised learning; stochastic gradient descent; adaptive step-size as one-dimensional optimization; analytic step-size determination using the 2nd order Taylor expansion; properties of the Hessian matrix; quadratic forms; geometry in the neighborhood of a local optimum; adaptive step-size without the Hessian pdf One-dimensional search methods
3/19 Swarm Intelligence 4 / Optimization meta-heuristics: Multiple restart gradient descent; black-box optimization approaches; iterative solution modification meta-heuristic; local search; hill-climbing; global search: basic ideas of iterated local search, tabu search, simulated annealing; from single-agent to multi-agent strategies; solution construction meta-heuristic pdf Extras:
3/24 Swarm Intelligence 5 / Ant Colony Optimization 1: Multi-agent systems and communications; neighborhoods and information exchange in natural systems; stigmergic communication; converging and diverging stigmergy; pheromone laying-following behavior in ant colonies and shortest path finding pdf
3/26 Swarm Intelligence 6 / Ant Colony Optimization 2: From ant colonies to ant-like agents; path finding on decision graphs; pheromone and heuristic information for local decision-making; stochastic policy learning; exploration vs. exploitation; pheromone variables as parametric collective learning; Ant Colony Optimization (ACO) meta-heuristic in psedo-code; notions on generalized policy iteration and Monte Carlo path sampling; TSP-case study pdf
3/28 Swarm Intelligence 7 / Ant Colony Optimization 3: Combining pheromone and heuristic information in Ant-routing table; functional forms for the ant stochastic decision policy; different strategies and timing for pheromone updating (i.e., policy updating); AntSystem, the first ACO instance, for TSP; issues in the AS strategies for decision policy and pheromone updating; ACS, an improved system, with global best updating for exploitation and online-step-by-step pheromone updating for exploration; ACS + Local Search / Daemon action (2-Opt ot 3-Opt) pdf ACO book
3/31 Swarm Intelligence 8 / Ant Colony Optimization 4: ACO + Local search; n-exchange nehigborhood; performance of LS; Iterated Local Search; strategies for ILS; MMAS for dealing with pheromone bounds and restart in case of stagnation; elitistic ant selection for pheromone updating; choices to make when designing ACO algorithms; notes on theoretical results; issues in dynamic scenarios (data routing in networks) pdf Slides on Local Search (LS) and Iterated LS
4/2 Task Allocation 1: Generalities on task allocation, division of labor, role assignment, social organization; optimization formulation for multi-agent task allocation; problem taxonomy; optimization models of task allocation: linear assignment, iterated assignment, online assignment, generalized assignment; complexity and basic approaches pdf Gerkey and Mataric taxonomy of TA problems
4/4 Task Allocation 2: More optimization models of task allocation: routing models (VRP, TSP, Team Orienteering) and set models (set covering, packing, partitioning), vehicle routing as set partitioning; coalition models: set partitioning and set covering; subset selection vs. sequence ordering in combinatorial optimization and task allocation pdf Formulations of Hamiltonian tour constraints in routing models (TSP)
7/4 Task Allocation 3: Emergent task allocation: ant-inspired methods; market-based methods; auction models with humans and with robots; single-item, multiple-items, combinatorial auctions; types of auctions for task allocation pdf
14/4 Task Allocation 4: Auction models for robot task allocation: parallel, combinatorial, and sequential auctions; multi-robot routing example; properties of parallel auctions; properties of combinatorial auctions; properties of sequential auctions pdf
16/4 Task Allocation 5: performance criteria and bidding rules; complexity of computing optimal bids (TSP); computational and communication complexity of the different auction mechanisms; optimal task allocation model for the multi-robot routing problem: VRP; worst-case deviation from optimality using bidding rules in sequential auctions; case study for goods delivery pdf VRP formulation for goods delivery scenario
18/4 Wisdom of the Crowd: wisdom of the crowd examples; experts vs. non experts; prediction diversity theorem; role of independence and diversity; role of interconnection networks on the dynamics and behavior of a complex system pdf
21/4 Networks 1: directed vs. undirected networks; adjacency matrix; number pf paths and walks; diameter; average node degree; degree distribution; local clustering; random network model; sparsity of real networks; power-law and scale free property; small-world property; real vs. random networks; Watts-Strogatz model pdf Barabasi's book on network science
23/4 Networks 2
25/4 Summary + Q&A

Homework Assignments

Topic Files Due Date
Homework 1: Study of solutions and stability of non-linear dynamical models of competing populations hw1.pdf February 15, 2019
Homework 2: Modeling of complex systems, Stability analysis, Bifurcations, Iterated maps, Deterministic chaos hw2.pdf March 11, 2019
Homework 3: Cellular automata hw3.pdf
Homework 3 Extra: Fractals hw3_extra.pdf
Homework 4: Particle Swarm Optimization hw4.pdf
Homework 5: Classical optimization hw5.pdf
Homework 6: Ant Colony Optimization hw6.pdf

Homework Policies

  • Homework is due on autolab by the posted deadline. Assignments submitted past the deadline will incur the use of late days.

  • You have 6 late days, but cannot use more than 2 late days per homework. No credit will be given for homework submitted more than 2 days after the due date. After your 6 late days have been used you will receive 20% off for each additional day late.

  • You can discuss the exercises with your classmates, but you should write up your own solutions. If you find a solution in any source other than the material provided on the course website or the textbook, you must mention the source. You can work on the programming questions in pairs, but theoretical questions are always submitted individually. Make sure that you include a README file with your andrew id and your collaborator's andrew id.

  • In general, for both assignments and exams, CMU's directives for academic integrity apply and must be duly followed.

Office Hours

Name Email Hours Location
Gianni Di Caro gdicaro@cmu.edu Thursdays 2:30-3:30pm + Drop in at my office any time ... M 1007