The course responsible for this course has chosen not to move his or her course web page to Studycas yet.

Course page for 2013/2014 (link updated 2014-08-28):

http://physics.gu.se/~ostlund/ds/index.php

Published in Course page
  1. Recent updates
  2. Course description
  3. Schedule
  4. Problem sets
  5. Exams
  6. Links

  

1. Recent updates

This course is replaced by two courses starting spring 2017:  Intelligent agents and Autonomous robots. Intelligent agents home page: http://www.me.chalmers.se/~mwahde/courses/ia/2017/ia.html

 

2. Course description

Course specific prerequisites

Basic mathematical and programming skills are required. It is an advantage, but not absolutely necessary, to be familiar with Matlab. Some background concerning microcontrollers is advantageous, but not a requirement.

Aim

The course aims at giving the students an understanding of design principles for autonomous systems, both robots and software agens, and also gives students the opportunity to apply their knowledge in practice through the construction of a simple autonomous robot.

Learning outcome (after completion of this course, the student should be able to)

After successfully completing the course, the student will be able to:

- Understand and describe basic properties of robotic hardware, including sensors, actuators and microcontrollers.
- Describe the basics of animal behavior (ethology) and its connection to robotic behaviors.
- Understand the basics of behavior-based robotics and evolutionary robotics.
- Set up and use basic kinematic and dynamic equations for robot motion.
- Define and set up computer simulations of wheeled autonomous robots (using a simulator provided by the lecturer).
- Define and set up evolutionary simulations for the optimization of robotic control systems (using a simulator provided by the lecturer).
- Understand and apply basic methods for behavior generation and behavior selection in autonomous robots.
- Understand the basics of utility theory and its application in robotic behavior selection.
- Understand and describe the basics of swarm intelligence and agent-based economics.
- Construct and use a simple autonomous robot.

Content

The contents of the course are as follows:

- Theory of autonomous robots: Kinematics and dynamics
- Behavior-based robotics
- Evolutionary robotics
- Utility theory, behavioral economics, theory of rational decision-making
- Behavior selection in autonomous robots
- Artificial life and swarm intelligence
- Software agents, particularly agent-based economics
- Learning in autonomous agents
- Robot construction

Organisation

The course extends over two quarters. In the first part of the course, the theory is covered in 14 lectures. In the second part, a robot construction project is carried out (in groups of 5-6 students). In the final weeks of the course, the constructed robots are applied in a variety of simple tasks.

Literature

Lecture notes and handouts

Examination

The robot construction project is graded and corresponds to around 30% of the grade. 40% of the grade is determined based on the results of two home problems, and the remaining 30% are determined by the results on a written exam (at the end of the first half of the course).

3. Schedule

Please have a look on the external course webpage for more information.

4. Problem sets

Please have a look on the external course webpage for more information.

5. Exams

Please have a look on the external course webpage for more information.

6. Links

External course webpage: http://www.me.chalmers.se/~mwahde/courses/aa/2014/aa.html

Published in Course page

The course responsible for this course has chosen not to move his or her course web page to Studycas yet.

 

Course page for 2013/2014 (link updated 2014-08-28):

http://physics.gu.se/~frtbm/joomla/index.php?option=com_content&view=article&id=98&catid=79&Itemid=484

Published in Course page

The course responsible for this course has chosen not to move his or her course web page to Studycas yet.

 

Course page for 2013/2014 (link updated 2014-08-28):

http://physics.gu.se/~frtbm/joomla/index.php?option=com_content&view=article&id=98&catid=79&Itemid=484

Published in Course page

Simulation of Complex Systems Fall 2016

The course information this term will be published on pingpong.chalmers.se. If you have any requests regarding the course, please contact This email address is being protected from spambots. You need JavaScript enabled to view it..

 


 

  1. Recent updates
  2. Course description
  3. Schedule
  4. Problem sets
  5. Modeling and simulation project
  6. Project ideas

