SC/AS/COSC 4401.03 Artificial Intelligence
GS/COSC 5326.03 Topics in Artificial Intelligence
Winter 2000

Basic Information

This Year's Topic: Intelligent Agent Modeling and Design.

One of the central concerns of Artificial Intelligence is the design and implementation of autonomous agents - active entities that perceive their environment, reason, plan and execute appropriate actions to achieve their goals (in service of their users), and react to external changes. These may be robots or intelligent software agents that "live" on the Internet. This course covers agent programming languages (such as our own, ConGolog, and others such as AGENT-0), logical models of agency, issues in agent architecture, and applications of intelligent agents.

Instructor

Prof. Yves Lespérance
Office: 342 CCB
Tel: 736-2100 ext. 70146
Email: lesperan@cs.yorku.ca

Lectures

MWF, 11:30 - 12:30, 120 CCB.

Instructor Office Hours

MWF, 16:00 - 17:00, 342 CCB, or by appointment.

Prerequisites

SC/AS/COSC 3402.03 or equivalent. You must know Prolog to take this course (or be able topick it up quickly on your own). You should also have a solid background in first-order logic.

Evaluation

Assignment	15%
In-class tests (2 @ 20% each)	40%
Project Proposal	5%
Project Report	40%
Total	100%

Tentative Outline

• Introduction to Intelligent Autonomous Agents and their Applications.
• Logical Preliminaries.
• Introduction to the Situation Calculus.
• The Situation Calculus: Foundations, Reasoning Methods, and Logic Programming Implementation.
• Complex Actions, Procedures, and Golog.
• Concurrent Processes and ConGolog.
• Modeling Agents' Knowledge and its Dynamics.
• Modeling Agents' Goals and their Dynamics.
• Embedded Agents and IndiGolog.
• Other Agent Modeling/Programming Languages, e.g. Agent0, 3APL, AgentSpeak(L).
• Multi-Agent System Infrastructures, e.g. RETSINA, OAA.

References and Links

General References

Wooldridge M. and Jennings, N.R., Intelligent Agents: Theory and Practice, Knowledge Engineering Review, 10 (2), 115-152, 1995; Postscript version, HTML version.

Reiter, R., Knowledge in Action: Logical Foundations for Describing and Implementing Dynamical Systems, Unpublished Draft Monograph, January 1999.

Huhns, M.N. and Singh, M.P. (Eds.), Readings in Agents, Morgan Kaufmann, San Francisco, CA, 1997.

Bradshaw, J. (Ed.), Software Agents, AAAI Press/MIT Press, Cambridge, MA, 1997.

Jennings, N.R. and Wooldridge, M. (Eds.), Agent Technology: Foundations, Applications, and Markets, Springer Verlag, Berlin, 1998.

Wooldridge, M. and Rao, A. (Eds.), Foundations of Rational Agency, Applied Logic Series, Vol. 14, Kluwer, Dordrecht, 1999.

Clocksin, W.F. and Mellish, C.S., Programming in Prolog, Springer Verlag, New York, 1987. Third edition.

Russell, S.J. and Norvig, P., Artificial Intelligence: A Modern Approach, Prentice Hall, 1995.

References on Agent Programming Languages

On Agent-0:

S.R. Thomas, A Survey of Agent-Oriented Programming. In Wooldridge, M. and Rao, A. (Eds.), Foundations of Rational Agency, Applied Logic Series, Vol. 14, pp. 263-274, Kluwer, Dordrecht, 1999.

Winton Davies's Agent-K, an implementation of an extension of Agent-0 that uses KQML for interagent communication.

On 3APL:

Koen Hindriks's home page.

On AgentSpeak(L) and PRS:

A. S. Rao and M. P. Georgeff. An abstract architecture for rational agents. In C. Rich, W. Swartout, and B. Nebel, editors, Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, pp. 439-449, Morgan Kaufmann Publishers, San Mateo, CA, 1992.

Univ. of Michican's implementation of PRS.

On RAP:

R.J. Firby, The RAP Language Manual, Animate Agent Project Working Note AAP-6, University of Chicago, March 1995.

Jim Firby's home page; has information on an implementation of RAP..

