CSCI 543: Software Multiagent Systems

Schedule of Classes

CS 543: Software Multiagent Systems

January 2010

 

I will change/update the papers listed in part II and III, as papers from 2010 become available.

 

PART I: Fundamentals of agents and multiagent systems

 

1. (January 12): Course intro, syllabus, what is an intelligent agent

 

2. (January 14): Beliefs, desires, intentions (BDI), Satisficing, Begin BDI logics

 

3. (January 19): BDI logics continued, BDI architectures, reactive plans

 

4. (January 21): Decision theory; Making simple decisions under uncertainty; risk; risk averseness, risk neutrality; Sequential decisions under uncertainty, Markov decision problems; Value iteration; basic introduction to POMDPs

Suggested reading: Kaebling, Littman, Cassandra: Planning and Acting in Partially Observable Stochastic Domains, AIJ 101, 1998

 

5. (January 26, 28, Feb 2): Game theory: Normal form and extensive form games, Prisoner’s dilemma, Chicken, Dominance, iterative dominance, Nash equilibrium; Mixed strategy Nash equilibrium, Iterative Prisonners dilemma, Stackelberg games, Bayesian Games, Harsanyi transformation

 

6. (Feb 4): Game theory and applications

Suggested reading: Pita et al: Using Game Theory for Los Angeles Airport Security, AI Magazine, 30(1):43-57, 2009

 

PART II: Collaboration: Agent-agent and agent-human interactions

 

1. (February 9): Distributed constraint reasoning, Distributed constraint satisfaction

 

2. (February 11,16) Distributed constraint optimization I: Complete algorithms

• P. J. Modi, W. Shen, M. Tambe and M. Yokoo, "ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees", Artificial Intelligence Journal, 161:149-180, 2005.

• R. Mailler and V. Lesser, "Solving Distributed Constraint Optimization Problems Using Cooperative Mediation", Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2004.

• J. Davin, P. J. Modi, "Impact of Problem Centralization in Distributed Constraint Optimization Algorithms", Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2005.

• A. Petcu and B. Faltings, "A Scalable Method for Multiagent Constraint Optimization", IJCAI 2005.

 

3. (February 18): Distributed constraint optimization II: Incomplete algorithms and recent theoretical results

• J. P. Pearce and Milind Tambe, "Quality guarantees on k-optimal solutions for distributed constraint optimization problems", In the International Joint Conference on Artificial Intelligence, IJCAI 2007.

• R. Maheswaran, J. P. Pearce and Milind Tambe, "Distributed algorithms for DCOP: A graphical game based approach", In International Conf on Parallel and distributed Systems (PDCS) 2004.

 

4. (Feb 23,25): Distributed Coordinated Exploration and Exploitation (DCEE)

• M., M. Taylor, M. Tambe, and M. Yokoo, "DCOPs Meet the RealWorld: Exploring Unknown Reward Matrices with Applications to Mobile Sensor Networks", In International Joint Conference on Artificial Intelligence (IJCAI), 2009.

• M. Taylor, M. Jain, P. Tandon, and M. Tambe, "Using DCOPs to Balance Exploration and Exploitation in Time-Critical Domains", In Proceedings of the IJCAI 2009 Workshop on Distributed Constraint Reasoning (DCR), 2009.

• M. Taylor, M. Jain, Y. Jin, M. Yooko, and M. Tambe, "When Should There be a "Me" in "Team"? Distributed Multi-Agent Optimization Under Uncertainty", In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2010.

 

5. (March): Distributed POMDPs

• R. Nair, M. Tambe, M. Yokoo, D. Pynadath, and S. Marsella, "Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings", IJCAI, 2003.

• R. Becker, S. Zilberstein, V. Lesser, and C. V. Goldman, "Transition independent decentralized markov decision problems", AAMAS, 2003.

• J. Marecki, P. Varkantham, T. Gupta, M. Tambe, and M. Yokoo, "Not all agents are equal: Scaling up Distributed POMDPs for Agent Networks", AAMAS, 2008.

 

6. (March):  Teamwork I: What is teamwork, team logic

• H. Levesque, P. Cohen, and J. Nunes, "On acting together", AAAI, 1990.

• B. Grosz and S. Kraus, "Collaborative Plans for Complex Group Action", In Artificial Intelligence, 1996.

 

7. (March): Teamwork II: Practically implementing teamwork beyond joint persistent goals: representing team plans and roles in an agent architecture, addressing practical communication costs, team monitoring and recovery from failures. Introduction to decision theoretic approaches to teamwork.

• D. V. Pynadath and M. Tambe, "Automated teamwork among heterogeneous software agents and humans", Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS), 2003.

• K. Decker, and V. Lesser, "Designing a Family of Coordination Algorithms", In Proceedings of the First International Conference on Multi-Agent Systems, 1994.

• G. Kaminka, and I. Frenkel, "Flexible Teamwork in Behavior-Based Robots", In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2005.

 

8. (March): Auctions, Team formation (symbolic matching, combinatorial auctions), task allocation (contract nets)

• T. Sandholm, "An algorithm for optimal winner determination in combinatorial auctions", In Sixteenth International Joint Conference on Artificial Intelligence (IJCAI), 1999.

• L. Huhnsberger, and B. Grosz, "A combinatorial auction for collaborative planning", In Proceedings of the International conference on Multi-agent Systems (AAMAS), 2000.

 

PART III: Adversarial domains, security, safety

 

1. (Mar 2, 4): Advanced topics in Game theory

• J. Pita, M. Jain, F. Ordóñez, M. Tambe, S. Kraus, and R. Magori-Cohen, "Effective Solutions for Real-World Stackelberg Games: When Agents Must Deal with Human Uncertainties", AAMAS 2009.

• Z. Yin, D. Korzhyk, C. Kiekintveld, V. Conitzer, and M. Tambe, "Stackelberg vs. Nash in Security Games: Interchangeability, Equivalence, and Uniqueness", AAMAS 2010.

 

2.  (March 9): Adjustable autonomy

 

3.  (March 11): Midterm

SPRING BREAK (March 15 – March 20)

 

4.  (March 23,25): Your paper presentations

 

5.  (March 30): Agent modeling I: Symbolic plan recognition, model tracing, prediction

• G. Kaminka, and M. Tambe, "Robust agent teams via socially attentive monitoring", Journal of Artificial Intelligence Research (JAIR) 2000.

• P. Gmytrasiewicz and E. Durfee, "Rational Coordination in Multi-Agent Environments", Journal of Autonomous Agents and Multi-Agent Systems 2000.

 

6. (April 1, April 6): Agent applications to security

• V. Conitzer and T. Sandholm, "Computing the optimal strategy to commit to", 7th ACM Conference on Electronic Commerce (EC), 2006.

• P. Paruchuri, J. Pearce, M. Tambe, S. Kraus, and F. Ordonez, "An Efficient Heuristic Approach for Security Against Multiple Adversaries", AAAI Spring Symposium on Game and Decision-Theoretic Agents, 2007.

• P. Paruchuri, M. Tambe, S. Kraus, F. Ordonez, "Security in multiagent systems by policy randomization", International Joint conference on Autonomous agents and Multiagent Systems (AAMAS), 2006.

 

7. (April 9, 14): Project presentations

 

8. (April 16): Late breaking topics

 

9. (April 21, 23, 28): Late breaking topics

 

10. (April 30): Quiz II