TEACH PROJECTS                                 Updated A.Sloman Feb 1988
                                         Updated Phil Husbands, Feb 1989
                                                 Sharon Wood, March 1991
                                              Modified A.Sloman Jan 1998


                     POSSIBLE AI PROGRAMMING PROJECTS
                     ---------------------------------

CONTENTS

 -- Introduction
 -- Choosing a project topic
 -- Possible Topics
 -- previous AI1 and KBS Project Titles
 -- Planning your project
 -- On avoiding disasters: allow a few days for them
 -- Further reading

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

This file was originally produced at Sussex University for students
doing the AI course or the MSc degree course in Knowledge Based Systems.
It has been substantially modified and extended at Birmingham, for
undergraduates and MSc students doing AI projects.

Students who have not been doing an AI or Cognitive Science degree but
are interested in doing an AI project may be able to do so if they first
teach themselves an AI language. The easiest language to learn for this
purpose is probably Pop-11, which is very similar in power to Common
Lisp, but more readable and better integrated with a teaching
environment, including integrated editor, and a large amount of online
documentation with tutorial examples.

If you are an experienced programmer, you can probably teach yourself
Pop-11 using the Pop-11 Primer which can be bought from the School
Library (Price 4 pounds). For online reading there is a plain text
version in
    /bham/poplog/local/teach/primer

Please do not attempt to print the primer, as it is nearly 18,000 lines
long.

The primer is now available for reading via a web browser (e.g. Netscape
or lynx) at
    ftp://ftp.cs.bham.ac.uk/pub/dist/poplog/primer/START.html

To find out more about Pop-11 (and Poplog) and how to run it, see the
man file: MAN POP11, and these web pages:
    ftp://ftp.cs.bham.ac.uk/pub/dist/poplog/poplog.info.html
    http://www.cogs.susx.ac.uk/users/adrianh/poplog.html
    http://www.cogs.susx.ac.uk/users/adrianh/pop11.html
    http://www.cvg.cs.reading.ac.uk/poplog

-- Choosing a project topic -------------------------------------------

The range of possible projects in Artificial Intelligence is huge. There
are many ways of arriving at a project proposal, including the
following.

1. Select a topic about which you have read in one of the AI textbooks,
or learnt about in lectures, and try to replicate the program described
there, using your own detailed design and testing. You will always learn
something even by re-implementing what others have done.

2. Look back at some of the teach files you have previously worked
through, and other teach files in the Poplog libraries. Many of them end
with quite difficult exercises which could be expanded into projects.
Examples are

TEACH RULEBASE              TEACH POPRULEBASE       TEACH EVANS
TEACH INDUCE_RULES.P        TEACH NEWSOLVER

TEACH GRAMMAR               TEACH PARSING           TEACH MSBLOCKS

TEACH PICTURES              TEACH REGIONS           TEACH LABELLING
TEACH WALTZ

TEACH ADVENT_OBJECTCLASS
TEACH SIM_AGENT             TEACH SIM_DEMO

TEACH FACES                 TEACH RC_GRAPHICS       TEACH RCLIB_DEMO.P
TEACH RC_GRAPHPLOT

3. Take one of the problems on which you have already worked and extend
the programs.

4. Think about some task that you are able to perform, e.g. playing a
game like noughts and crosses or battleships, or mastermind, checking
logical proofs, solving algebraic equations, translating sentences from
one language to another, teaching an absolute beginner Pop-11 (or some
other programming language), finding syntactic errors in simple programs
and fixing them, teaching a young child arithmetic, teaching someone
elementary logic.

Then try to analyse how you do that task, and attempt to implement that.
You will also need to read up books on AI (and maybe psychology,
linguistics, etc.) which are relevant to the task, to get ideas.

5. Study some task that insects or other animals can perform and attempt
to simulate their ability in a simulated world. An example might be
"flocking behaviour" of a groups of animals, or finding food and
bringing it home, or learning the structure of some terrain (e.g.
exploring a network of corridors with rooms of various kinds on
those corridors, and building up a "cognitive map" of the network so
that thereafter you can select a good route from one place to another
even if you have not followed that exact route before).