1. Recent updates

  • Dec 9: Added Mathematica files used in lectures 2 and 7 (see below under attachments).
  • Dec 1: Computer lab Dec 5 is cancelled. I will return with information on how we will deal with the last two sessions. 
  • Dec 1: Added compulsory and additional reading for Lecture 6 on cellular automata (see below).
  • Dec 1: Fourth and fifth home problems uploaded (see below).
  • Nov 26: Additional reading on the Barábasi-Albert preferential model added under Lecture 5.
  • Nov 21: Third home problem uploaded (see below).
  • Nov 21: Added lecture slides for Lecture 5 on networks.
  • Nov 21: Added link to compulsory reading for Lecture 5 on networks.
  • Nov 17: Added link to compulsory reading for Lecture 4 on modeling of complex systems.
  • Nov 17: Updated flawed link to reading on Schelling's model of segregation under Lecture 2 (spatial model of segregation).
  • Nov 11: Regarding homework: You are all meant to write your own code, in your preferred language. But you will work together as a group in discussing the homework and resolving algorithmic issues.
  • Nov 10: If you are taking this course, but have not yet received an email from me with your assigned group, please send me an email as soon as possible. 
  • Nov 10: Second home problem uploaded (see below).
  • Nov 10: First home problem uploaded (see below).
  • Nov 05: Slides for today's lecture added (see below).
  • Nov 05: Homepage updated for 2014. The course starts Wednesday Nov 05 and ends with project presentations Dec 19. This is the last date you have to be present at Chalmers for this course, as there is no exam. 

2. Course description

Much of modelling in the sciences focuses on simple models, highlighting key mechanisms using small sets of moving parts. However, in complex systems the interesting features are often a direct result of having large sets of particles or agents with different characteristics. This makes new tools a necessity. The course introduces simulation techniques frequently used in complex systems to handle models with many heterogeneous parts. Specifically, we will look at agent-based modelling, evolutionary game theory, cellular automata, and networks, with application to physics, biology and social science. We also learn how to validate the outcomes of simulation models in order to reach scientifically sound conclusions.

Literature

There is no single book that covers all the topics in the course so we have no required books. However, we aim to provide a set of compulsory (and additional) readings assigned to each lecture that covers and perhaps broadens the content of the lectures.  

If you still want something for your shelf, here are some recommendations:

Mark Newman's book on Networks is very good, both comprehensive and well-written. It covers much more than this course, but if you're the type that reads non-fiction and textbooks for fun, I can recommend it. If you want something shorter, the review article Statistical Mechanics of Complex Networks by Albert and Barabasi are available for free and covers most of the network topics we discuss.

For agent-based models we have used Epstein's Generative Social Science for a reading project earlier years. It gives a good overview of what kind of questions agent-based models can be used to handle in the social sciences and also discusses a range of fairly deep issues regarding e.g. what it means to explain a social phenomenon. Epstein's and Axtell's Growing Artificial Societies is shorter and focuses more on a single type of model, but can also serve as an introductory text.

For cellular automata, Ilachinski's Cellular Automata - A Discrete Universe is very comprehensive and covers almost everything even remotedly related to CA. I'm not very impressed with its quality though, and would only recommend it to someone who only need the coverage and can afford to read it with a skeptical mind. You can also take a look at Wolfram's A New Kind of Science (full book available online), though even stronger caveats apply here (see e.g. this review). Wolfram's papers are much more measured, though a bit dated by now. You could for example take a look at his review Statistical Mechanics of Cellular Automata.

Teachers:

Main lecturer: Kolbjørn Tunstrøm (This email address is being protected from spambots. You need JavaScript enabled to view it.)

Tutors: Erik Edlund, Vilhelm Verendel, Clas Andersson, Jonas Einarsson, Martin Nilsson Jacobi

Examiner: Martin Nilsson Jacobi (This email address is being protected from spambots. You need JavaScript enabled to view it.)

You can find us in our offices at the division of Physical Resource Theory, in the EDIT-building.

3. Schedule

Ordinary lectures are 8.00-10.00 in MC on Wednesdays and Fridays. Computerlabs replace Friday lectures some weeks and take place in F-T7204 (in Forskarhuset Fysik, street address Fysikgränd 3).