On RPL:

Drew McDermott's home page.

References on Process Modeling in ConGolog

Y. Lespérance, T.G.Kelley, J. Mylopoulos, E.S.K. Yu. Modeling Dynamic Domains with ConGolog, in Advanced Information Systems Engineering, 11th International Conference, CAiSE-99, Proceedings, pp. 365-380, Heidelberg, Germany, June 1999, LNCS vol. 1626, Springer-Verlag, Berlin.

S. Shapiro, Y. Lespérance, and H.J. Levesque. Specifying Communicative Multi-Agent Systems with ConGolog. In Working Notes of the AAAI Fall 1997 Symposium on Communicative Action in Humans and Machines, pp. 75-82, Cambridge, MA, November, 1997, AAAI Press. A version of this paper also appears in Agents and Multi-Agent Systems -- Formalisms, Methodologies, and Applications, W. Wobcke, M. Pagnucco, and C. Zhang, eds., pp. 1-14, LNAI, Springer-Verlag, Berlin, 1998.

The Tropos home page - other resources on requirements engineering and process modeling.

The paper on the Contract Net protocol:
Randall Davis and Reid G. Smith. Negociation as a Metaphor for Distributed Problem Solving, Artificial Intelligence, 20:63-109,1983.

References on the Open Agent Architecture (OAA)

D. L. Martin, A. J. Cheyer, and D. B. Moran, The open agent architecture: A framework for building distributed software systems, Applied Artificial Intelligence, 13, 91-128, January-March 1999. Gnu-compressed PostScript version, HTML version.

The OAA home page.

Detailed Schedule

• Week 1: Introduction - Intelligent Agents and their Applications.
  Required readings: Wooldridge M. and Jennings, N.R., Intelligent Agents: Theory and Practice, Postscript version, HTML version.
  Reference on SRI Automated Office Application (optional reading): P. R. Cohen, A. J. Cheyer, M. Wang, and S. C. Baeg, "An open agent architecture," in AAAI Spring Symposium, pp. 1--8, March 1994. HTML version. GNU-Compressed (gz) PostScript version.
  Reference on ConGolog Robotics Application (optional reading): Y. Lespérance, K. Tam, and M. Jenkin. Reactivity in a Logic-Based Robot Programming Framework. to appear in Jennings, N.R. and Lespérance, Y., editors, Intelligent Agents Volume VI - Proceedings of the 1999 Workshop on Agent Theories, Architectures, and Languages (ATAL-99), LNAI, Springer-Verlag, Berlin, 2000.
  Lecture transparencies.

• Week 2: Logical Preliminaries.
  Required readings: Reiter, R., Knowledge in Action: Logical Foundations for Describing and Implementing Dynamical Systems, Chapters 1 and 2.
  

• Week 3: Introduction to the Situation Calculus.
  Required readings: Reiter book, Chapter 3.
  

• Week 4: The Situation Calculus: Foundations, Induction, and Regression.
  Required readings: Reiter book Chapter 4.
  Yale shooting example transparencies.

• Week 5: Logic Programming Implementation of Basic Action Theories.
  Required readings: Reiter book Chapter 5.
  

• Week 6: Complex Actions and Golog.
  Required readings: Reiter book Chapter 6.
  

• Week 7: Reading Week.

• Week 8 (Feb. 21): Concurrent Processes and ConGolog.
  Required readings: G. De Giacomo, Y. Lespérance, and H.J. Levesque. ConGolog, a Concurrent Programming Language Based on the Situation Calculus: Language and Implementation. A revised version will appear in Artificial Inteligence, 2000.
  Lecture transparencies.

• The midterm test is on Wed. Feb. 23. It covers everything we have seen up to the end of week 6, i.e., the first 6 chapters of Reiter's book and the Wooldridge and Jennings paper. The test is open-book and lasts 50 minutes. For the the Yale shooting example transparencies, see week 4 above.

• The assignment is now out. The deadline has been extended to Monday March 6. Assignment handout.
  You must implement your program using the ConGolog implementation found in ~lesperan/cogrobo/ConGolog98/ on the Ariel and CAT systems.
  Information on ConGolog implementation on CAT.
  Information on ConGolog implementation on Ariel.
  See the Golog elevator example in ~lesperan/cogrobo/ConGolog98/examples/elevatorGolog.pl.