6. Consider some task that you are able to perform but which you think
not everyone can perform, e.g. solving puzzles, doing arithmetic,
writing programs, and try to devise a program that will teach others to
do it. (HELP LOGIC describes a program to teach fluency in propositional
logic through some simple games. The code is all in LIB LOGIC. You
could try to extend it, or give it a graphical interface.)

7. Develop a package that helps users do something, providing a more
helpful interface than existing Unix and X interfaces. E.g. this could
be a graphical interface for running Unix programs and reading their
output, for finding MAN files that are relevant to some topic, or
even learning to use Unix. (A WEB based tutorial on unix can be found
in /bham/doc/unixhelp.html It has many flaws. Perhaps you can improve it
by adding some AI support, e.g. a program that keeps track of what the
user has already looked at: the existing files often present you
with information in the wrong context. See also HELP SHELL and
HELP UNIX.COMMANDS)

8. Look at some of the things you found difficult when learning to
program Pop-11, or things you did not like about the editor, then try to
devise an aid to help other students overcome the problems. E.g. can you
improve the menu interface?

See TEACH VED_MENU. Or try using the facilities described in TEACH
RCLIB_DEMO.P to build a new improved interface to VED or Pop-11 or
Prolog for beginners.

(It is possible in VED to trigger a procedure every time a key is
pressed. So in principle an intelligent assistant could "watch" all of a
user's typing and make suggestions, give warnings, put up relevant
menus, etc.)

For some of the above projects you may like to use a graphical
interface. There are several tools for building graphical interfaces in
Pop-11. You could look at the following

    TEACH RC_GRAPHIC, TEACH RCLIB_DEMO.P and files referred to in that

    HELP POPUPTOOL, TEACH PROPSHEET, TEACH VED_MENU


-- Possible Topics ----------------------------------------------------

What follows is a list of suggestions to illustrate the range of
possibilities. Some of them have been done in previous years.

This is a randomly ordered list of possible project topics that may give
you some ideas. There is no need to feel restricted to using this list.

* Some of the items below refer to turtle pictures. The idea is that a
mechanical turtle can crawl around a 2-D array leaving a trail of
"paint" some of the time. This is one way to make pictures, which can
then be analysed and interpreted by programs that inspect the array. See
TEACH VTURTLE for a program that allows you to treat an editor buffer as
a 2-D array in which turtle pictures can be drawn. This package was
developed before the RC_GRAPHIC library was available. You might like to
try extending the VTURTLE library so that it links up with RC_GRAPHIC
somehow.

*  An Eliza-like program.  This could extend TEACH ELIZA to include a
wider variety of cues and responses. You could try to give the program a
better grasp of English grammar. Maybe use some of the procedures in LIB
GRAMMAR. The danger is that the program will not have a rich structure. It
could end up made of lots of little procedures all doing essentially the same
sort of thing. This is not encouraged, except for students who are
having great difficulty in programming.


*  A conversational program which accepts information about some topic -
for example geography, or a family tree, or the layout of furniture in a
room, or train time-tables, and which can answer questions. The
interaction language could either be a subset of English or, less
ambitiously, something like data-base patterns. If you choose a subset of
English it will have to be pretty restricted. E.g. think of railway
announcements, or newspaper headlines.

*  A program which accepts simple English descriptions of pictures then
draws appropriate Turtle pictures. For example descriptions might be:
"A SQUARE INSIDE A BIG RECTANGLE TO THE RIGHT OF A SMALL TRIANGLE".
"A SQUARE ABOVE A TRIANGLE SHARING ONE SIDE".
The sort of description given in geometry problems: "D IS A POINT ON A
LINE AB. CD IS PERPENDICULAR TO AB, AND THE ANGLES ABC AND BAC ARE
EQUAL".

