CSCE 689-600: Special Topics in Multi-Robot Systems
Instructor: Dr. Dylan Shell
| Office | : | HRBB 333B |
| Phone | : | (979) 845-2369 |
| : | dshell_at_cs.tamu.edu | |
| Web | : | http://robots.cs.tamu.edu/dshell |
| Office hours | : | Thursdays after lectures or by email appointments |
Spring 2011
| Lecture Time | : | Tuesdays & Thursdays 5:30pm-6:45pm |
| Lecture Location | : | HRBB 210 (and 320) |
Course Description
Recent years have seen a great increase in the volume of research conducted into multi-robot systems. This course covers the state-of-the-art in control and synthesis techniques for multi-robot systems. Starting initially from motivations and definitions, students will study several important coordination methods and the ideas that have inspired them. The course balances study of fielded systems and applications with analysis of algorithms and formalisms. Students will use physical robots to design, implement and demonstrate multi-robot controllers.
Detailed Description
This course is a seminar-style survey of issues and approaches to control and coordination in multi-robot systems. Although the subject area is distributed robotics, it is an explicit goal of this course to advance students' critical thinking and communication skills. This is achieved through discussions, regular presentations and report writing.
Students will read original papers within the field, tracking the development from early seminal works, quickly gaining breadth through surveys, and sample particular approaches through representative systems. The discussion will focus on the multi-scale aspect of cooperative phenomena, i.e., high-level coordination and planning versus local real-time control and interactions. Throughout the semester, the course will consider both demonstrated multi-robot systems and biological and/or natural systems that have served as inspiration for these systems.
Students are expected to read all of the required readings. Each of the papers will be discussedand critiqued by everyone in the class, but one student will be assigned the lead for each paper. The students leading discussion of the paper in a given class should prepare a clear 10-minute presentation. This presentation should assume that most of the audience has read the paper, and not spend more than about 5 minutes summarizing it. Most of the presentation should be spent on analyzing the paper, its strengths, weaknesses, any points needing clarification, and addressing any questions. Students are encouraged to include videos and any other interesting supporting information in support of the presentations. For lectures in which additional readings are provided, these are optional to the class, but the presenters are expected to have some familiarity with the material.
Presentations require a PowerPoint/Foils presentation to show from the students' laptops. An LCD projector is available in the meeting classroom for the paper presentation it is the presenter's responsibility to provide the presentation on a laptop that is compatible with the projector, and cables to connect to it. Please plan ahead to address logistical questions.
For each paper being covered on a given day, each student (whether presenting or not), should bring to class their version of the paper, including notes that they have made to themselves. They should have notes, including several questions and critiques which they can contribute to the discussion. The best way to have a good participation grade is to have serious, thoughful criticism of the paper.
The final project reports should be written in the same formal tone as the papers read in class; this means no contractions, jokes, or otherwise inappropriate expressions for a technical report. Eloquent prose and literary style are encouraged, as is originality of content, but keep in mind that these reports are one type of practice for technical writing.
In summary, for each class, you should bring:
- Printouts or digital versions of the papers being discussed;
- A presentation, if you are presenting/leading the discussion of one of the papers;
- Your personal summary, thoughts on and questions regarding the papers you read;
- Great enthusiasm for discussing all of the papers.
Prerequisites
No particular course is a prerequisite, however, students will required to be proficient programmers in a language such as Java, C or C++. Familiarity with common Open Source Software and GNU/Linux will be beneficial. Students will need to demonstrate critical thinking and broader scientific skills (such as technical writing and presentation) throughout the course. Enrollment is open to all graduate students and undergraduate computer science seniors that are deemed competent.
Learning Goals
The following are the learning goals of this course:-
- Students will gain an understanding of state-of-the-art in multi-robot control and coordination techniques.
- Students appreciate the development and process by which the state-of-the-art has been arrived at.
- Students will hone critical thinking and communication skills (including technical discussion, presentation and writing).
Syllabus
Introduction, Motivation and Early Demonstrations
"More Is Different", P. W. Anderson, Science, Vol. 177, No. 4047. (Aug. 4, 1972), pp. 393-396.
"An imitation of life", W. Grey Walter, Scientific American (1950) 182(5): 42-45.
"A machine that learns'', W. Grey Walter, Scientific American (1951) 185(2): 60-63.
(January 20) Discussion lead by Shell
- "Vehicles. Experiments in Synthetic Psychology", V. Braitenberg, The MIT Press, 1984.
- "The first biologically inspired robots", O. Holland, Robotica, 21, pp. 351-363, 2003.
Principles of Control Architectures
(Jan 25) Jill Greczek
Overviews
(Read both.)"Multiple Mobile Robot Systems", Lynne E. Parker, Chapter 40 in Springer Handbook of Robotics, Bruno Siciliano and Oussama Khatib (eds.), 2008. (Use electronic resource)
(Jan 27) Shuvra Nath
"Networked Robots", Vijay Kumar, Daniela Rus and Gaurav S. Sukhatme, Chapter 41 in Springer Handbook of Robotics, Bruno Siciliano and Oussama Khatib (eds.), 2008. (Use electronic resource)
(Jan 27) Autumn Breese
Feb 2: Class demonstrations of docking exercise.
Group Behavior: Minimalist Control
(Read two of these three.)(Feb 4) Jesus Rico
(Feb 4) Raymond Lin
(Feb 4) Asish Ghoshal
(Read two of these.)(Feb 8) Young Ho Kim
(Feb 8) Aditya Mahadevan
(Feb 8) Liaoyuon Huo
- See book 5. (Available in digital form via the library.)
Group Behavior: Strategy
(Feb 10) Asish Ghoshal
Read one of the following two:(Feb 10) Raymond Lin
(Feb 10) Jill Greczek
Optimal Assignment Problem
Group Behavior: Market-based methods
(Feb 17) Aditya Mahadevan
- See book 4.
Task Domain: Motion Control, Planning, Formations
(Feb 22) Shuvra Nath
(Feb 22) Autumn Breese
Task Domain: Tracking
(Feb 24) Jesus Rico
Mar 1: Task-allocation assignment due.
Task Domain: Predator-Prey
(Mar 3) Liaoyuan Huo
Mar 8: Presentations of Proposal Ideas.
Automated Synthesis
(Mar 11) Jesus Rico
Mar 11: Project groups formed, and have spoken with Dr Shell about your project idea.
Mar 22: No class. Work on project proposal document!
Analysis
(Mar 24) Raymond Lin
Mar 24: Project groups finalized and project proposal submitted.
(Mar 29) Shuvra Nath
(Mar 31) Jill Greczek
- "On Information Invariants in Robotics." B. Donald, Artificial Intelligence --- Special Volume on Computational Research on Interaction and Agency, Part 1, 72(1-2):217-304, January 1995.
- "Communication Complexity of Multi-Robot Systems", E. Klavins, Algorithmic Foundations of Robotics V, volume 7 of Springer Tracts in Advanced Robotics, 2002, pp. 275-292.
Apr 5: Guest Lecture
Apr 7: Project work
Biological Inspirations
(Apr 12) Young Ho Kim
- "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem", M. Dorigo and L. M. Gambardella, IEEE Transactions on Evolutionary Computation, 1(1): 53--66, 1997.
- "A Distributed Feedback Mechanism to Regulate Wall Construction by a Robotic Swarm", Robert L. Stewart and R. Andrew Russell, Adaptive Behavior, 14(1), 2006, pp. 21-51.
Apr 12: Preliminary project demonstration
Coordination Primitives
(Subject to change depending on class interest.)(Apr 14) TBD -- in refereed review form
Simulation
(Subject to change depending on class interest.)(Apr 19) TBD -- in refereed review form
Apr 19: Draft Report Due
Minimalism: Analysis
"Comparing the Power of Robots", J. O'Kane, S. LaValle International Journal of Robotics Research, volume 27, no 1, 2008, pp. 5-23.
Apr 26: Open discussion
Apr 28: Work on projects
Mar 3: Final Presentations (10 minutes per group)
Mar 6th (11:59 PST) Final Papers due (one per group)
Learning Outcomes
By the end of the course, the student should be able to:-
- Understand and articulate the meaning of embodiment, situatedness and feedback in distributed robotics systems.
- Name several hard open-problems in the area, and understand why they are hard.
- Explain the dichotomy that currently exists between implicit and explicit coordination mechanisms, and provide examples.
- Give examples of how biology, operations research, and economics have inspired solutions to distributed robot problems.
- Position novel research within area of multi-robot systems.
- Give a technical talk.
- Write a high-quality review of multi-robot systems conference paper.
Texts
The readings are cited in full. Digital versions should be either easy to find, or available from the class website.
No textbooks are required. However students (and particularly presenters) may need to read more widely to gain a thorough understanding of the papers. The following books may be useful in this regard:-
- Introduction to AI Robotics, Robin Murphy, MIT Press, 2000.
- Autonomous Robots, George Bekey, MIT Press, 2006.
- Probabilistic Robotics, Sebastian Thurn, Wolfram Burgard and Dieter Fox, MIT Press, 2005.
- The Sciences of the Artificial, Herbert Simon, MIT Press, Third edition, 1996.
- Swarm intelligence: From Natural to Artificial Systems, Eric Bonabeau, Marco Dorigo, and Guy Theraulaz, MIT Press, 1999.
Course Projects
The principles learned in this class will be applied to a final experimental project that will include an implementation on physical robot hardware. In addition to this, there is an early (very early!) exercise, which will involve demonstration of simple navigation of a single physical robot.
It is expected that these aspects of the course will take a significant portion of each student's time. Students are strongly advised to start early so as to ensure completion. The reading requirements of the class are specifically paced so as to enable students to tackle interesting projects.
Docking Exercise
This forms an initial programming exercise in order to enable students to get familiar with the hardware platform. The instructor will provide a simple feedback behavior which students are to individually implement and demonstrate to the satisfaction of the instructor.
Details on the exercise are here
Task-Allocation Assignment
This is an assignment requiring students to formalize an optimization-based framework for task-allocation which is a generalization of the assignment problem described in class.
Project Ideas Presentation
The final project is expected to be a demonstration of complex coordinated group behavior. The purpose of these presentations is to have the class propose interesting ideas and to look out for potential project partners. By coming up with potential project ideas before groups are formed or final projects have been fixed, the hope is that some wild ideas can be proposed. A list papers from which ideas for projects can be found is here.
Each student is expected to propose an idea for a project with sufficient scope for two students to work on it. The project should be motivated and an potential approach described. Ideally, metrics for project success should be outlined.
Final Project
Students will have a fair degree of flexibility in that they can propose their own projects. Ideally it will reflect something they found most interesting in the course. The "Project Ideas Presentation" given by fellow students should be a good source for project topics. Team projects are encouraged with the following provisos: 1) teams must not exceed three students, 2) the project scope must scale appropriately, 3) the individual contribution of each team member must be clear. After proposal documents are submitted, feedback will be provided as well. Do not wait until this deadline to speak with the instructor about your project ideas. Groups must obtain confirmation of an acceptance of the proposal.
Each project is expected to be an implementation of coordinated group behavior involving a complex interaction (e.g., cooperation on a task, competition, and/or adaptation) implemented on the iRobot Create hardware. Office hours will be used to iterate on proposed projects in person.
Final projects will be presented to the class on scheduled end-of-semester presentation days. Project presentations will be alloted 20 minutes, followed by questions from the class. Live demos are encouraged but not required.
A detailed final paper is a required part of the course project. The class A hardcopy of the report is due on the last day of project presentations. Specification of the final paper will be provided in class.
The following are important project dates:-
| 20 Jan | : | Hardware provided during class. |
| 2 Feb | : | Docking demonstration. |
| 10 Feb | : | Task-allocation assignment handed out. |
| 1 Mar | : | Task-allocation assignment due. |
| 8 Mar | : | Presentation of proposal ideas. |
| 11 Mar | : | Project groups formed. |
| 24 Mar | : | Finalization of projects groups, along with project proposal draft. |
| 12 Apr | : | Initial demonstration of project |
| 26 & 28 Apr | : | Project presentations |
| 28 Apr | : | Final demonstration of project |
| 3 Mar | : | Final project report due |
Project Presentation Roster
Assessment and Examinations
The first set of presentations are scheduled for 5:30-7pm on April 26 and 28. The division of the groups will appear here once it has been finalized.
Grades will be based on the following components:-
| Class Participation | : | 30% |
| Docking Exercise | : | 10% |
| Task-Allocation Assignment | : | 10% |
| Proposal Idea Presentation | : | 10% |
| Final Project | : | 40% |
Notice, in particular, the significant weight given to class participation. As a seminar-style course, students are expected to have several serious critiques of the paper prepared for class and to miss few sessions. Make-ups for assignments and projects will be given only under circumstances beyond student's control (a university sanctioned excuse). Unless circumstances are particularly extreme, it is expected that an absentee presenter shall find a suitable replacement. Prior arrangements with the instructor must be made when feasible and official verification of circumstances necessitating the absence will be required.
Please seek assistance immediately if you are having difficulty with the course. Help can only be made available from the instructor and the teaching assistants if they are notified promptly.
Students with Disabilities
The Americans with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact Disability Services, in Cain Hall, Room B118, or call (979) 845-1637. For additional information visit http://disability.tamu.edu.
Academic Integrity
This course has a zero-tolerance policy to academic misconduct of any kind including: cheating, fabrication, falsification, multiple submissions, plagiarism. Ignorance of the rules does not exclude any student from the requirements or the processes of the Honor System. Definitions and further information is at http://www.tamu.edu/aggiehonor. Note in particular the seriousness of the disciplinary action.
Task-Allocation Assignment Posted