Variations can occur, please check the lecture plan below.

Lecture plan

Lecture 1: Wednesday Nov 05 The role of simulations in the study of complex systems; Course information; Introduction to agent based modeling; Collective motion.

Compulsory reading:

Additonal reading:

Lecture slides:

Lecture 2: Friday Nov 07 Agent based models continued; SIR model of disease spreading; Schelling's model of segregation.

Compulsory reading:

Additonal reading:

Lecture 3: Wednesday Nov 12 Evolutionary game theory (guest lecture by Kristian Lindgren).

Compulsory reading:

Lecture 4: Wednesday Nov 19 Modeling of complex systems (guest lecture by Philip Gerlee).

Compulsory reading:

Lecture 5: Friday Nov 21 Networks Part 1; Preferential growth and scale free networks; The small world model.

Compulsory reading:

Additonal reading:

Lecture slides:

Lecture 6: Wednesday Nov 26 Introduction to cellular automata (CA); CA as modeling technique (guest lecture by Martin Nilsson Jacobi).

Compulsory reading:

Additonal reading:

Lecture 7: Wednesday Dec 03 Networks part 2; Community structure and modularity; Percolation and disease spreading on networks.

Lecture 8: Wednesday Dec 10 Stability of complex systems.

See also TimeEdit. But note the change we have made in presentation date from Jan 09 2015 to Dec 19 2014.

4. Problem sets

The purpose of the problem sets is to provide you with hands on experience of the different methods presented in the course. You will work in groups of 3 and have your work assessed in a series of scheduled computer labs. The problem sets account for 50% of your total course grade.

Grading

There are five problem sets available, each accounting for 25 points. The homework deadlines are set with the assumption that you choose one of Homework 1 and Homework 2, followed by doing the other three. A perfect score is therefore 100.

Note 1: A necessary (but not sufficient) requirement for passing grade is that 10 points are achieved in each homework 1 or 2, 3, 4, and 5.
Note 2: You can build your score anyway you want, attaining a maximum of 125 points (that's right; 25 points more than a perfect score).

The grade limits will be 45 points for grade 3, 65 points for grade 4, and 85 points for grade 5. For GU the limits will be 45 points for G and 75 for VG.

Computer labs

The computer lab sessions serve two purposes: 1) To get help if you are stuck in a problem set (and have not managed to get unstuck by consulting some of your classmates); and 2) To have your homework graded. Previous terms, we have experienced queues during lab hours. Therefore, we emphasise the “home” in homework; being prepared before you enter the lab is crucial for these sessions to run smoothly.

Groups

You will be randomly divided into groups of three (possibly two). The reason for this is to allow for efficient execution of the computer labs; we only have two people available this year assisting in the lab sessions. But: Everyone is meant to program their own code, or at least contribute significantly to each problem set. That is, while you can split up the work in each problem set, you are not allowed to split the problem sets between you. Honor code: If you have not contributed to solving the problems, you should say so during assessment.

The topics of the homework are given below. Instructions for the specific homework's will follow throughout the term.

  • Homework 1: Disease spreading Implementing the agent-based SIR-model from the lecture on Nov 7. Deadline is Nov 28 (but first possibility of assessment is Nov 14). For instructions, download H1_DiseaseSpreading.pdf.
  • Homework 2: Evolutionary game theory A cellular automaton demonstrating the spatial prisoners dilemma, related to Kristian's lecture Nov 12. Deadline is Nov 28 (but first possibility of assessment is Nov 14). For instructions, download H2_EvoGamesCA.pdf.
  • Homework 3: Network models: Implementation and investigations of different random network models.  For instructions, download H3_NetworkModels.pdf. This pdf also contains links to files you need for the homework.
  • Homework 4: Cellular automaton model of forest fires. For instructions, download H4_ForestFires.pdf.
  • Homework 5: Communities and disease spreading on networks. For instructions, download H5_NetworkCommunitiesDynamics. This pdf also contains links to files you need for the homework.

Lab schedule

