|
Course Description Schedule Assignments Reading List Paper Reviews Coding Exercise Final Projects Fall04 Staff
DIVISION OF ENGINEERING AND APPLIED
SCIENCES
HARVARD UNIVERSITY
CS 266: Biologically-inspired Distributed and Multi-agent SystemsFall 2006 |
|
|
| Announcements |
This year we had many very interesting final projects, some of which are listed here. You can read the final papers here.
| Course Description |
Instructor: Prof. Radhika Nagpal (rad@eecs)
Class Time: Tues/Thurs 1-2:30
Location: MD 221
Teaching Fellows: Dan Yamins (yamins@fas), Ankit Patel (abpatel@fas)
Office Hours: Radhika: Tues 3-5pm, MD235, Dan and Ankit: Monday 5-7, MD 238
A colony of cells cooperates to form a multicellular organism under the direction of a common genetic program. A swarm of bees cooperates to construct a hive. Emerging technologies are making possible a new class of large-scale, embedded, distributed systems --- vast sensors networks for habitat monitoring and smart buildings, programmable materials with embedded sensors and actuators, swarms of tiny robots and shape-changing robots with thousands of modules, even genetically-engineered cells as new computational substrates. These examples raise a fundamental question for the organization and design of computing systems: How do we engineer robust behavior from the cooperation of vast numbers of unreliable parts? Biology hints that there may be significant power to be achieved from building things out of cheap, imprecise parts with limited life.
This class will survey the state of the art in bio-inspired approaches to designing robust collective behavior in different domains. A unifying theme amongst these domains is the desire to construct robust systems consisting of many individually unreliable nodes, that produce complex but predictable global behavior. We will focus on algorithms, methods for analysis, and programming paradigms for engineering self-organizing systems. Topics include: swarm intelligence and applications, amorphous computing and self-assembling materials/robots, immune and evolution inspired approaches, and theoretical approaches to global-to-local derivation. The class will be primarily based on discussions of research papers, along with a final project and assignments (see below).
Prerequisites:
This class is geared toward graduate students at all levels as well as advanced undergraduates. Students should have a familiarity with systems (e.g. operating systems CS 161 or computer networks CS 143) and algorithms (e.g. CS 124). Experience reading research papers is useful. Enrollment may be limited to 20.Textbook:
Self-Organization in Biological Systems, Camazine et al, Princeton Studies Complexity, 2001
(at Amazon, note that the paperback version is significantly cheaper).
Link to simulations and illustrations from the book.
| Assignments |
This course will involve reading research papers, leading and participating in class discussions, completing a coding exercise, and a final project.
- Paper reading and in-class discussion: For each class, there will be one or two research papers assigned which will be discussed in class.
- Paper reviews: Before each class, you will write a short review for each paper assigned that week. The review should consist of: 1 summary paragraph, 1 major strength, 1 major weakness, and 1 question. Reviews are due MIDNIGHT the day before class; post your review here and read other people's reviews.
- Class presentation: You will be expected to present a paper and lead the class discussion in at least one lecture.
- Coding Exercise: There will be one coding exercise during the theory section of the course.
- Final project: Finally, everyone will undertake a final project in groups of 2. Proposals will be due at the end of the first month. There will be several suggested projects, however you are also encouraged to pick a general area that interests you and formulate a project within that area. You can also take a look at projects from fall 2004. At the end of the term, everyone will present projects in class and prepare a written project report. This report will be due by the last day of classes (i.e. projects may not extend into the reading period).
More details on each of these aspects will be presented at the first class. The final grade will take into account each of these aspects.
| Tentative Schedule |
| Date | Topic (Reading and Assignments) | Presenter |
| Tu 9/19/06 |
Course Introduction (2 weeks) Overview: Self-organizing Systems |
Radhika lecture1 |
| Th 9/21/06 | Overview: Swarm Intelligence and Self-organization [R1], [R2] | Radhika lecture2 |
| Tu 9/26/06 | Overview: Amorphous Computing and Global-to-local Compilation [R1], [R2] | |
| Th 9/28/06 |
---Class Picnic--- |
|
| Tu 10/3/06 |
Swarm Intelligence (3 weeks) Ant foraging and network routing [R1], [R2] |
Roy Shi, Ben Smith session4_part1 session4_part2 |
| Th 10/5/06 | Collective sorting and division of labor models [R1], [R2] | Fabiano Romeiro, Yuriy Vasilyev session5 |
| Tu 10/10/06 | Collective construction: termites to robots [R1], [R2] | Jimmy Sun, Jie tang session6 |
| Th 10/12/06 | Firely Fly Synchronization [R1], [R2] | Zak Stone, Jeff Lau Session 7 |
| Tu 10/17/06 |
Flocking birds and automous vehicles
[R1], [R2]
Assignment 1: Project Proposal due (2 pages) [guidelines] |
Sam Lipoff, Patrick Ohiomoba, Prabhas Pokharel session8 |
| Th 10/19/06 |
Amorphous Computing (3 weeks) Models of morphogenesis and embryo development [R1], [R2] |
Radhika lecture4 |
| Tu 10/24/06 | ---Guest Lecture: James McLurkin (Swarms of Mobile Robots)--- | guest-lecture |
| Th 10/26/06 | Programmable self-assembly and scale-invariance [R1], [R2] | Tyler Gibson, Mike Karpelson session11_part1 session11_part2 |
| Tu 10/31/06 | Programmable self-assembly and self-repair [R1], [R2] | Panos Kouretas, Shelten Yuen, Jean Yang session12_part1 session12_part2 session12_part3 |
| Th 11/2/06 | Reconfigurable Robots: cellular automata and graph grammars [R1], [R2] | Julius Degesys, Charlie Frogner session13 |
| Tu 11/7/06 | Gradients in pervasive computing [R1], [R2] | Chit-Kwan Lin, Ian Rose session14_part1 session14_part2 |
| Th 11/9/06 |
Theory of Global to Local (2 weeks) Constructing local rules for equigrouping [coding exercise page] |
Dan Yamins |
| Tu 11/14/06 | Constructing local rules for general patterns | Dan Yamins
lecture16 |
| Th 11/16/06 | Necessary conditions and local checkability | Dan Yamins
lecture17 |
| Tu 11/21/06 |
---Guest Lecture: Prof. Drew Endy (MIT, Synthetic Biology)---
Assignment 2: Project Update due (1 page) [guidelines] |
|
| Th 11/23/06 | ---Holiday: Thanksgiving--- | (no class) |
| Tu 11/28/06 | Symmetry, polarity emergence, and other related problems | Dan Yamins |
| Th 11/30/06 | Immune and evolutionary-inspired approaches (2 weeks) Immune system and evolution as distributed search [R1], [R2] |
Ece Kamar, Elif Yamangil Session 20 |
| Tu 12/5/06 | Immune-inspired approaches to computer security [R1], [R2] | Francois-Xavier Willems, Ian Fischer Session 21 |
| Th 12/7/06 | Evolving agent morphology and control [R1], [R2] | Earl Solis, Ilan Wapinski |
| Tu 12/12/06 | Evolving multi-agent systems [R1] [R2] | Sven Seuken, Chih-Han Yu Session 23 |
| Th 12/14/06 | Project Presentations | |
| Tu 12/19/06 | Project Presentations | |
| Mon ??? | Final papers due | - |
| Reading List |
The assigned papers are marked as [R]. The remaining links point to more examples of work and reviews that are helpful for presentation and research projects. Not all papers are available as pdf, those that are not will be made available in class.
Textbooks
For some of the subjects, there are textbooks that give a higher-level view of the subject. These are useful if you are presenting or want to read more about the area. We will maintain a "class library" of these books, so you can talk to the TF and check out the books for short periods of time.
Swarm Intelligence
| Staff |
Radhika Nagpal (Lecturer)
rad at eecs harvard edu
Office: 235 Maxwell Dworkin
Phone number: 496-6434
Daniel Yamins (Teaching Fellow)
yamins at fas harvard edu
Office: 238 Maxwell Dworkin
Ankit Patel (Teaching Fellow)
abpatel at fas harvard edu
Office: 238 Maxwell Dworkin