GS/COSC 6390A Knowledge Representation - Fall 2002

Course Project

Proposal (worth 5% of course grade) due: November 11
Presentation (worth 15% of course grade) due: December 2 or 3
Final report (worth 40% of course grade) due: December 20

This course requires doing a project in the area of intelligent agents. The project may involve doing a literature survey, an implementation of an agent application, or even a research paper on a problem and a proposed solution. Some topics suggestions appear below, classified according to the type of project. Projects should be done individually, unless an advance authorization for a group project has been obtained from the instructor (this will only be allowed if project components can be assigned to individual group members).

Project Deliverables

By November 11, you should select a topic and submit a short (approx. 2 pages) project proposal. The proposal should outline your topic, state the project's objectives, give a tentative timetable for the tasks to be accomplished, and include a list of references (especially important for literature surveys). For implementation projects, it is recommended that a preliminary design for the system be included. You are encouraged to discuss your project with the instructor in advance. You will also get feedback on your proposal.

On December 2 or 3 students will give a short class presentation on their project and answer questions (you will be given a time slot in advance). This is worth 15% of the course's grade.

Your final report on the project is due by December 20. For literature survey projects, include an overview of the topic area, a discussion of the papers read, and a complete list of references; critical analysis is expected. For implementation projects, state the project's motivation and objectives, provide a readable description the system that was implemented (e.g. for Golog/ConGolog/IndiGolog programs, include a list of actions, fluents, procedures, agents, etc. each with an English explanation, and perhaps some diagrams to explain how the system behaves - e.g., state transition, dataflow, interaction diagrams), explain how the system is used, and describe the testing that was performed; include the documented code and sample tests in appendix. Also provide a discussion of how well the tools used in the project performed.

Suggested Project Topics

Implementation Projects

In this kind of project, you experiment with one or several agent programming tools by developing an agent application with the tool(s) and reporting on your experience.

Recommended agent programming tools are:

Other possibilities include: Jack, Zeus, FIPA-OS, JAM, UM-PRS, Agent-K, AgentBuilder, etc. The AgentBuilder site has a good list.

Using IndiGolog in combination with JADE would be more challenging than using the other tools above because you would need to develop your own interface for this; you can look at the IndiGolog-Java socket interface in the elevatorWithGUI example and the IndiGolog-OAA interface library IgOAAlib for inspiration.

Possible applications include:

See my IndiGolog site and the IgOAAlib site for examples of the first two types. If possible, compare your implementation with these or others.

To get insights into how IndiGolog is used, try to do the following robot control assignment from a previous year. The assignment asks for ConGolog programs, but write IndiGolog programs instead; for this, you have to modify the specification to use only functional fluents and translate the given axioms and interpreter calls into IndiGolog notation. This application can also be a starting point for a course project.

Literature Survey Projects

Survey an agent programming language or do a comparison of several; see the references below. If an implementation is available, you can also try it out.

Such a survey could also focus on a particular class of agent programming languages such as rule-based ones, e.g., AgentSpeak(L) and 3APL; see the references below and Wooldridge's Intro. to Multiagent Systems book for some discussion. Many features of these languages can actually be simulated in ConGolog/IndiGolog. You could write a compiler that takes a set of 3APL-style rules and compiles it into an equivalent ConGolog program. Then you could develop a set of examples to test your compiler. See the paper A. Gabaldon. Programming Hierarchical Task Networks in the Situation Calculus. In Proc. of AIPS'02 Workshop on On-line Planning and Scheduling, Toulouse, France, April 24, 2002.

Survey probabilistic or decision-theoretic extensions of Golog; see Chapter 12 Reiter's book for an introduction and some references; you could also experiment with the available implementations.

Survey work on implementions of Golog that support reasoning under incomplete knowledge; see Chapter 11 and Section 10.6 Reiter's book for an introduction and some references; see also recent papers by Ron Petrick, where efficient reasoning mechanisms that could be incorporated into IndiGolog are described. You could to try to extend the IndiGolog interpreter to incorporate some of this and test the result on some examples.

