CPSC 689 - Special Topics in Multi-Agent Systems

Spring 2006

Professor: Dr. Thomas R. Ioerger
Office: 322C Bright Bldg.
Phone: 845-0161
email: ioerger@cs.tamu.edu
office hours: make appointment by email

Meeting: Tues/Thurs, 1:30-3:00, 320 Bright

Course Web Page: http://www.cs.tamu.edu/faculty/ioerger/cs689-spring06/index.html

Prerequisites: CPSC 625 (AI), CPSC 631 (Programming Environments in AI)

Textbooks

There will be no textbook used. The course will be based on research papers that can be printed out.

For background material, here are some good textbooks on agents:

Wooldridge, M. (2002). An Introduction to Multiagent Systems. Wiley.
Ferber, J. (1999). Multi-Agent Systems. Addison-Wesley.
Weiss, G. (1999). Multi-Agent Systems. MIT Press.
Bradshaw, G. (1997). Software Agents. AAAI Press.
Huhns, M. and Singh, P. (1998). Reading in Agents. Morgan Kaufmann.
Wooldridge, M. and Rao, A. (1999). Foundations of Rational Agency. Applied Logic Series, Vol. 14, Kluwer.
Wooldridge, M. (2000). Reasoning about Rational Agents. MIT Press.

Goals of this Course

To learn about extended topics in Multi-Agent Systems, including multi-agent interactions, cooperation, and distributed decision-making. Two focal themes will be: utility-maximization for self-interested agents, and coordination through market-based mechanisms.

Game Theory, Strategic Decision-Making in Competitive Environments
Negotiation
Auctions (market-based models)
Coalition Formation
Voting (consensus mechanisms)

Assignments, Projects, Exams, and Grading

The primary work for the course will consist of reading and discussing journal papers from the research literature. Students will have to give presentations and lead discussions on 2 papers from a selected list. The grade will be based on the quality of the presentations (60%) and class participation (40%).

Schedule:

The schedule is presented as weekly topics. Each week will consist of a student-presentation on Tues, followed by a class discussion on Thurs.

Tues, Jan 24: Sandholm (1999)
Tues, Jan 31: Zlotkin and Rosenschein (1989) (negotiation); Sandholm and Lesser (2002) (leveled commitments; see also: Sandholm, Sikka, Norden (1999))
Tues, Feb 7: Sandholm and Lesser (1997)
Tues, Feb 14: Sandholm et al. (1999)
Tues, Feb 21: Shehory and Kraus (1998)
Tues, Feb 28: payoff distribution: Kraus, Shehory and Taase (2004); Zlotkin and Rosenschein (1994)
Tues, Mar 7: combinatorial auctions: Walsh and Wellman, 1998; Walsh, Wellman, and Ygge, 2000; Sandholm, Suri, Gilpin, and Levine, 2002
Tues, Mar 14: (Spring Break)
Tues, Mar 21: MDPs: Russell and Norvig, pp. 613-628, Littman et al. (complexity), Littman (Markov games)
Tues, Mar 28: Boutilier, Brafman, and Geib (1997) (MDPs and planning)
Tues, Apr 4: Nair and Tambe (2005) (hybrid BDI-POMDP)
Tues, Apr 11: Gmytrasiewicz and Durfee (2001), Gmytrasiewicz and Durfee (2000) (recursive modeling method, RMM)
Tues, Apr 18: Sen and Sekaran (1998) (learning coordination knowledge)
Tues, Apr 25: Ephrati and Rosenschein (1996) (deriving consensus, Clarke tax)

References:

Sandholm, T. (1999). Distributed Rational Decision Making. in Multi-Agent Systems (chapter 5). G. Weiss, ed. MIT Press: Cambridge, MA.
Sen, S. and Sekaran, M. (1998). Individual learning of coordination knowledge. Journal of Experimental & Theoretical Artificial Intelligence, 10:333-356.
Zlotkin, G. and Rosenschein, J.S. (1989). Negotiation and Task Sharing Among Autonomous Agents in Cooperative Domains. IJCAI, 912-917.
Sandholm, T. and Lesser, V. (2002). Leveled-commitment contracting: A backtracking instrument for mulitagent systems. AI Magazine, 23(3):89-100.
Sandholm, T., Sikka, S., and Norden, S. (1999). Algorithms for optimizing leveled commitment contracts. IJCAI, 535-540.
Sandholm, T., Larson, K., Andersson, M., Shehory, O., and Tohme, F. (1999). Coalition Structure Generation with Worst Case Guarantees. Artificial Intelligence, 111(12) , 209-238.
T. Sandholm and V. R. Lesser. Coalitions among computationally bounded agents. Artificial Intelligence, 94(1-2):99-137, 1997.
Shehory, O., and Kraus, S. 1998. Methods for task allocation via agent coalition formation. Artificial Intelligence, 101(1-2):165-200.
Zlotkin, G., and Rosenschein, J.S. (1994), "Coalition, Cryptography, And Stability: Mechanisms For Coalition Formation In Task Oriented Domains", Proceedings of the Twelfth National Conference on Artificial Intelligence, pp. 432-437.
Kraus, S. and Shehory, O. and Taase, G. (2004). The Advantages of Compromising in Coalition Formation with Incomplete Information. Third International Joint Conference on Autonomous Agents and Multiagent Systems, pp. 588-595.
Walsh, W. and Wellman, M. (1998). A market protocol for decentralized task allocation. Proceedings of the Third International Conference on Multi-Agent Systems, 325-332.
Walsh, W.E., Wellman, M.P., and Ygge, F. (2000). Combinatorial auctions for supply chain formation. Proceedings of ACM Conference on Electronic Commerce, 260-269.
Sandholm, T., Suri, S., Gilpin, A. and Levine, D. (2002). Winner determination in combinatorial auction generalizations. Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems, 69-76.
Boutilier, C., Brafman R.I., and Geib C. (1997). Prioritized goal decomposition of Markov decision processes: Toward a synthesis of classical and decision theoretic planning. Proceedings of the 15th International Joint Conference on Artificial Intelligence, 1156-1162.
Gmytrasiewicz, P.J., and Durfee, E.H. (2001). Rational communication in multi-agent environments. Autonomous Agents and Multi-Agent Systems, 4:233-272.
Gmytrasiewicz, P.J., and Durfee, E.H. (2000). Rational coordination in multi-agent environments. Autonomous Agents and Multi-Agent Systems, 3:319-350.
Nair, R. and Tambe, M. (2005). Hybrid bdi-pomdp framework for multiagent teaming. Journal of AI Research, 23:367-413.
Ephrati, E. and Rosenschein, J. (1996). Deriving consensus in multiagent systems. Artificial Intelligence, 87:21-74.