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