Another interesting area for agent application is contingency planning, i.e, generating plans that achieve goals in dynamic or nondeterministic environments. There is a fair amount of work on this that could be surveyed; see the references below. Also, a simple approach to contingency planning involves writing a program that simulates the environment and using it during planning, as proposed in [Lespérance & Ng 00]. You could try to extend the approach proposed there and implemented in interpreterN.pl to allow for nondeterministic environment simulators and generate conditional plans. One could also compare the qualitative approaches to contingency planning with the decision-theoretic approaches mentioned earlier.

There has been some work done on agent programming languages for agents that operate in environments with continuous processes, especially for robotics applications, for instance, cc-Golog; see the references below. You could survey this work. You could also experiment with cc-Golog.

Survey the area of agent architectures, looking at the tradeoffs between making plans and reacting quickly to dangers or opportunities, as well committing to plans versus making the best possible choice at any moment. See the general course references for starting points, especially the Wooldridge's Intro to Multiagent Systems book and Wooldridge and Jennings survey paper.

Survey work on high-level/knowledge-based control of vision systems for robotics applications; see below for references. We also have a testbed system for this and you could work with it.

Survey work on the use of agent technology in semantic web applications; see below for references.

Survey a particular type of application of agents, such as Internet information retrieval, cooperative work, etc. See the general course references for starting points, especially the books by Wookdridge, Jennings and Wooldridge, and Huhns and Singh.

Multiagent System Modeling Projects

Here, you use an agent-oriented modeling framework or agent-oriented software engineering framework to specify/model a multiagent system (MAS). Recommended frameworks are: Other AOSE frameworks of interest include MASE, PASSI, Message-UML, DESIRE, etc.

You can experiment with one framework or compare several frameworks. You can also do a literature survey of the area, looking at many frameworks. See the references below.

In some cases, it may be possible to use a tool associated with the framework to perform simulation or verification, e.g. the ConGolog simulation tool or CASL's PVS theorem prover-based tool. You could also look at the use of model checkers to verify multiagent system specifications.

References

On Agent Programming Languages

On Agent-0 and related languages:

Y. Shoham, Agent Oriented Programming, Artificial Intelligence, 60(1), 51-92, 1993.

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 V. Hindriks, Frank S. de Boer, W. van der Hoek and J.-J.Ch. Meyer. Agent Programming in 3APL, Autonomous Agents and Multi-Agent Systems, 2(4):357-401, 1999.

On AgentSpeak(L) and PRS:

A. S. Rao, AgentSpeak(L): BDI Agents speak out in a logical, computable language. In Agents Breaking Away, Walter Van de Velde and John W. Perrame (Eds.), pp. 42-55, LNAI, Volume 1038, Springer Verlag, 1996.

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, Adaptive Execution in Complex Dynamic Domains, Ph.D. Thesis, Yale University, Technical Report YALEU/CSD/RR #672, January 1989.

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, A Reactive Plan Language, Technical Report no. 864, Dept. of Computer Science, Yale University, 1991.

Drew McDermott's home page.

On Multiagent Infrastructures

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.

On JADE

The JADE home page.

The FIPA home page.

On Agent Technology and the Semantic Web

McIlraith, S., Son, T.C. and Zeng, H. Semantic Web Services. IEEE Intelligent Systems, Special Issue on the Semantic Web, 16(2):46--53, March/April, 2001. Copyright IEEE, 2001. See also the other papers in this special issue of IEEE Intelligent Systems.

McIlraith, S. and Son, T. Adapting Golog for Composition of Semantic Web Services. In Proc. of the 8th Int. Conference on Knowledge Representation and Reasoning (KR2002), Toulouse, April, 2002.

The DAML Project home page.

The W3C Semantic Web page.

The W3C Web Services page.

The Agentcities home page.

The FIPA home page.

On Agent-Oriented Software Engineering and MAS Modeling Frameworks

On MAS 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.

X. Wang and Y. Lespérance, Agent-Oriented Requirements Engineering Using ConGolog and i*. In Wagner, G., Karlapalem, K., Lesp\'{e}rance, Y., and Yu, E., editors, {\em Agent-Oriented Information Systems 2001, Proceedings of the 3rd International Bi-Conference Workshop AOIS-2001}, 59-78, iCue Publishing, Berlin, 2001.

The ConGolog simulation tool page.