All computer labs take place in F-T7204.

  • Lab 1: Friday         Nov 14 08:00-09:45    Homework 1 & 2
  • Lab 2: Friday         Nov 28 08:00-09:45    Homework 3
  • Lab 3: Friday         Dec 05 08:00-09:45    Homework 4
  • Lab 4: Friday         Dec 12 08:00-09:45    Homework 4 & 5
  • Lab 5: Wednesday Dec 17 08:00-09:45    Extra lab

Each lab is intended to focus on the specified homework, but there will be an extra lab in the end where you can have assessed any of the homeworks.

5. Modeling and simulation project

The purpose of the project work is to provide you with training in

  • Defining your own research question. 
  • Executing a collaborative project.
  • Presenting your independent work in writing and as a summary talk.

The project accounts for 50% of your total course grade.

General information

You will be randomly divided into groups of three (possibly four). The reason for this is twofold; it will assure a broad distribution of skills and interest; it is a realistic scenario for later work in academia or industry.

Each group gets a tutor assigned and has ~3 meetings with this tutor during the course. Should it be so that you experience problems with the group assembly, you need to take this up with your tutor as soon as possible.

The project should be presented to the class on Friday December 19, and in a written report, to be handed in (by email) to your tutor within January 16. The effort spent on the project and the report/presentation should be around 50% of the total effort spent on the course.

On topics and questions

Your project needs two things to get started: a topic and a question (or problem formulation). A topic explains what you are going to do, a question explains why. A typical topic description could be "we want to do a agent-based simulation of a predator-prey system." A corresponding question could be "to see whether space changes the stability as compared to the behaviour in the standard ODE models.”

General advice

If I had an hour to solve a problem and my life depended on it, I would use the first 55 minutes to formulate the right question because as soon as I have identified the right question I can solve the problem in less than five minutes.

—Albert Einstein

Everything takes longer time than you expect, so getting started with your model implementation is essential for a successful project. Do not interpret the time ratio in the quote too literally; the moral is that you need to have a question you want to answer with your model. This provides the project with direction and makes navigating it much easier. But research (as much else) is a highly iterative process, so don’t expect a perfect question from the start. If you realize your question didn't make sense half-way through your project, take the time to try and formulate a new one. In a lot of real research the question in the paper ends up being quite different from the one that started the project (similarly among start-ups, many end up with a completely different product that their initial idea).

Start simple. It is fine to have a grand, pie-in-the-sky idea, but make sure the steps to the goal has some value in themselves. Not only does this prevent you from being stuck with nothing to show at the end of the course, it also gives you feedback on your big idea as early as possible. Start with a small question and iterate it towards greatness.

If there is a simpler model of what you are trying to do that shows some part of the interesting features, at the very least think about how they compare. Ideally, implement both and do a careful comparison. You can often get great project ideas out of thinking about what you lose when you remove features.

It's OK to fail. Research has a large portion of luck involved. If you have a good idea that don't work out, analyze why and we're happy.

Tutors

Each project group gets assigned a tutor. The tutor’s job is to give you general advice on anything you need as best as he or she can. The tutor’s job is not to formulate your project for you, nor to debug your code. The general guideline is to have three meetings in total: one in the beginning when you have a problem formulation and maybe have started implementing something; one in the middle when you have gotten your first results and thought about whether you need to reformulate your problem; and one at the end, to decide what more should be done and to get advice on the report and the oral presentation.

To get the most out of the meetings, make sure to prepare yourselves. Have specific questions written down. Have a demonstration of your code ready to run.

Presentation

The presentation of the project should take maximum 10 minutes, with an additional 5 minutes for questions and discussion. The timing will be enforced, so make sure you go through the presentation beforehand and check its duration. You decide whether and how to divide the material between yourselves.

Put the emphasis on what your problem formulation is, a general discussion about how you tackled it, what problems you had, and what your conclusions are. 

Report

Structure your report like a scientific article, with an abstract summarizing the rationale and results of the project; an introduction shortly explaining background and motivating why the question is interesting; methods and/or results section(s) describing your model and what you do with it; a discussion section; and ending with a short summary. Put some work into the discussion section. This is where you demonstrate that you truly understand the implications of your work, including shortcomings and uncertainties. It is important that the discussion does not fall out as a simple summary of what the figures show.

