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 nonlinear, 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 multirobot system.
Under certain conditions, such systems can produce useful systemlevel behaviors, display selforganized spatialtemporal patterns, effectively perform computations, information dissemination, and decisionmaking. 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:
For each system, we will present the general model and study general properties in terms of selforganization 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).
Students who successfully complete the course will have acquired general knowledge of multicomponent 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.
The only strict prerequisite is 15122 (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. /
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 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 1page cheatsheet
(written in any desired format).
In addition to the slides, during the course additional material will be provided by the instructor to cover specific parts of the course.
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 selforganization; course road map  Interesting, useful, or just enjoyable readings:


1/15  Continuoustime dynamical systems 1: Time, entropy, and selforganization; examples from physics and chemistry; modeling complex systems; introduction to dynamical systems (ODEs)  
1/17  Continuoustime dynamical systems 2: General formal definition of dynamical systems; vector fields, flows, and orbits; recurrence equations and iterated maps; continoustime dynamical systems; separation of variables; population growth models and solutions  A (relatively old) survey on population growth  
1/20  Continuoustime dynamical systems 3: More on growth models; flows and divergence; dissipative and conservative systems; regular vs. chaotic scenarios; first notions on attractors.  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  Continuoustime 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  
1/24  Continuoustime 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  
1/27  Continuoustime dynamical systems 6: Analysis of stability in linear systems; phase portraits vs. cases for eigenvalues and eigenvectors; classification of equilibrium points;  
1/29  Continuoustime dynamical systems 7: Structural stability in linear systems; analysis of solutions and stability in nonlinear systems; stability of perturbation of the vector field near equlibrium points; linearization techniques; derivatives and Jacobian matrix  
1/31  Discussion of next homework  
2/3  Continuoustime dynamical systems 8: Analysis of linearized systems and stability in the original nonlinear system; damped pendulum case study; eigenvalues and stability; separatrices and basin of attraction; nullclines; python software for the analysis of dynamical systems 


2/5  Continuoustime dynamical systems 9: Global stability notions; basin of attraction; Lyapunov functions; geometry of equilibria and attractors in the phase space  
2/7  Continuoustime dynamical systems 10: Limit cycles; Van der Pol oscillator; conditions of existence of limit cycles; Poincare'Bendixson theorem; no chaos in 2D  
2/10  Continuoustime dynamical systems 11: Attractors; strange attractors; Lorenz nonlinear system; divergence and volume contraction in the phase space; bifurcations (saddle, transcritical, pitchfork, super and subcritical, Hopf); route to chaos; characterization of deterministic chaos 


2/12  National sports day  
2/14  Discussion of next homework  
2/17  Discretetime dynamical systems 1: Maps vs. flows; discretetime dynamic systems; equilibrium points and stability; logistic map; analysis of the transition from order to chaos; sensitivity to initial conditions  
2/19  Discretetime dynamical systems 2: Bifurcations and period doubling phenomena in logistic map; orbit diagrams; study of the occurrence of periodic windows; selfsimilarity; different types of bifurcations  
2/21  Discretetime 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 multidimensional maps; hyperbolic points and analysis of stability in flows and maps; concepts for HartmanGrobman theorem: metric vs. topological spaces, neighborhoods and continuity in topological spaces, homeomorphisms and conjugate maps; HartmanGrobman 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)  Review paper on methods for constructing Lyapunov functions (check sections 1, 2, 2.1, 2.7, 3.2)  
2/24  Cellular Automata 1 / Discretetime dynamical systems 4: Review of the concepts related to
metric and topological spaces, conjugate maps, HartmanGrobman theorem, and Lyapunov functions from the
previous lecture (see the slides of 2/21 lecture); from ndimensional 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 
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 / Discretetime 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  
2/28  Cellular Automata 3 / Discretetime 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; preypredator model; bacterial diffusion model, quorum sensing: rockpaperscissors CA; simple fluid simulation; generative music approaches  Check the videos' links included in the slides! Scientific articles on specific CA models: 