*  A program which analyses a Turtle picture and produces an interpretation.
This might be either a description to be printed out, or a collection of
assertions in the data base, as in the PICTURES and SEEPICTURE demos.  The
information in the data base could be used to answer questions about the
picture. (If you don't want to write the programs to find the lines and
junctions you could use the findlines and findjuncs library programs to do
the preliminary analysis.) The program might be made to recognise simple
shapes, or to segment pictures of overlapping rectangles. There is a very
large range of possible extensions.

*  A program which analyses the state in some game (chess, draughts,
noughts and crosses, battleships, etc.) and selects a good (or
reasonable) move.  This could evolve into a program which plays the
game.

*  Completing a jigsaw puzzle.  Think of a puzzle made of coloured
pieces, with square, rectangular or triangular shapes. The task is to
assemble the pieces to form some specified pattern.

*  A program to find its way out of a maze.  (You could use the Turtle
to draw the maze).

*  A program which draws "interesting" mazes, that is mazes which are
not too easy, not too difficult.

*  A program which learns to recognise simple shapes (squares,
triangles, faces made of squares etc.) by being given pictures and told
what they are.

*  A blocksworld program which can carry out commands and answer
questions.  (I.e. extend teach BLOCKS)

*  An engine and some trucks are on a set of railway lines connected by
points. Use the engine to get all the trucks into a siding.

*  Write a program to do some logic.  It could use truth-tables to test
simple arguments for validity. Or it might be given some axioms and
rules and then asked to prove theorems derivable from the axioms in
accordance with the rules. Or it might transform formulas into a 'normal'
form, then test for consistency.

