TEACH POP11_PROJECT                           Aaron Sloman November 1999

         CONTENTS - (Use <ENTER> g to access required sections)

 -- Introduction
 -- Objectives of the mini-project
 -- Techniques that your project will need
 -- Possible topics
 -- -- 1. A problem solver based on searching
 -- -- -- A route-finding program
 -- -- -- A puzzle solving program
 -- -- 2. A "natural language" front end
 -- -- -- A front end to LIB RIVER
 -- -- -- A conversational drinks machine
 -- -- -- A diary manager
 -- -- 3. A program to play a board game
 -- -- 4. An expert system (e.g. fault diagnosis, or planning)
 -- -- 5. An "object oriented" adventure game (possibly using SIM_AGENT)
 -- Other possible projects
 -- WARNING
 -- Formulating a proposal
 -- After the topic has been approved: a project plan
 -- Writing up the report
 -- Handing in the report
 -- What assessors will be looking for

-- Introduction -------------------------------------------------------

The final exercise for the introductory Pop-11 programming course is to
propose design, implement, and document a mini-project.

The deadline for submission of the report will be announced separately.

You will almost certainly find the project highly enjoyable but also
very challenging.

If you find the descriptions of possible mini-projects below too
daunting at first, please note that some of the options have been
designed to be much easier than others, and are supported by helpful
TEACH files, whereas others are more challenging and require more
independent work. The most important thing is not that you have to
produce a very impressive or highly original project, but that that you
should be able to do something that works, and then write a good report
on it explaining what it is, how it works, and how it could be improved.
You should also, in your critical discussion of your program, show
evidence of having read about related work in AI. Of course, the
difficulty of a project will be taken into account in awarding a mark.

Tutors and demonstrators can help you cut down your project goals to a
size that suits your abilities.

Students who wish to collaborate on a project may discuss this with the
tutor. They will have to hand in separate reports, each report making it
very clear which portion of the work was done by whom and how the
collaboration was managed.

Below you will find a list of possible topics for your projects. If you
think you have an alternative topic that you would prefer to work on
please send a brief description as soon as possible by email to the
person currently teaching your course.

-- Objectives of the mini-project -------------------------------------

There are several important educational objectives

o The project will help you consolidate your grasp of the language
  Pop-11 (many of whose features are also found in other programming
  languages).

o You will have your first experience of designing a complete system
  yourself, starting from the process of specifying high level goals.
  This requires clarity of thought and an ability to think at different
  levels of abstraction, which will be very useful in many other
  contexts later on, both in your studies here and in your later career.

o You will continue learning how to test your programs and to track
  down bugs.
  (Everyone produces bugs. More advanced programmers produce more
  advanced bugs. Learning techniques for tracking down problems, and
  fixing them, is very important for anyone who needs to be able to
  design working systems or explanatory models. Thus the bugs are
  an important part of the learning process.)

o You will have experience of writing a report on your program. In fact
  it is mainly the reports that assessors will read, so you will need
  to be able to explain your objectives clearly, explain the design you
  developed in order to meet those objectives, demonstrate how far the
  program succeeds, and analyse its weaknesses and possibilities for
  future development.

o If the project relates to published literature you will also learn how
  to report on things you have read and relate your own work to the work
  of others.

In addition to these educational objectives the project will count as
part of your assessment. That's less important!

-- Techniques that your project will need -----------------------------

Your project should make use of a subset of the techniques that you have
learnt this term.