On CASL:

S. Shapiro and Y. Lespérance. Modeling Multiagent Systems with the Cognitive Agents Specification Language - A Feature Interaction Resolution Application. In Castelfranchi, C. and Lespérance, Y., editors, Intelligent Agents Volume VII - Proceedings of the 2000 Workshop on Agent Theories, Architectures, and Languages (ATAL-2000), LNAI, vol. 1986, 244-259, Springer-Verlag, Berlin, 2001.

S. Shapiro, Y. Lespérance, and H.J. Levesque. The Cognitive Agents Specification Language and Verification Environment for Multiagent Systems. In C. Castelfranchi and W. Lewis Johnson (Eds.), Proc. of the 1st Int. Joint Conference on Autonomous Agents and Multiagent Systems, 19-26, Bologna, Italy, July 15-19, 2002. ACM Press.

Y. Lespérance. On the Epistemic Feasibility of Plans in Multiagent Systems Specifications. In J.J.C. Meyer and M. Tambe (Eds) Intelligent Agents VIII, Agent Theories, Architectures, and Languages, 8th International Workshop, ATAL-2001, Seattle, WA, USA, Aug. 1-3, 2001, Revised papers, 69-85, LNAI 2333, Springer, 2002.

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.

On i*:

The i* home page.

On Tropos:

The Tropos home page. This has links to other resources on Agent-Oriented Software Engineering, requirements engineering and process modeling.

On Agent UML:

The Agent UML home page.

On Gaia:

M. Wooldridge, N. R. Jennings, and D. Kinny. The Gaia Methodology for Agent-Oriented Analysis and Design. In Journal of Autonomous Agents and Multi-Agent Systems. 3(3):285-312. 2000.

On Good Examples for Agent-Oriented Methodologies:

E. Yu, L.M. Cysneiros. Agent-Oriented Methodologies - Towards A Challenge Exemplar. Proc. of the 4th International Workshop on Agent-Oriented Information Systems (AOIS'02), Toronto, May 27-28, 2002..

On Coordination Protocols:

The original 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.

On Contingent Planning and Incorporating it in IndiGolog:

Y. Lespérance and H.-K. Ng. Integrating Planning into Reactive High-Level Robot Programs. In Proceedings of the Second International Cognitive Robotics Workshop, 49-54, Berlin, Germany, August, 2000.

E. Guere and R. Alami. A Possibilistic Planner that Deals with Non-Determinism and Contingency. Proc. of the 16th International Joint Conference on Artificial Intelligence (IJCAI'99), 996-1001, Stockholm, August, 1999.

On Continuous Control:

H. Grosskreutz and G.Lakemeyer, cc-Golog: Towards More Realistic Logic-Based Robot Controllers, Proc. AAAI-2000, Austin, TX, July 2000.

H. Grosskreutz and G.Lakemeyer, On-Line Execution of ccGolog Plans, Proc. IJCAI-01, Seattle, WA, August 2001.

M. Beetz. Structured Reactive Controllers - Robots that Perform Everyday Activity. In Proc. of the 3rd Int. Conference on Autonomous Agents, Seattle, WA, 1999.

E Gat. Integrating Planning and Reacting in a Heterogenous Asynchronous Architecture for Controlling Real-World Mobile Robots. In Proc. of the Tenth National Conference on Artificial Intelligence, 809-815, San Jose, CA, July 1992.

You can also look at the references for RPL and RAP.

On High-Level/Knowledge-Based Control of Vision Systems:

C. Shekhar, S. Moisan, R. Vincent, P. Burlina, and R. Chellappa. Knowledge-Based Control of Vision Systems. Image and Vision Computing, 17, 667-683, 1999.

P. Robertson and J.M. Brady. Adaptive Image Analysis for Aerial Surveillance. IEEE Intelligent Systems, 30-45, May/June, 1999.

P. Jasiobedzki, M. Abraham, P. Newhook, and J. Talbot. Model Based Pose Estimation for Autonomous Operations in Space. Proc. of IEEE Int. Conference on Intelligence, Information, and Systems. Washington, Nov., 1999.

These references, as well as documents from the CITO project High-Level Control of Vision Sensing Systems, are available from the instructor.