Write enough to say what you need to say. Don't think "the report feels short, better throw in some extra figures." If you can say the same thing in fewer words, do so. Short reports make for happy graders. Do not exceed 10 pages.

Be sure to reference any source you use. The report should be readable and understandable on its own, but there is no need to reproduce for example derivations of equations from your sources; a citation is enough.

Figures are an important part of the report, but only those that substantially contribute to your analysis should be included. Make sure that each figure is well designed with informative captions (not just "Fig. X shows how quantity A depends on quantity B"). If you find it hard to do this, you probably are not clear on why you include an figure, so cut it out.

Most importantly, use your own judgement and try to write a report you would like to read.

Evaluation criteria

The project grade will be based on your report, but the presentation might be used as input for deciding on whether to tip a grade upwards or downwards. Criteria that will be considered are:
  • Is the project report well structured (see above)?
  • Does the project have a clear research question?
  • Does the project answer the initial or iterated research question?
  • Are the methods and analysis appropriate for convincingly answering the research question?
  • Is there a clear coupling between the model, the research question, and conclusions?
  • Are the figures included informative with descriptive captions?
  • Is the length of the report appropriate for the story it tells?
Note that the research question does not have to be answered in the affirmative. A negative result is equally valid as long as an analysis is carried out that properly explains the negative result and what eventually would work better.

After you get your grades, it will be possible to make a revised submission to raise your grades. The feedback from your tutor should provide you with the necessary input for achieving a higher grade.

6. Project ideas

Here are a few project titles from Simulation of Complex Systems 2013:

  • Predator avoidance in schools of fish
  • Cartel formation in Bertrand’s model of oligopoly
  • Simulation of escape panic behaviour
  • Public services and segregation
  • Disease dynamics in the informative society
  • The size-rank law and urban growth
  • Optimal resource allocation using genetic algorithms
  • Traffic light and roundabout performance evaluation with IDM/MOBIL

There are lots of interesting papers to be found under publications (and working papers) at the Santa Fe Institute (SFI). Many ideas that have been brought up and discussed at the Complex Systems seminar can be developed into projects in this course. Also, projects that some of you have done in earlier courses, like Stochastic optimization algorithms, can be continued and developed into new projects here. I also recommend that you search the web; there are so many good papers and ideas to be found out there.

Many of the links below point to papers describing the investigation of a certain model. You may use such a model a starting point for the project, which usually means that you have to do your own implementation. Then you may critically test the limits of the model. What are critical assumptions and parameter values? To what extent are the conclusions drawn by the authors general, etc?

Social systems

Societal structure - hierarchies, norms, institutions. The online Journal of Artificial Societies and Social Simulation provides some ideas and papers.

Voting models

The results of a democratic voting process may heavily depend on the voting system. Explore this by modelling a population of people voting. Read "The complexity of voting" by David A. Meyer.

Modelling segregation in urban areas

See, for example, relevant chapters in Schelling's book on micromotives and macrobehaviour (at Kristian Lindgren's office).

Evolution of strategies in game-theoretic models

There are several possible ideas that could be developed into projects here. Kristian Lindgren and Anders Eriksson have a set of papers, most of them dealing with the Prisoner's Dilemma game, that could serve as a starting point or for inspiration. There are several examples of games in Herbert Gintis' book "Game Theory Evolving" that can be developed into interesting multi-agent models. There are several models (some with source code) presented at Axelrod's "Complexity of Cooperation" web site.


a) The ultimatum game. Make a critical analysis or a modification of the model presented in Science: M. A. Nowak, K. M. Page, and K. Sigmund: "Fairness versus reason in the Ultimatum Game", Science 289, 1773-1775 (2000).
b) Evolution of Cooperation through Indirect Reciprocity, see Leimar, O. and Hammerstein, P. (2001), Proc.Royal.Soc.Lond.B, 745–753. (online text version). This is a reply and critisism of a paper by Nowak and Sigmund i Nature.

Panic and other types of basic group behaviour