• Week 9 (Feb. 28): Embedded Agents and IndiGolog.
  Required readings: G. De Giacomo, H.J. Levesque. An Incremental Interpreter for High-Level Programs with Sensing. In Cognitive Robotics - Papers from the 1998 AAAI Fall Symposium, AAAI Technical Report FS-98-02, pp. 28-34, 1998.
  Lecture transparencies.
  See the IndiGolog interpreter and examples in ~lesperan/cogrobo/IndiGolog.

• Week 10 (March 6): Multi-Agent System Infrastructures.
  Required readings: D. L. Martin, A. J. Cheyer, and D. B. Moran, The open agent architecture: A framework for building distributed software systems, Applied Artificial Intelligence, 13, 91-128, January-March 1999. Gnu-compressed PostScript version, HTML version.

• Week 11 (March 13): Multi-Agent System Infrastructures (cont.).
  Required readings:
  Y. Labrou and T. Finin, Semantics and Conversations for an Agent Communication Language, Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, August 1997.
  Suggested readings:
  R. Bayardo, et al., InfoSleuth: Agent-Based Semantic Integration of Information in Open and Dynamic Environments Proc. of SIGMOD'97. PostScript, HTML.
  T. Finin, Y. Labrou, and J. Mayfield, KQML as an agent communication language, in J.M. Bradshaw (Ed.), Software Agents, MIT Press, Cambridge, 1997.
  

• Week 12 (March 20): Rule-Based Agent Programming Languages and Interaction Protocols
  Class cancelled on Monday March 20 and no office hours.
  Required readings:
  Koen V. Hindriks, Frank S. de Boer, W. van der Hoek and J.-J.Ch. Meyer, A Formal Semantics for an Abstract Programming Language, Proc. ATAL'97, LNAI 1365, Springer-Verlag.
  Suggested readings:
  Randall Davis and Reid G. Smith. Negociation as a Metaphor for Distributed Problem Solving, Artificial Intelligence, 20:63-109,1983.
  T. Sandholm and V. Lesser. Issues in Automated Negotiation and Electronic Commerce: Extending the Contract Net Framework. In Proc. of the International Conference on Multiagent Systems, pp. 328-335, 1995. Also appears in Readings in Agents.
  J. Rosenschein and G. Zlotkin. Designing Conventions for Automated Negotiation. AI Magazine, 15(3), 29-46, 1994. Also appears in Readings in Agents.
  

• Week 13 (March 27): Modeling Mental States and Communication
  Lecture transparencies on knowledge.
  Required readings:
  S. Shapiro, Y. Lespérance, and H.J. Levesque. Specifying Communicative Multi-Agent Systems with ConGolog. In Working Notes of the AAAI Fall 1997 Symposium on Communicative Action in Humans and Machines, pp. 75-82, Cambridge, MA, November, 1997, AAAI Press. A version of this paper also appears in Agents and Multi-Agent Systems -- Formalisms, Methodologies, and Applications, W. Wobcke, M. Pagnucco, and C. Zhang, eds., pp. 1-14, LNAI, Springer-Verlag, Berlin, 1998.

• The end of term test is on Friday, March 31. It focuses on the material covered since reading week. The test is open-book and lasts 50 minutes.
  Sample questions.

• The project is now out. Project handout. The proposal is due March 13 and the final report is due April 10. See the additional references and links above. If you cannot get a paper after looking for it at the library, and there is no link to it on the Web, come and see me.

  Project tips: If you are doing a project involving an implementation, it must be documented properly. For IndiGolog or ConGolog programs, your report should include a list of primitive actions and fluents with a brief explanation in English, a list of the procedures defined with an English explanation of what they do and their parameters, a general explanation of the problem and design chosen, and a discussion of the tests done. Your code should also be documented properly. In terms of style, you should not use free Prolog variables in IndiGolog or ConGolog procedures; use "some" and "pick". You can pickup your marked assignment for feedback on style and documentation.