CS 980-01: Topics in Multi-Agent and Multi-Robot Systems

Who: Professor Amato
When: Tuesday, Thursday  3:40pm - 5:00pm
Where: Kingsbury N233


In this class, students will learn about the state of the art in mult-agent and multi-robot systems. Multi-agent systems are those with more than one decision-maker (or "agent") and these agents may be cooperative or self-interested.  We will discuss methods for both problem types, including task allocation (e.g., auction-based mechanisms), swarm optimization and ways of dealing with partial information (e.g., noisy senors or other limited information) and limited communication. We will be reading recent research papers that describe and compare the various methods as well as a number of application papers. Although we will focus on robotics, we will read about other application domains such as video games and networking.

Reading responses: For each paper, students should write a short (<1 page) response. See "how to read a paper" for guidelines and how to structure your responses. Also, check out the review guidelines for RSS.

Projects: Students will write research papers on a topic of their choosing. Topics can be related to any of the material we cover in class and be theoretical or experimental. More details on projects will be discussed in class.

Students leading the discussion: Later in the semester, students will each choose 1 paper to present and will lead the discussion for that class. Papers must be relevant to the material covered in this class and approved beforehand.

Prerequisites: Previous exposure to AI planning, Game Theory and/or Robotics is helpful, but not necessary

Tentative Schedule

Date Assignment Optional material
9/1 Overview
No response needed
9/3 Chap. 1 of Multiagent Systems, 2nd edition, edited by Weiss (Sections 1-2 only)
Multiagent Systems, 2nd edition edited by Weiss
9/8 Chap. 1 of Multiagent Systems, 2nd edition, edited by Weiss (Sections 3-4)
9/10 Coordinated Multi-Robot Exploration by Burgard, Moors, Stachniss and Schneider
9/15 Planning and Acting in Partially Observable Stochastic Domains by Kaelbling, Littman and Cassandra (only up to 4.4!) POMDPs for dummies, Chapter 3 of Reinforcement Learning: An Introduction, Chapter 17 of AI: A Modern Approach
9/17 Decentralized Control of Partially Observable Markov Decision Processes by Amato, Chowdhary, Geramifard, Ure and Kochenderfer Cooperative Decision Making, Chapter 11 in Weiss, Decentralized POMDPs, the Dec-POMDP page, MAS plan website
9/22 [ Dec-POMDP discussion ]
9/24 Planning for Decentralized Control of Multiple Robots Under Uncertainty by Amato, Konidaris, Cruz, Maynor, How and Kaelbling video for paper, Policy Search for Multi-Robot Coordination under Uncertainty (with videos: BeerBots and CSAIL)
9/29 TCP ex Machina: Computer-Generated Congestion Control by Winstein and Balakrishnan
10/1 Markov Games as a Framework for Multi-Agent Reinforcement Learning by Littman Chapter 10 in Weiss
10/6 If Multi-Agent Learning is the Answer, What is the Question? by Shoham, Powers and Grenager
10/8 High-level Reinforcement Learning in Strategy Games by Amato and Shani
10/13 Editorial: Advances in Multi-Robot Systems by Arai, Pagello and Parker
10/15 Cooperative Multi-Robot Box-Pushing by Matarić, Nilsson and Simsarian
10/20 A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems by Gerkey and Matarić Slides from an overview talk by Dylan Shell, A newer survey
10/22 Multi-Robot Coordination with Periodic Connectivity by Hollinger and Singh
Project topics due
10/27 A Survey of Consensus Problems in Multi-agent Coordination by Ren, Beard and Atkins
10/29 Designing Collective Behavior in a Termite-Inspired Robot Construction Team by Werfel, Petersen and Nagpal
Programmable Self-Assembly in a Thousand-Robot Swarm by Rubenstein, Cornejo and Nagpal
Extra material for: Werfel, et al., Rubinstein, et al.
11/3 Economic Mechanism Design for Computerized Agents by Varian
11/5 Sammie: A Survey on Multi-robot Patrolling Algorithms by Portugal and Rocha
Madison: Graph-based Cross Entropy Method for Solving Multi-Robot Decentralized POMDPs (see email) 

11/10 No class (Pretending to be Wednesday)!
11/12 No class (Away)!
11/17 Mike K.: An Experimental Study of the Learnability of Congestion Control by Sivaraman, Winstein, Thaker and Balakrishnan
Collin: Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination by Stone, Kaminka, Kraus and Rosenschein

Project status reports
11/19 Mike B.: Auction-Based Multi-Robot Routing by Lagoudakis et al.
Tianyi: A Multi-Agent System for the Automation of a Port Container Terminal by Rebollo, Jullian, Carrascosa and Botti

11/24 Andreas: Optimization of Temporal Dynamics for Adaptive Human-Robot Interaction in Assembly Manufacturing by Wilcox, Nikolaidis and Shah
Reazul: Policy Search for Multi-Robot Coordination under Uncertainty by Amato, Konidaris, Anders, Cruz, How and Kaelbling

11/26 No class (Thanksgiving)!
12/1 Will: Friend-or-Foe Q-learning in General-Sum Games by Littman
Michaela: Integrated Perception and Planning in the Continuous Space: A POMDP Approach by Bai, Hsu and Lee

12/3 Bahram: Coordinated multi-robot exploration using a segmentation of the environment by Wurm, Stachniss and Burgard

12/8 Project presentations: Collin, Tianyi, Andreas, Will, Madison, Sam

12/10 Project presentations: Reazul, Michaela, Mike B., Mike K., Bahram

12/17 Not a class day AAAI format
Final paper due (11:59pm)