TEACH AI1.PROJECTS Aaron Sloman Nov 1993 CONTENTS - (Use g to access required sections) -- Introduction -- Objectives of the mini-project -- Techniques that your project will need -- Possible topics -- -- 1. A route finder program. -- -- 2. A "natural language" front end -- -- -- A front end to LIB RIVER -- -- -- A conversational drinks machine -- -- 3. An expert system (fault diagnosis, or planning) -- -- 4. An "object oriented" adventure game -- 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 AI1 Pop-11 programming course is to propose design, implement, and document a mini-project implemented using Pop-11. 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. 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. Teaching staff and demonstrators are available to help you cut down your project goals to a size that suits your abilities. Students who wish to collaborate on a project may do so, as long as they 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 Aaron Sloman or your tutor if you prefer. (Email to either "a.sloman" on the computer science network or "slomana" on sun1. The latter will be automatically forwarded.) (MSc students may have different arrangements.) -- Objectives of the mini-project ------------------------------------- There are several highly 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 start learning how to test your programs and to track down bugs. (Everyone produces bugs at some stage during the development of programs: learning techniques for finding the source of the problem when your program doesn't work properly is very important for anyone who needs to be able to design working systems or explanatory theories.) 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 In some cases where 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. Because we expect students who have not previously done any programming to take a few months to develop confidence and fluency, the first term mini-project for AI undergraduates will count for less than the second term mini-project. (There are different arrangements for MSc students) -- Techniques that your project will need ----------------------------- Your project should make use of a subset of the techniques that you have learnt this term. These techniques include: A. General programming techniques such as: - defining procedures that form a package that work together - using a variety of syntactic control structures including conditionals and loops of various kinds - manipulating lists and other data-structures - describing programs (saying what they do and how they do it) 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, MATCHES, DATABASE, RIVER) - using a search strategy to permit the computer to find a solution to a problem by exploring combinations of alternatives (E.g. TEACH TOWER.SEARCH, SEARCHING) - designing a simplified natural language interface to replace a typical programming command interface. (E.g. TEACH GRAMMAR, TEACH RIVERCHAT) - designing a simple expert system of some kind (E.g. LIB ANIMALS, LIB GROCERIES, TEACH SEARCHING, TEACH PSYSRIVER) It isn't necessary for every student to address all these techniques. You may focus on a subset that interests you. Note: Later you will learn other techniques including the use of logic and neural nets. -- Possible topics ---------------------------------------------------- Here is a list of recommended 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. This means that you may need quite a lot of 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 route finder program. In TEACH SEARCHING you will find some general techniques for building a program that solves a problem by exploring a search space. A possible application for this, 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. TEACH ROUTE introduces an existing library program that gives information about routes in London. You might want to take some ideas from that. You could also use ideas from the Sharples et al. book Computers and Thought, which describes a route-finding program. It is up to you to decide whether your program should find all routes, 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".). -- -- 2. A "natural language" front end -- -- -- A front end to LIB RIVER Teach river introduced you to commands like putin(fox); getin(); crossriver(); 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. 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.) -- -- -- 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) -- -- 3. An expert system (fault diagnosis, or planning) LIB ANIMALS and LIB GROCERIES introduce the use of a forward chaining production system to design a simple expert system. Note: In order to access them, you need first to run the command lib ai1 TEACH PSYSRIVER shows a 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. -- -- 4. An "object oriented" adventure game This one is potentially quite difficult as it involves a lot of new concepts. 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.) 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. -- Other possible projects There are other possibilities for projects. If you really 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. Only projects based on topics that have been approved in advance are acceptable. -- 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 don't 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 do: 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 comment by your tutor. This 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 NOTE: most students invent projects that are too complicated for the time available: expect to have to curtail your ambitions after you have started working on the project and have discovered some of the unexpected complications and difficulties. (They ALWAYS turn up!) -- 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. -- 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: the length of the main report on a mini-project (excluding the program listings and other appendices) should be no more than about 2000 words. (See HELP WC for a Word Counting program). You can use HELP RNO and HELP VED_RNO to provide help regarding formatting the text, getting pages automatically numbered, etc. -- Handing in the report ---------------------------------------------- You will be given a special "cover sheet" that you should use as the front page of your report. 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 long list of possible factors described in TEACH PROJECT.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. The most important points to watch out for are these: 1. Your report should explain very clearly WHAT you did, HOW you did it, HOW to use the program, and what its strengths and weaknesses are. 2. 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). 3. 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. 4. Your report should clearly acknowledge any use of programs produced by other people. 5. 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. But remember: the educational value to you of doing the project and producing the report are of far more importance than its role in assessment. --- $poplocal/local/teach/ai1.projects --- The University of Birmingham 1993. --------------------------------