CSCE 689-604: Special Topics in Multi-Robot Systems

Instructor: Dr. Dylan Shell

Fall 2009

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 presented by an assigned student, and will be discussed and critiqued by everyone in the class. The students presenting a paper in a given class should prepare a clear 25-minute presentation. This presentation should assume that the audience has read the paper, and not spend more than about 5 minutes summarizing it. Most of the presentation should be spent on discussing 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), will bring to class a report up to one page long (no more), consisting of the following parts:

1. A paragraph briefly summarizing the contributions of the paper (copies of the abstract and/or intro and/or conclusions will not do);
2. A paragraph critiquing the paper. The critique should take the form of addressing the strengths and weaknesses of the paper, comparing it briefly to other work, especially other papers read in class, as relevant, etc.

The 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. Further details can be found in this rubric which outlines aspects used in assessing the reports.

All summary reports should include: the student's name, and the title and authors of the paper being summarized and critiqued. Hand-written or late reports will not be accepted. Each paper report should be turned in on a separate piece of paper, i.e., do not bundle multiple reports due on a given day into a single report, turn them in as separate stand-alone reports.

In summary, for each class, you should bring:

1. Printouts or digital versions of the papers being discussed;
2. A printed summary report for each of the papers;
3. A presentation, if you are presenting one of the papers;
4. 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

Principles of Control Architectures

"Modeling Adaptive Autonomous Agents", Pattie Maes, Artificial Life, 1(1-2), MIT Press, pp. 135-162, 1994.

(Sept 8) Abhishek Soni

Group Behavior: Minimalist Control

"On why better robots make it harder", T. Smithers, From Animals to Animats, Simulation of Adaptive Behavior, pp. 64--72, 1994.

(Sept 10) Benjamin Fine

"Stigmergy, self-organization, and sorting in collective robotics", Owen Holland and Chris Melhuish, Artificial Life, 5(2), pp. 173--202, 1999.

(Sept 10) Phillip Coleman

"Cooperative transport by ants and robots", C. Ronald Kube and Eric Bonabeau, Robotics and Autonomous Systems, 30(1-2), pp. 85--101, 2000.

(Sept 15) Tanushree Mitra

Group Behavior: Strategy

A formal framework for the study of task allocation in multi-robot systems", B. Gerkey and M. Mataric', International Journal of Robotics Research, 23(9):939-954, September 2004.

(Sept 22) Vasant Srinivasan

"Distributed Mobile Robotics by the Method of Dynamic Teams", Jim Jennings and C. Kirkwood-Watts, Proceedings of the International Symposium on Distributed Autonomous Robotic Systems, Karlsruhe, Germany, May 1998.

(Sept 24) Yong Song

"Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork", Peter Stone and Manuela Veloso, Artificial Intelligence, 110(2), pp. 241-273, 1998.

(Sept 24) Lantao Liu

Optimal Assignment Problem

Group Behavior: Market-based methods

"Market-Based Multirobot Coordination: A Survey and Analysis", M.B. Dias, R. Zlot, N. Kalra, and A. Stentz, Proceedings of the IEEE, 94(7), July 2006 pp. 1257-1270.

(Oct 1) Narayana Penukonda

Task Domain: Motion Control, Planning, Formations

"Safe Multirobot Navigation Within Dynamics Constraints", J. R. Bruce and M. M. Veloso, Proceedings of the IEEE, 94(7), July 2006 pp. 1398-1411.

(Oct 6) Zohreh Keshavarzbagheri

"Social potential fields: A distributed behavioral control for autonoomous robots", J. Reif and H. Wang, in International Workshop on Algorithmic Foundations of Robotics (WAFR), pp. 431-459, 1995.

(Oct 8) Dr. Shell

No class on Oct 13!

Task Domain: Tracking

"Dynamic Sensor Planning and Control for Optimally Tracking Targets", J. Spletzer and C. J. Taylor, International Journal of Robotics Research, November 2002.

(Oct 15) Shawn Kristek

Task Domain: Predator-Prey

"Coevolving Predator and Prey Robots: Do `Arms Races' Arise in Artificial Evolution?", S. Nolfi and D. Floreano, Artificial Life, Vol. 4, No. 4, Pages 311-335, 1998.

(Oct 20) Brittany Duncan

Automated Synthesis

"Building multirobot coalitions through automated task solution synthesis", Lynne E. Parker, Fang Tang, Proceedings of the IEEE, 94(7), July 2006 pp. 1289-1305.

(Oct 22) Jung-Hwan Kim

Analysis

"Minimalism + Distribution = Supermodularity", B. Donald, J. Jennings, and D. Rus, Journal of Experimental and Theoretical AI, 9(20-3), 1997, pp. 293-321.

(Oct 27) Dr Shell

"Analysis of Dynamic Task Allocation in Multi-Robot Systems", K. Lerman, C. Jones, A. Galstyan and M. Mataric', International Journal of Robotics Research, 25(3), March 2006, pp. 225-241.

(Oct 29) Negar Rashidi

"Hierarchic Social Entropy: An Information Theoretic Measure of Robot Group Diversity", T Balch, Autonomous Robots, 8(3), June, 2000.

(Nov 3) Dr. Shell

Biological Inspirations

"How multirobot systems research will accelerate our understanding of social animal behavior", T. Balch, F. Dellaert, A. Feldman, A. Guillory, C. L. Isbell, Jr., Z. Khan, S. C. Pratt, A. N. Stein, and H. Wilde, Proceedings of the IEEE, 94(7), July 2006 pp. 1445-1463.

(Nov 5) Dongkun Kim

Coordination Primitives

"Towards a Catalog of Biologically-inspired Primitives," Radhika Nagpal, Workshop on Engineering Self-organising Applications, Autonomous Agents and Multiagents Systems Conference (AAMAS), 2003.

(Nov 10) General Discussion

Simulation

"Noise and The Reality Gap: The Use of Simulation in Evolutionary Robotics" Nick Jakobi, Phil Husbands and Inman Harvey, Advances in Artificial Life: Proc. 3rd European Conference on Artificial Life, 1995.

(Nov 12) General Discussion

No class on Nov 17, Project Work.

No class on Nov 19, project work.

Nov 24: Meeting in the Lab to discuss project progress.

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:-

1. Introduction to AI Robotics, Robin Murphy, MIT Press, 2000.
2. Autonomous Robots, George Bekey, MIT Press, 2006.
3. Probabilistic Robotics, Sebastian Thurn, Wolfram Burgard and Dieter Fox, MIT Press, 2005.
4. The Sciences of the Artificial, Herbert Simon, MIT Press, Third edition, 1996.
5. 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 earlier mini-project, which will involve demonstration of a simple on 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.

Mini-Project

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 mini-project

Final Project

Looking at teaming? This is what your classmates are looking for in collaborators.

A list of recommended individual projects will be provided by the instructor on request. (Some suggestions are here.) Students will have a fair degree of flexibility in that they can adapt those provided or even propose their own projects. Team projects are also possible, but with the following provisos: 1) teams must not exceed two students, 2) the project scope must be twice that of individual projects, 3) the individual contribution of each team member must be clear, and 4) individual final reports must be turned in. After proposal documents are submitted, feedback will be provided as well as a decision. Students (or groups) must have confirmation of an acceptance of the proposal. If the project proposal deadline passes without an accepted project proposal, the student must submit one of the original proposed projects.

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. 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:-

Assessment and Examinations

Grades will be based on the following components:-

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. All students are granted two paper summaries that they can miss without penalty. Use those two wisely. 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.