Depending on how much progress you have made since starting, these
techniques could include:


  A. General programming techniques such as:

    - defining procedures that form a package that work together,
      passing arguments and receiving results

    - using a variety of syntactic control constructs including
      conditionals and loops of various kinds (while, for, foreach, etc.)

    - manipulating lists and other data-structures (e.g. words,
      strings, numbers)

    - describing programs (saying what they do and how they do it,
      at different levels of abstraction)


  B. Techniques that are more specifically relevant to designing
     intelligent (or "knowledge based") systems, including:

    - using lists and the pattern matcher to store and manipulate
      information about the chosen problem domain
      (E.g. TEACH RESPOND, RIVER2, MATCHES, DATABASE)

    - using a search strategy to permit the computer to find a solution
      to a problem by exploring combinations of alternatives
      (E.g. TEACH TOWER, SEARCHING)

    - using domain-specific heuristics to control the search

    - designing a simplified natural language interface to replace a
      typical programming command interface.
      (E.g. TEACH GRAMMAR, TEACH RIVERCHAT)

    - using rule-based programming (perhaps: See TEACH RULEBASE)

    - designing a simple expert system of some kind
      (E.g. TEACH SEARCHING, PRBWINE, RULEBASE, PRBRIVER)

    - for some students, learning to use object oriented techniques,
      based on classes, methods, and inheritance.
      (E.g. TEACH ADVENT_OBJECTCLASS, TEACH OOP)

    - for some students, learning to use the graphical facilities
      in POP11 (e.g. TEACH GSTART, RC_GRAPHIC)

    - for some students, learning to use the control-panel and menu
      facilities in POP-11
      (E.g. TEACH  RCLIB_DEMO.P, HELP RC_CONTROL_PANEL (and others)

    - for some students, learning to use the SIM_AGENT toolkit.
      (E.g. TEACH SIM_FEELINGS, TEACH SIM_AGENT)

It isn't necessary for every student to address all these techniques.
You may focus on a subset that relates to what you have learnt and your
interests.


-- Possible topics ----------------------------------------------------

Here is a list of possible project topics. Each of them is very
open-ended. For students who are new to programming it would be possible
to attempt a simple version of one of these. Those with more experience
and fluency can attempt a more ambitious version.

It is a fact of life that programming abilities vary ENORMOUSLY from
individual to individual, so students who see others making much more
rapid progress should try to do the best they can without letting the
discrepancy cause depression or despair. You may need guidance on how to
restrict your objectives to something that you can manage. Also remember
that the primary assessment will not be on how much code you have
written, but on how well you report on what you have and have not done,
as explained below.

Each of the following topics grows out of teach files, some of which you
have already worked through, some not.

-- -- 1. A problem solver based on searching

Ideally every student should do a program that involves some searching,
as this is such a basic and general aspect of AI (and intelligence).
However for some students this may be too difficult, and one of the
later options would then be more suitable.

TEACH TOWER introduces basic programming techniques for searching for a
solution to a problem. TEACH SEARCHING generalises this by showing you
how to build a very general program that can be applied to a variety of
problems for which a solution can only be found by searching in an
abstract or concrete search space. Your project could complete the
problem solver described in TEACH SEARCHING and show how to apply it to
a few different problems, e.g. solving the river crossing problem, or
some other.

-- -- -- A route-finding program

Another possible searching application, sketched in the teach file, is a
program that finds routes. If you wish to work on this you could develop
a program that explains how to get from any school in this university to
any other school. You would need to study a map of the university to
work out how to store information about portions of routes, and you
would have to think about the form in which it would be useful for a
person to be given information about how to get to another part of the
university. It may actually be useful to go out and explore views from
different parts of the university in order to be able to print out good
advice. If you wish to create a map that can be displayed graphically,
there are facilities in Pop-11 (e.g. TEACH GSTART, TEACH RC_GRAPHIC,
TEACH FACES).

TEACH * ROUTE introduces an existing library program that gives
information about routes on the London underground network. It is also
described in the appendix to Chapter 5 of the book by Sharples et al. If
you decide to write a route-finding program you could use the format of
that program for storing geographical information, or devise your own
format.

You need to think very clearly about the objectives of your program.
Should it find all routes from A to B, or any route that works (no
matter how devious), or the shortest route, or the route that satisfies
some constraint specified by the user (e.g. "I want to go via the
library".).

-- -- -- A puzzle solving program

There are many puzzles that require you to search for a solution by
finding combinations of moves formed from basic actions, until you find
a complex action sequence (e.g. a plan) that has the required
properties. TEACH * TOWER gave a very simple example where the actions
were all of the form "Select a block" or "Select a number". A different
kind would be the river-crossing puzzle where the actions are of
different sorts (put in X, get in, get out, take out X).

You could select such a puzzle and design a program to solve it by
searching. If possible it should be a puzzle that admits various initial
states and different goal states, so that you can test the program with
different combinations of initial and final states. E.g. a general
program for solving the river puzzle would start with any legal
combination of fox, chicken and grain on river banks and find a way to
achieve any legal combination, e.g. everything on the right bank except
the man and the chicken.

Another kind of puzzle would be a sort of crossword puzzle. A program
might be given a list of words, e.g.

    [cow eel elephant little love peel tone wine]

And a puzzle in this form, where the dots represent spaces to be
filled by letters from the words. The problem is to insert all the
words consistently, with letters replacing the dots, and words going
from right to left or top to bottom.

      [[# . . . . . . . . # . . . # #]
       [# . # # . # # # # # . # . # #]
       [# . . . . # # # # # . . . . #]
       [# # # # . . . . . . # # . # #]]

In this problem the searching consists of trying different words in
different locations. There are, of course, heuristics that could
cut down the search.


-- -- 2. A "natural language" front end

-- -- -- A front end to LIB RIVER

TEACH RIVER2 introduced you to commands like

    riv_putin("fox") =>
    riv_getin() =>
    riv_cross() =>

It might be much nicer (e.g. for a child) to be able to type in
sentences in English such as

    Please put the fox in
    Put the fox in the boat
    Climb into the boat
    Join the fox in the boat
    Please row across
    Take the passenger out
    Put the fox on the bank
    Where is the chicken?
    Has anything been eaten?
    Will anything be eaten if I get in now?

TEACH RIVERCHAT gives some ideas as to how you might do this. The
simplest strategy would be to use the pattern matcher as in the
TEACH RESPOND file to cater for all the different forms of utterance.

TEACH TRAIN_CLERK introduces a possible project based on a simulated
train clerk that answers questions about trains and sells tickets.

More interesting would be to devise a grammar for the interaction
language and use the parsing facilities in LIB GRAMMAR (described in
TEACH GRAMMAR) to check whether a sentence is grammatical and if so
produce a parse tree which can then be further analysed and interpreted.
(This would be considerably more difficult than using simple pattern
matching, but more general. Some possible techniques for this are
illustrated in TEACH MSBLOCKS, but that may be too complicated for
beginners.)

If you did not finish TEACH RIVERCHAT, a relatively easy project would
be to finish and extend that. A more ambitious project could apply the
techniques to a different domain of conversation.

-- -- -- A conversational drinks machine

There are many variants of the previous idea. For example another one
would be a "talking" drinks machine. You could type in questions about
which drinks are available, how much they cost, whether they are hot or
cold, etc. The machine should also be able to tell you what change you
would get if you put in a pound coin, or a five pound note, and so on.
It should be able to tell you if it is out of some ingredient, and
perhaps suggest an alternative:

    Sorry I am out of milk, so would you prefer black coffee or
    hot chocolate?

You could do this using the database to store information about the
state of the machine, and a matcher-based conversational controller, as
in TEACH RESPOND and TEACH RIVERCHAT. (See also TEACH DATABASE, RIVER2)

Could you extend the drinks machine so that it gives you advice on which
sort of drink would suit you, depending on how how the weather is,
whether you are soon going to bed, how much money you have, what kinds
of drinks you like, whether you like milk or sugar, whether cafeine
keeps you awake, whether you are on a diet, etc.

Perhaps, when the machine is out of change, if you tell it which coins
you have, it could tell you which combination of the coins adds up to
the total required for the drink you have chosen?

If you have learnt to use some of Pop-11's graphical facilities as
described in TEACH FACES and TEACH RC_GRAPHIC you could add a graphical
display of the contents of the drinks machine, showing how it changes.


-- -- -- A diary manager

One example would be to write a diary manager program which keeps track
of all your appointments using the Pop-11 database, and has
conversations with you in English, accepting information about new
appointments, asking questions about appointments already in the
database.

A nice extension would be to have the diary manager give you advice as
to the best way to schedule some of your meetings. E.g. if you have to
meet X in Birmingham, Y Coventry and Z in London, what would be good
days to have the meetings? Or if you have to see A for two hours,
B for one hour C for an hour and a half, which would be the best way to
fit these into slots in your existing diary. Can you see some link with
TEACH * TOWER here?

-- -- 3. A program to play a board game

There are many "board" games of varying degrees of complexity, including
noughts and crosses (tic-tac-toe), a generalisation called GO-moku
(where four in a row wins on a 19 by 19 board), another generalisation
called Connect four (where you drop coloured disks down vertical
channels, nim, othello, mastermind, chess, drafts (checkers), fox and
hounds, and many more.

Writing a complete program to play a game from beginning to end can be
quite difficult, even for a simple game by noughts and crosses. A
possible project is to select a game and then develop one or more parts
of a game playing program.

E.g. the first part might manage a representation of the board, read in
moves, check whether moves are legal, check whether one side or the
other has won, and display the board along with any relevant messages.

That could be combined with a "random" move generator to play the game.

Alternatively, having got that far you could try to develop programs to
choose a good move. That might involve procedures which detect threats
that need to be blocked and opportunities for good moves, and perhaps
some way of ordering possible moves. In general a good player may have
to search through alternative combinations of moves of both players to
find out what the consequences of various moves are, before deciding
which move to adopt. (Compare searching through possible moves in order
to decide how to get the fox chicken and grain across the river.)

For a first mini-project a complete game playing program is probably too
ambitious, so aim for a partial one, and then if you have time, you can
complete it.

-- -- 4. An expert system (e.g. fault diagnosis, or planning)

TEACH * RULEBASE introduces the use of a forward chaining production
system to design a very simple expert system. More complete information
is available in TEACH * POPRULEBASE, and even more(!) can be found in
HELP * POPRULEBASE.

Several demonstration programs are provided, which you might wish to
extend.

TEACH * PRBWINE introduces an expert wine adviser. You could turn it
into something more general. This sort of thing is fairly easy, as there
is not really any problem-solving involved, just chatting to narrow down
options. Perhaps it is too easy?

TEACH * PRBZOO gives a rule-based program for identifying animals from
their descriptions. This can be very simple, perhaps too simple.
However, it could be extended in some way, e.g. so that the program
learns.

TEACH * PRBGROCERIES
This is about a program for packing groceries into bags at a supermarket
checkout point. You could try extending to to cope with more types of
items and more constraints (e.g. don't put uncooked meat or fish in the
same bag as cooked meat or fruit).

TEACH * PRBRIVER shows a much more complicated example, where the
computer works out a plan for solving the river-crossing problem.

You could try to design either a fault-diagnosis system or some kind of
planning system (more difficult). For example if you have a car or some
kind of machine that has a manual with a section concerned with
"trouble-shooting" you could find a way to give the computer the
information that is in the manual. Another possibility would be to
look at Benjamin Spock's book on Baby and Child Care, or some other
home medicine book, and design a little expert system to help parents
decide whether a baby should be taken to the doctor or not, on the basis
of different combinations of commonly occurring symptoms.

TEACH * EXPERTS gives an overview of some types of expert systems and
relevant facilities in Pop-11. The standard text books on AI give
further information that could give you ideas.


-- -- 5. An "object oriented" adventure game (possibly using SIM_AGENT)

This one is potentially quite difficult as it involves a lot of new
concepts. It is probably most suitable for students who have had prior
programming experience before starting this course.

If you have found all the programming so far very easy, and you have
worked through TEACH SEARCHING and TEACH GRAMMAR, you could try to teach
yourself about "Object Oriented Programming" using the introduction
provided in TEACH OBJECTCLASS_EXAMPLE. (This explains and illustrates
notions of classes, methods, and inheritance.) See also TEACH OOP

Then having done that you could work through TEACH ADVENT_OBJECTCLASS to
get some ideas on how to design a simple adventure game. On that basis
you could try extending the adventure game, either by making the players
more intelligent, or by adding a natural language interface of some
kind, e.g. using the ideas in TEACH RIVERCHAT.

More detailed suggestions are included in TEACH ADVENT_OBJECTCLASS

Another possibility would be to use the Objectclass facilities as a
basis for the conversational drinks machine described above, instead
of using the database for the simulation.

The file TEACH SIM_FEELINGS introduces the SIM_AGENT toolkit which
provides a framework for designing simulation in which a collection of
agents interact with one another. This could be the basis of a quite
ambitious project.

-- Other possible projects --------------------------------------------

There are MANY other possibilities for projects, including simple
teaching programs, simple learning programs, simple picture analysing
programs, and many more.

If you wish to do something different from all the above, and you have
an idea that you feel confident you could work on, you could make a
proposal. Every project topic must have been approved in advance by the
course tutor.

The project should include the use of lists to store knowledge about
something, and the use of the pattern matcher or database procedures to
access information in lists. Ideally it should involve some searching to
find a solution to a problem.

For additional example project topics look at TEACH * PROJECTS


-- WARNING ------------------------------------------------------------

Each of the above topics is potentially something on which you could
spend far more time than you will have available. So it is important
that you do  NOT aim to design an all-singing all-dancing program that
does everything that could possibly be required for the task you have
chosen.

It will be enough if you design, implement, test, and report on an
ILLUSTRATIVE SUBSET of the facilities. Your report can mention the ways
in which the program is incomplete and might be extended.

Some students who enjoy programming will find this warning very hard to
remember and will therefore spend far too much time on the programming,
and as a result may not have enough time to produce a good report.
Remember the report is the most important thing you have to hand in: the
program is merely background.

-- Formulating a proposal ---------------------------------------------

Before you finally decide on your project it is important that you
write a first draft proposal for approval by your tutor, and then a more
detailed proposal after your topic has been approved. The first draft
proposal should:

a. Describe the domain

b. Give some examples of the kind of behaviour you would expect your
   program to produce (a mini-scenario).

c. Sketch the strategy you intend to follow implementing the program
   (Referring to relevant teach files if appropriate)

This proposal should be NO MORE than one page one.

-- After the topic has been approved: a project plan ------------------

Having had the topic approved, you should try to expand your proposal
into a project plan, which should have all the following sections:

a. A brief description of the problem domain (e.g. see the list of
   possible topics, above.)

b. A first general statement of the problem you intend to solve in that
   domain, i.e. a summary of what the program will actually do, and what
   it is for.

c. Some brief examples of the kind of behaviour you would expect your
   program to produce (some scenarios).

d. An outline "ontology" for the program, i.e. the kinds of objects
   properties, relationships, events and processes that you expect
   your program to know about. (Some kind of tree-structured diagram
   showing the different classes of objects and their properties could
   be useful here.) (NB this ontology concerns the things in the world
   not the things in the program. E.g. rivers, boats and animals, not
   lists, words, numbers, objectclass structures.)

e. Plans for the form in which the information about these things will
   be stored in the program. E.g. will you use the Pop-11 database,
   or perhaps something else (e.g. Objectclass structures)?

f. A list of the main procedures and how they will work. (Diagrams may
   help here.)

g. A timetable for doing the various bits of the task, including
   writing the report.

This project plan could be between three and five pages in length. It
will provide an important checklist for you as you work on the project.
You are likely to change your plan as you learn more about the problems
through designing and testing the programs. As that happens you can
modify the plan, but there should always be a *current* plan
representing what you are doing and how and when.

TEACH * PROPOSALS may give you some ideas on how to plan your project.

-- Writing up the report ----------------------------------------------

TEACH * REPORTS makes a number of suggestions regarding how to write up
a report. You are not obliged to stick to the format proposed there, but
if you deviate from it then you should have good reasons.

NOTE: You should find out the length requirement for your report, and
make sure that the main report does not exceed that length. You can
added extra material in the program listings and other appendices.

(See HELP WC for a Word Counting program).

You can use HELP RNO and HELP VED_RNO to find out how to format the
text, number pages automatically, etc., if you write your report using
VED. More ambitious students may wish to learn to use Latex. See
TEACH LATEX, TEACH LATEX.TEX The report must NOT be handwritten.


-- Handing in the report ----------------------------------------------

You will be given a special "cover sheet" that you should use as the
front page of your report.

This should show the TITLE of your project AS WELL as the course title.
(Every project should have a descriptive title: not just "programming
project".)

Make sure that your report is submitted in a form that is convenient to
read. Do NOT hand in fan-folded pages direct from the printer: separate
the pages, trim them (i.e. remove sprocket holes), and staple or clip
them together with the cover sheet on top.

Aim to get it all printed out at least three days before the deadline:
one of the unfortunate laws of nature is that computers or printers
always break down just before deadlines, so if you leave things till the
last moment there will be no excuse for late submission.


-- What assessors will be looking for ---------------------------------

Marking examinations, essays and project reports, like so many other
things is a very subjective process. However you may find it helpful
to be aware of some of the considerations that markers take into account
when assessing projects.

There is a list of possible factors described in

    TEACH * AI1PROJECT.CHECKLIST

Which of these factors are actually used will depend on the stage the
student is at and the type of project. In general first year projects
will be examined more leniently than more advanced projects.

Important points to watch out for are these (see TEACH REPORTS):

1. Your report must explain how ANY person can run your program without
being logged in as you. Give instructions on how to test your program,
including explicit examples of what to type in. This should be in an
appendix, clearly identified in the table of contents.

That means that any files or directories must be named by the full
explicit path name. Also any files that load other files must load them
via the full path name (unless they are all in the same directory in
which case one can load the files from that directory).

This also means that any directory your files are in must be readable
by anyone, as must the files themselves.

2. Your report should explain very clearly WHAT the program does, HOW it
does it, what works and what doesn't, and what its strengths and
weaknesses are.

3. Your report should not mix up levels of explanation, and in
particular should not go into great details in the form of a line by
line explanation of the programs. Separate the description (WHAT) from
the explanation (HOW).

4. Your report should include some examples of the program working, but
should NOT include lengthy indigestible sections of program printout,
such as can be produced by TRACE.

5. Your report should clearly acknowledge any use of programs produced
by other people, including programs copied from TEACH FILES.

6. Grammar, spelling and English style should be good. Make sure that
you proof-read the report before handing it in. Last-minute corrections
can be made in ink if necessary. It is desirable to get another student
to read a draft of your report and make comments on its clarity,
interest, etc. You should do the same for other students.

7. The report should show that you have learnt more about AI than you
could have got simply by doing Pop-11 exercises and attending lectures.
Your reading of AI textbooks, journals, conference proceedings, etc.
will help.

REMEMBER: the educational value to you of doing the project and
producing the report on it are of far more importance than its role in
assessment.


--- $poplocal/local/teach/pop11_project
--- The University of Birmingham 1999.  --------------------------------