How to model the group behaviour in panic situations. See link related to Nature paper Simulating dynamical features of escape panic by Helbing et. al.

Networks and infrastructure systems

Traffic simulation
Make a realistic model of a small part of Göteborg's traffic system. Model a highway with some exits, include tunnel, etc... Very nice Java simulations are available on Helbing's page (two-lane version). A quantitative analysis of how traffic flow is affected by road characteristics, could be a suitable goal for one project.

City growth simulation
How will Göteborg develop in the future? Or, from the map of 1809, how could Göteborg have developed to today? See Project Gigalopolis for an example on how such models can be constructed. We also have a number of papers in the Complex Systems Group, see our project description. One project may involve exploring how different local rules can give rise to different types of growth.

Small world networks
See book and papers by Duncan J. Watts (Small Worlds: The dynamics of networks between order and randomness, Princeton Univ. Press, 1999). A very good review by Mark Newman is available here. There are a lot of new papers published on these ideas.

Economic systems

Artificial markets, software agents, etc.
Lots of information to be found under Leigh Tesfatsion's web page on Agent-Based Computational Economics. She also offers a number of links to software useful for multi-agent modelling, and she offers a long list of suitable student projects (covering a lot of complex systems), see at the bottom of the syllabus page for her course).


a) A simple stock market with a stock (or two).
b) Cournot duopoly, or a simple oligopoly model; see, for example, Fudenberg & Tirole p.14.
c) A Sugarscape inspired model, see Epstein's and Axtell's book.

If you are interested in working on software agents, check the online tutorial by Patty Maes from Software Agents Group at MIT Media Laboratory.

Natural systems, ecosystems

Pattern formation in chemical, biological, and ecological systems.


a) Make a PDE model of a simple chemical system that exhibits pattern formation (2X -> 3X model, see Science paper).
b) Host-parasitoid interactions may lead to complicated space-time patterns; Hassell has done a lot in this area, see, e.g., Hassell, M.P., H.N. Comins, and R.M. May. 1991. Spatial structure and chaos in insect populationd dynamics. Nature 353: 255-258 and Pacala, S., M.P. Hassell, and R.M. May. 1990. Host-parasitoid associations in patchy environments. Nature 344: 150-153.
c) Spatial dynamics in a host-pathogen system, see, for example, paper by G.M. Hood with model description.

Modelling population dynamics - comparing agent-based models with ODEs

Make an agent-based model of a few variations of simple one and two species population dynamics and compare the behaviour with simpler models in terms of ordinary differential equations. When does an ODE work as a good approximation to the more complicated agent-based model?

Ecosystems in fragmented environments

Build an individual based model of a species that lives in a fragmented environment.

Decentralized dynamics of animal flocks

Construct a model in which various types of flocking behaviour may evolve.

Global issues, resources, and the environment

See, for example, the link to Beyond the Limits (incl Mac program and hints on how to get the model for PC)

How many will there be 2050? Try to make a projection of the world population growth to year 2050. There are several approaches possible, see for example paper in Nature by Lutz et al. (For fun, see web page on "world population since creation" with figure that shows a 9 billion population before the flood...)

Modelling resource use in multi-agent systems; tragedy of the commons

Fishery models: Make a model of fishermen harvesting a population that follows a simple dynamics model. Model the fishermen as adaptive agents. Think on how to model their behaviour. How do they adapt their strategies to each other and to the resource?

Artifical worlds and virtual reality

"Physical" simulations in artificial worlds. Here one may use the software package, breve, that Jon Klein has developed in his Master's thesis (runs under MacOSX).

a) Make models of and simulate flock behaviour in 2D or 3D worlds. Follow links from breve; see also Craig Reynolds web page on Boids.
b) Simm's evolving creatures, see, e.g., "Evolving 3D Morphology and behaviour by competition", Artificial Life 1, 353-372 (1995).

Complex system games

Use complex systems ideas in order to design simple but tricky games (either computer-human or human-human). The first versions of the game Blobity of Catchy Software was a project of this course in 2000.

 

Published in Course page
Page 1 of 4