CIS341 AI Projects 2005

The main assessed work is a project report which can be either:

• an extended research-based essay of up to 3,500 words, with a separate list of references, or
• a programming project report of up to 3,500 words; you should also submit
  • a printout of your source code
  • a copy of your code on diskette
  • clear instructions on how to run your program
  Important:
  • Your project must be able to run on the Hatcham House PCs without any additional software;
  • The project must be coded in Prolog or Java, unless I have already agreed that you can use a different language.

You should choose a topic from the list below. Please email me your project title by Wednesday March 23rd.

Programming Projects

1. Expert System. See AAAI website: AI Topics, Expert Systems. Coding an expert system from scratch would be over-ambitious for a project of this scope but you could start with Bratko's expert system shell, described in Chapter 16 of Bratko 2001, supplemented with a knowledge base from a domain of your choice, and design and implement some improvements as suggested in Bratko's section 16.4. (The file frequent.txt contains predicates used in the shell.)
2. Definite Clause Grammars building on the lab exercises to extend the grammatical coverage and/or including semantic analysis. Suitable topics include:

   Coordination

   which is problematic for Prolog's top-down parsing strategy, e.g.

   1. John visited Edinburgh and Glasgow
   2. John likes fish and Mary likes chips

   "Unbounded dependencies"

   which are problematic for context-free grammars, e.g.

   1. Pavarotti likes a fish that Loren says she thinks Silvio hates.
   2. What fish did Loren say she thinks Silvio hates?

   One way to tackle this would be to consolidate your solutions to the lab exercises, including the new Exercise 6 on relative clauses. Useful readings include:
   • Internet Grammar of English
   • Pereira and Shieber, chapters 2.7, 3.7-8, 4.2-3.
   • Relevant chapters in Callan, Russell and Norvig.
   • The Language Instinct by Steven Pinker.
3. Route finder using heuristic search algorithms. This will build on lab exercises from Week 8 onwards. The domain will be a map of Roumania. The program should have some of the following functions:
   • Find a route between any two locations using depth-first, breadth-first, iterative deepening or uniform-cost search;
   • Find a route from any location to Bucharest using greedy search or A* search;
   • If you complete all the above try also implementing IDA*.
   You should start by completing the lab exercises on search algorithms. These exercises include simple examples of depth-first and breadth-first search in Prolog and Java. These programs are not especially efficient, particularly the Java versions, and there is plenty of scope for improvement. To implement uniform-cost, greedy search and A* you will need to rewrite the breadth-first version to include representations of path costs.

Research Topics

1. Philosophy of AI: can computers think, will they ever be able to; does it make sense to talk of computer systems having beliefs and intentions? See AAAI website: AI Topics, Turing Test.
2. The Semantic Web: using AI techniques of knowledge representation and reasoning to make machine-understandable data available on web pages. See www.semanticweb.org, or the semantic web pages at the W3C.
3. Case study of a major AI application, such as Nasa's Remote Agent system that operates an unmanned space probe
4. Survey of an area where AI has made an important contribution, e.g. gaming. See AAAI website: AI Topics, Applications, Games.

Important notes

• All projects must relate to one or more of the core topics in the CIS341 syllabus:
  • Formal grammars for natural language
  • Logic and knowledge representation
  • Search and problem solving
  • Planning
  • Philosophy of AI
• The content of your project must not overlap with your BSc project. If the topic is related to your BSc project, you should make clear in both reports how the two pieces of work are related.