*  Write a program to create "magic squares" (i.e. a square array of
numbers all of whose rows, columns and diagonals add up to the same
total. It's easy for a 3 by 3 square, so start with that, then try 4 by
4. Why can't it be done for a 2 by 2 square?

*  The missionaries and cannibals puzzle, or some other puzzle.

*  A simple translation program - to translate bits of English into
German or vice versa.

*  A program to analyse the harmonies or rhythms in some piece of
music.

*  A program which solves problems about family relationships, for
example "Is your mother's grandfather's wife your sister's grandmother's
mother?" "Can your uncle be a bachelor and an only child?"

*  A variation on a jigsaw puzzle project. Design a program which knows
about some words (e.g. knows whether they are nouns, verbs, adjectives,
etc.), and which can be given a sentence with one or more words missing.
Its task is to decide which of the words it knows about could fit into
the gaps.  E.g. if it knows the following words:
        CAT KICK OLD IS LICKED
then it should be able to select suitable fillers for the gaps in:

        [THE DOG BIT THE ... ]
        [THE ... MAN KICKED THE DOG]
        [THE DOG ... THE MAN]

How much grammar would the program need to know?

*  A slightly different version. A program which can take a list containing a
bit of POP11 code, with a gap, and select a suitable word or symbol to fill
the gap. E.g. what is missing from:
        [IF X > Y ... X ELSE Y ENDIF]

* A program to correct errors in simple POP-11 programs.

*  A program to do sums like a young child - adding and subtracting
(and multiplying?) using columns representing hundreds, tens, units etc.
Designing the program should lead to theories about the kinds of
mistakes children are likely to make and explanations of such mistakes.

*  A program to solve simple crossword puzzles (e.g. from children's
puzzle books.). Alternatively, give it an incomplete crossword puzzle,
and one clue and see if it can work out the answer to that clue.

* A program to analyse images of some kind. Digitised images can be
provided.

*  A program to analyse Turtle pictures with curved lines. E.g. finding
closed regions.

*  Look at the pictures in a child's colouring book.  Try to analyse
some of the problems in recognising the objects depicted. Design a
program to cope with some of these problems. Alternatively, look at the
problems involved in copying the pictures, or colouring them in (e.g.
which bits of the picture should have the same colour.)

*  A program to copy turtle pictures in something like the way a child
might (e.g. find important sub-structures and try to draw them. What
problems of planning, etc., would this give rise to?)

*  A program to teach elementary programming in POP11. It should pose
problems like those in our exercise sheets, read in the students'
answers, and give advice and criticism. (For example, it could start
with simple arithmetic expressions, and look for errors of bracketing,
missing out operators, etc. Or it could look at simple turtle programs,
looking for syntactic mistakes, or "silly" features, like two TURN
commands without any DRAW or JUMP in between.)

*  A program which is given information about roads in a town and which
can plan routes from one location to another. How should the layout of
the town be represented? An extension of this would be to add
information about an alternative method of transport, e.g. underground,
or bus-routes, and have the system capable of planning a route depending
on how much time you've got, whether you can afford taxis, whether you
suffer from claustrophobia, etc.

*  A program which plays mastermind or word mastermind. (In the latter
case a word of four (or more) letters is chosen from a specified list,
and the program has to try to guess the word in as short a sequence of
guesses as possible, being told each time only whether it has any
letters right and if so how many of them are in the correct position.)

* Implement some kind of parser that you have read about.

* Pop-11 contains powerful tools for implementing incremental compilers
for other languages. That is how Common lisp, Prolog and ML were
implemented in Poplog, three very different languages. You might like to
try using Pop-11 to implement a compiler for another language, e.g.
Java or Scheme. (C and C++ could not easily be done because Poplog store
management is incompatible with allowing user programs to create
pointers into the middle of a datastructure: the garbage collector might
relocate that structure and then the pointer would no longer work.) For
more information see
    REF POPCOMPILE
    REF VMCODE
and the source code files for lisp, prolog and ml in
    $usepop/pop/lisp/src/
    $usepop/pop/plog/src/
    $usepop/pop/pml/src/

* At Birmingham we have developed a powerful toolkit (SIM_AGENT) for
building simulations involving one or more agents taking in information,
interpreting it, deciding what to do, making plans, perhaps getting
emotional, performing actions, communicating with other agents, etc.
A project could be based on using that toolkit, either on your own, or
in collaboration with other students, to build some simulated scenario,
e.g. perhaps an adventure game. Some students have used it to simulate a
sheepdog herding a group of sheep into a pen (difficult).

To use the toolkit you first need to learn about object oriented
programming in Pop-11 (See TEACH OOP and follow up references to
Objectclass) and rule-based programming (See TEACH RULEBASE).

You can find an introductory overview of the toolkit TEACH SIM_AGENT.
There is a (long) introductory example involving two teams of agents
each instructed by their captains to march past obstacles to a target
location in TEACH SIM_DEMO

* We have also recently developed a powerful graphical package which can
be used for creating control panels, menus, pictures, etc. e.g. for
interactive programs playing games, giving tutorials, or controlling
other programs. This is described in
    HELP RCLIB, TEACH RCLIB_DEMO.P, TEACH RC_LINEPIC
and other online tutorials referred to there. A student project could

    (a) extend this package in some way (suggestions available)
    (b) use it to build an interface to something else, e.g.
        VED, Pop-11, Unix, mail, ....
    (c) use it to build some sort of interactive program, e.g. a board
        game or a tutorial program.

There are other possibilities. E.g. in SIM_AGENT it can be used to
demonstrate what the agents are doing, and also to provide control
facilities while agents are running.

-- previous AI1 and KBS Project Titles --------------------------------

A list of titles of some previous projects submitted by second year
undergraduate students at Sussex can be found in TEACH * KBSTITLES


-- Planning your project ----------------------------------------------

For an AI course we prefer you to design a program to do something which
people (e.g. you) can do, so that in the process you may have some
insight into the problems of explaining how you do it. Trying to make
a computer do something you cannot do yourself is very risky.

The file TEACH * PROPOSALS gives some suggestions on planning a project.
It is very important to think hard about the goals of your project and
try to be clear about what you are trying to achieve and what sorts of
behaviour your program will produce BEFORE you start writing the
program.

TEACH * PGUIDE gives suggestions on doing an AI project.

TEACH * PSTYLE gives advice on how projects should be written up. It is
probably a good idea to look at it early on so that you can get a feel
for what you are aiming to produce. Remember that as far as assessment
is concerned the write-up is more important than the code. So make sure
you leave enough time to write a good report. TEACH * REPORTS is for
more elementary project reports, but some of its advice is still
relevant for a longer project.

In the early stages the hardest task is to define what your goal is, and
perhaps to justify it.

Try writing down, first of all, a page or so, sketching out what you
plan to do (not necessarily HOW are going to achieve it), and why you
find it interesting. Write a page on each of WHAT and WHY, for instance,
or half a page.

The WHAT description should describe the ontology of the domain, i.e.

    what kinds of objects your program is concerned with
    what kinds of properties the objects can have
    what kinds of relationships can exist between objects
    what kinds of changes or processes can occur (usually changing
        properties or relationships)

    The description of the ontology should be INDEPENDENT of how your
    program is going to work. It should a specification that could be
    given to someone who might then choose a different implementation
    from yours.

The WHY description could be much shorter. It should motivate the
project either in terms of practical applications, or theoretical
interest (e.g. explaining some human capability), or because it is
fun, or....

If you have any idea as to HOW you are going to do it you should produce
a sketch of a description. E.g. indicate the kinds of data-structures
(lists, vectors, POP-11 database, or whatever) that you are going to use
to represent the items described in the ontology. Summarise the main
procedures you are going to require.

When you are reasonably happy with the general topic (having discussed
it with the tutor) you should design a 'scenario'.  That is sketch out
an imaginary demonstration of the performance of your finished program.
This should not include any details of how it works, but could include
marginal comments indicating points of interest. A good example of
such a scenario is that used by Winograd to explain what his program
SHRDLU was about. You can find it reproduced in many books, e.g.
Boden's book, J.Benthall (ed) THE LIMITS OF HUMAN NATURE, Schank and
Colby, COMPUTER MODELS OF THOUGHT AND LANGUAGE.


Read Winograd's scenario and then see if you can devise an interesting
exposition like his, but obviously on a smaller scale. Make your reader
want to know how the program works.

Having designed the scenario try decomposing the problem. That is,
try to identify as many of the sub-problems as you can, and sketch
strategies for solving them. Try writing procedures to deal with the
sub-problems, and wherever possible test them independently of one
another. You may find it useful to prepare a chart showing which
procedures use which others. Also, for each procedure write down a
specification of what it is supposed to do. What inputs will it be
given? What output will it produce? Will it change a turtle picture, or
the database, or some 'global' variables when it runs?

Try putting the bits together. There are bound to be bugs. Often you
have to abandon an approach and try a totally different organisation.
Sometimes in the course of implementing your ideas you will find that
you want to revise your objectives. Usually people end up with less
ambitious goals than they started with.

This whole process could take many weeks. Don't aim for something too
ambitious or you will be disappointed at not getting there. Make sure
you discuss with your tutor, and other students, what you are doing and
why.


-- On avoiding disasters: allow a few days for them -------------------

Most topics are very open-ended. That is, you can go on indefinitely
adding to the problems your program might be expected to solve. It is
important not to fall into the trap of doing this. Stop programming in
time to write a good report. You can then later add some bells and
whistles to your program if you have extra ideas, and attach an appendix
describing the extensions to your report.

Also remember that computers can fail without notice, and as a result
your work may be lost. So you should aim to ensure that you are ready to
print out the report a few days before the project deadline in case
there are last minute disasters. Assessment exercises handed in late
suffer penalties that can seriously affect the degree result.

There was one student who did not heed this warning who was working on
the report a few hours before the deadline and then accidentally deleted
the whole file.


-- Further reading ----------------------------------------------------

TEACH * PROPOSALS
TEACH * PGUIDE
TEACH * REPORTS
TEACH * PSTYLE
TEACH * PROGSTYLE

--- $poplocal/local/teach/projects
--- Copyright University of Sussex 1989. All rights reserved. ----------

--- $poplocal/local/teach/projects
--- Copyright University of Birmingham 1998. All rights reserved. ------