3/10  Cellular Automata 4 / Discretetime dynamical systems 6: Application case study: CAs as simulation models of car traffic; rule 184; densitydependent behavior and phase transitions; NagelSchreckenberg onedimensional model; boundary conditions; VelocityDependent Randomization (VDR) model; metastability and lifetime of traffic jams; effect of traffic lights; RickertNagelSchreckenberg twodimensional model with lane changes  
3/12  Swarm Intelligence 1 / PSO 1: Limitations of the Cellular Automata model; from CA to a more general agentbased modeling; basic notions on optimization problems; mathematical programming and blackbox 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 pseudocode; interpretation of the different components; explorationexploitation dilemma  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 pseudocode; interpretation of the different components; explorationexploitation dilemma; properties of different neighborhoods; properties of acceleration coefficients; constriction coefficient; fullyinformed PSO; variance of performance; theoretical properties  
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 stepsize; application example to the minimization of the loss fucntion in supervised learning; stochastic gradient descent; adaptive stepsize as onedimensional optimization; analytic stepsize determination using the 2nd order Taylor expansion; properties of the Hessian matrix; quadratic forms; geometry in the neighborhood of a local optimum; adaptive stepsize without the Hessian  Onedimensional search methods  
3/19  Swarm Intelligence 4 / Optimization metaheuristics: Multiple restart gradient descent; blackbox optimization approaches; iterative solution modification metaheuristic; local search; hillclimbing; global search: basic ideas of iterated local search, tabu search, simulated annealing; from singleagent to multiagent strategies; solution construction metaheuristic  Extras:  
3/24  Swarm Intelligence 5 / Ant Colony Optimization 1: Multiagent systems and communications; neighborhoods and information exchange in natural systems; stigmergic communication; converging and diverging stigmergy; pheromone layingfollowing behavior in ant colonies and shortest path finding  
3/26  Swarm Intelligence 6 / Ant Colony Optimization 2: From ant colonies to antlike agents; path finding on decision graphs; pheromone and heuristic information for local decisionmaking; stochastic policy learning; exploration vs. exploitation; pheromone variables as parametric collective learning; Ant Colony Optimization (ACO) metaheuristic in psedocode; notions on generalized policy iteration and Monte Carlo path sampling; TSPcase study  
3/28  Swarm Intelligence 7 / Ant Colony Optimization 3: Combining pheromone and heuristic information in Antrouting 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 onlinestepbystep pheromone updating for exploration; ACS + Local Search / Daemon action (2Opt ot 3Opt)  ACO book  
3/31  Swarm Intelligence 8 / Ant Colony Optimization 4: ACO + Local search; nexchange 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)  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 multiagent task allocation; problem taxonomy; optimization models of task allocation: linear assignment, iterated assignment, online assignment, generalized assignment; complexity and basic approaches  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  Formulations of Hamiltonian tour constraints in routing models (TSP)  
7/4  Task Allocation 3: Emergent task allocation: antinspired methods; marketbased methods; auction models with humans and with robots; singleitem, multipleitems, combinatorial auctions; types of auctions for task allocation  
14/4  Task Allocation 4: Auction models for robot task allocation: parallel, combinatorial, and sequential auctions; multirobot routing example; properties of parallel auctions; properties of combinatorial auctions; properties of sequential auctions  
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 multirobot routing problem: VRP; worstcase deviation from optimality using bidding rules in sequential auctions; case study for goods delivery  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  
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; powerlaw and scale free property; smallworld property; real vs. random networks; WattsStrogatz model  Barabasi's book on network science  
23/4  Networks 2: notion of centrality to assess importance and criticality of a node; different centrality indices; degree centrality; betweenness centrality; closeness centrality; eigenvector centrality; iterative solutions for eigenvector centrality; message passing, pushpull, power method approaches; alpha centrality; examples, page ranking  
25/4  Summary + Q&A 
Topic  Files  Due Date 

Homework 1: Study of solutions and stability of nonlinear 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 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.
Name  Hours  Location  

Gianni Di Caro  gdicaro@cmu.edu  Thursdays 2:303:30pm + Drop in at my office any time ...  M 1007 